Question

There are N students each wearing either a red or white hat, call them student 1, student 2,.., student N. They can see the color of everyone else’s hat expect their own. A teacher asks them sequentially (student 1 first, student 2 second, and so on) if they know the color of their own hat.
a) Does any of them reply in the affirmative?
The reality is that all of them are wearing a red hat. The teacher announces that at least one student is wearing a red hat. Then she again asks them sequentially if they know the color of their own hat?
b) Show that if N=2 then the second student will reply in the affirmative.
c) Show that for any general N, the first N-1 students will not know the color of their hat but the Nth
student will.
d) Briefly explain the idea of common knowledge at play here.

Answer 1

This is a classic "prisoners and hats" puzzle. This puzzle is based on a concept called Hierarchy of Beliefs. Which involves reasoning on the basis of actions of the other people involved.

Initially, the players have to devise a plan to communicate information among themselves. The most popular strategy used is to first stand in a circle and then to raise their hand if the player standing to the immediate right is wearing a Red hat.

A) When the teacher announces that at least one person is wearing red then. All the players will raise their hand with respect to the above given technique. After that, all the players will look to their immediate left to see if their own hat is red or white. If the player on their immediate left raises their hand it means their hat is red, if not then it is white. Hence, everyone will be able to provide the color of their own hat.

B) If N=2, then both would let each other know what color they see. Hence, both would be able to tell the color of their own hat.

C) Generally, using the above technique all would know the color. But in order to satisfy the above statements then a different strategy and formation is needed. Which is, for all the players to stand on a staircase and everyone facing one direction. Therefore, the player on the top of the staircase (Nth player) could see the colors of all hats except his/her and all the players (N-1 students) can see the colors of the hats who are standing in front of him/her but not his/hers and all the player standing behind. In such formation, the players will say red if the number of red hats in front are even and white if the number of red hats in front are odd. By this, all N-1 players will be able to deduce the color of their hat by counting the number of red hats in front of him/her. The Nth player will have 50-50 chances of saying the right answer.

D) As explained above, the idea of common knowledge will allow to pass on the information which cannot be seen by an individual alone. The strategy acts only as a medium to communicate information to a single or a collective group of people.