面白い問題スレの過去ログに同じ問題の解説が載っている。
かなり詳しく解説されているから、わからない人は読むといい。
こちらは帽子の色ではなくて、獰猛な飼い犬バージョンだが
問題としては全く同じもの。
なぜ少なくとも一人いると言う仮定が必要なのかも解ると思う。

http://www3.tokai.or.jp/meta/gokudo-/omoshi-log/1026218280.html
174-202 あたり