Prisoners and hats puzzle
From Wikipedia, the free encyclopedia
The prisoners and hats puzzle is a logic puzzle that involves reasoning about the actions of other people, drawing in aspects of Game theory. There are many variations, but the central theme remains the same.
Contents |
[edit] The 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.
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.
[edit] 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).
In common with many puzzles of this type, the solution relies on the assumption that all participants are totally rational and are 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 C violates the "No communication" rule (given that communication is usually defined as the "transfer of information").
[edit] Variant
In a variant of this puzzle 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. (D again not to be seen and only there to wear the last hat)
[edit] The solution
There are two possible ways to solve this puzzle: the trivial way would be that one of the 3 prisoners wears the single off-colour hat, and thus the other two can easily deduce the colour of theirs. In the non trivial case each prisoner wears a hat of the same colour (while D wears the off colour hat). After a while the one of the prisoners should be able to deduce that, since none of the other was able to state the colour of his own hat, he must wear a hat of the same colour as the others.
[edit] Three-Hat Variant
In this variant there are 3 prisoners and 3 hats. Each prisoner is assigned a random hat, either red or blue. Each person can see the hats of two others, but not their own. On a clue, they each have to guess their own hat color or pass. They win release if at least one person guessed correctly and none guessed incorrectly (passing is neither correct nor incorrect).
This puzzle doesn't have a 100% winning strategy, so the question is: What is the best strategy? Which strategy has the highest probability of winning?
If you think of colors of hats as bits, this problem has some important applications in coding theory.
The solution and the discussion of this puzzle can be found here (also a solution to the analogous 7-hat puzzle).
