Friday, July 1, 2011

Solution to Prisoner's Hat Puzzle




For the sake of explanation let's label the prisoners in line order A B and C. Thus B can see A (and A's 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").


Solution for the difficult form -:
In the case where every player has to make a guess, but they are free to choose when to guess, there is a strategy that allows every player to guess correctly. Each player should act as follows:
Count the numbers b of black hats and w of white hats.
Wait min(b,w) seconds.
If nobody has yet spoken, guess that your hat is black if you can see fewer black hats than white hats, or white if you can see fewer white hats than black hats.
If you have not yet spoken, guess that your hat is of the opposite colour to that of one of the first people to speak.
Suppose that in total there are B black hats and W white hats. There are three cases.
If B = W then those players wearing black hats see B−1 black hats and B white hats, so wait B−1 seconds then correctly guess that they are wearing a black hat. Similarly, those players wearing a white hat will wait W−1 seconds before guessing correctly that they are wearing a white hat. So all players make a correct guess at the same time.
If B < W then those wearing a black hat will see B−1 black hats and W white hats, whilst those wearing a white hat will see B black hats and W−1 white hats. Since B−1 < B ≤ W−1, those players wearing a black hat will be the first to speak, guessing correctly that their hat is black. The other players then guess correctly that their hat is white.
The case where W < B is similar.

No comments:

Post a Comment