The prisoners and hats puzzle is an induction puzzle (a kind of logic puzzle) that involves reasoning about the actions of other people, drawing in aspects of Game theory. Generaly interview questions asked from math oriented. Companies expect that IT students have the backround knowledge of problem solving. This puzzle comee under game theory.

Puzzle : Prisoners and three hats

Four prisoners are arrested for a crime, but the jail is full and the jailer has nowhere to put them. He eventually comes up with the solution of giving them a puzzle so if they succeed they can go free but if they fail they are executed.

The jailer puts three of the men sitting in a line. The fourth man is put behind a screen (or in a separate room). He gives all four men party hats (as in diagram). The jailer explains that there are two red and two blue hats. The prisoners can see the hats in front of them but not on themselves or behind. The fourth man behind the screen can't see or be seen by any other prisoner. No communication between the men is allowed.

If any prisoner can figure out and say (out loud) to the jailer what colour hat he has on his head all four prisoners go free. The puzzle is to find how the prisoners can escape.

The solution

For the sake of explanation let's label the prisoners in line order A B and C. Thus B can see A (and his hat colour) and C can see A and B.

The prisoners know that there are only two hats of each colour. So if C observes that A and B have hats of the same colour, C would deduce that his own hat is the opposite colour. However, If A and B have hats of different colours, then C can say nothing. The key is that prisoner B, after allowing an appropriate interval, and knowing what C would do, can deduce that if C says nothing the hats on A and B must be different. Being able to see A's hat he can deduce his own hat colour. (The fourth prisoner is irrelevant to the puzzle: his only purpose is to wear the fourth hat).

Puzzle : Prisoners and Four - hats.
Now the same puzzle with different condition. Instead of two red and two blue hats there are 3 hats of one colour and only 1 hat of another, and the 3 prisoners can see each other i.e. A sees B & C, B sees A & C and C sees A & B. As like shown in diagram (D again not to be seen and only there to wear the last hat)

The solution

There are two cases:
In first case, one of the three prisoners (in A, B, C) wears the single off-colour hat, thus the other two can easily deduce the colour of theirs. For example if A is single color then B can see that C and A have different color hats. From this he concludes that his color is not single so he shouts his color.

In second case, the three prisoners wear hats of the same colour, while D wears the off-colour hat. After a while, all four prisoners should be able to deduce that, since none of the others was able to state the colour of his own hat, D must wear the off-colour hat.

Puzzle : Prisoners and Five - hats.
Another different condition. only three prisoners and five hats (supposedly two black and three white) are involved. The three prisoners are ordered to stand in a straight line facing the front, with A in front and C at the back. They are told that there will be two black hats and three white hats. One hat is then put on each prisoner's head; each prisoner can only see the hats of the people in front of him and not on his own's. The first prisoner that is able to announce the colour of his hat correctly will be released. No communication between the prisoners is allowed. After some time, only A is able to announce (correctly) that his hat is white. Why is that so?

The solution

Assuming that A wears a black hat.

• If B wears a black hat as well, C can immediately tell that he is wearing a white hat after looking at the two black hats in front of him.

• If B does not wear a black hat, C will be unable to tell the colour of his hat (since there is a black and a white). Hence, B can deduce from A's black hat and C's response that he (B) is not wearing a black hat (otherwise the above situation will happen) and is therefore wearing a white hat.

This therefore proves that A must not be wearing a black hat.