Prisoners and hats puzzle

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 sometimes called the hierarchy of beliefs. There are many variations, but the central theme remains the same. It is not to be confused with the similar Hat Puzzle.

According to the story, 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.

[1]

The jailer seats three of the men into a line. B faces the wall, C faces B, and D faces C and B. The fourth man, A, is put behind a screen (or in a separate room). The jailer gives all four men party hats. He explains that there are two black hats and two white hats, that each prisoner is wearing one of the hats, and that each of the prisoners see only the hats in front of him but neither on himself nor behind him. The fourth man behind the screen can't see or be seen by any other prisoner. No communication among the prisoners is allowed.

If any prisoner can figure out what color hat he has on his own head with 100% certainty (without guessing) and tell the jailer, all four prisoners go free. If any prisoner suggests an incorrect answer, all four prisoners are executed. The puzzle is to find how the prisoners can escape.

The prisoners know that there are only two hats of each color. So if D observes that B and C have hats of the same color, D would deduce that his own hat is the opposite color. However, if B and C have hats of different colors, then D can say nothing. The key is that prisoner C, after allowing an appropriate interval, and knowing what D would do, can deduce that if D says nothing the hats on B and C must be different; able to see B's hat, he can deduce his own hat color.

In common with many puzzles of this type, the solution relies upon the assumption that all participants are totally rational and intelligent enough to make the appropriate deductions.

After solving this puzzle, some insight into the nature of communication can be gained by pondering whether the meaningful silence of prisoner D violates the "No communication" rule (given that communication is usually defined as the "transfer of information").

...
Wikipedia