Prisoners and hats puzzle
From Wikipedia, the free encyclopedia
| This article may not meet the general notability guideline or one of the following specific guidelines for inclusion on Wikipedia: Biographies, Books, Companies, Fiction, Music, Neologisms, Numbers, Web content, or several proposals for new guidelines. If you are familiar with the subject matter, please expand or rewrite the article to establish its notability. The best way to address this concern is to reference published, third-party sources about the subject. If notability cannot be established, the article is more likely to be considered for redirection, merge or ultimately deletion, per Wikipedia:Guide to deletion. This article has been tagged since February 2008. |
 |
This article does not cite any references or sources. (February 2008) Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed. |
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. There are many variations, but the central theme remains the same. Not to be confused with the similar Hat Puzzle.
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) and other 3 variants are available on this Logic Puzzles page (they are called Masters of Logic I-IV).
[edit] Ten-Hat Variant
 |
The tone or style of this article or section may not be appropriate for Wikipedia. Specific concerns may be found on the talk page. See Wikipedia's guide to writing better articles for suggestions.(June 2008) |
In this variant there are 10 prisoners and 10 hats. Each prisoner is assigned a random hat, either red or blue, but the number of each color hat is not known to the prisoners. The prisoners will be lined up single file where each can see the hats in front of him but not behind. Starting with the prisoner in the back of the line and moving forward, they must each, in turn, say only one word which must be "red" or "blue". If the word matches their hat color they are released, if not, they are killed on the spot. A friendly guard warns them of this test one hour beforehand and tells them that they can formulate a plan where by following the stated rules, 9 of the 10 prisoners will definitely survive, and 1 has a 50/50 chance of survival. What is the plan to achieve the goal?
[edit] Ten-Hat Solution
The prisoners can use a binary code where each blue hat = 0 and each red hat = 1. The prisoner in the back of the line adds up all the values and if the sum is even he says "blue" (blue being =0 and therefore even) and if the sum is odd he says "red". This prisoner has a 50/50 chance of having the hat color that he said, but each subsequent prisoner can calculate his own color by adding up the hats in front (and behind after hearing the answers [excluding the prisoner in the back]) and comparing it to the initial answer given by the prisoner in the back of the line. The total number of red hats has to be an even or odd number matching the initial even or odd answer given by the prisoner in back.
[edit] Countably Infinite-Hat Variant
In this variant, a countably infinite number of prisoners, each with an unknown and randomly assigned red or blue hat line up single file line. Each prisoner faces away from the beginning of the line, and each prisoner can see all the hats in front of him, and none of the hats behind. Starting from the beginning of the line, each prisoner must correctly identify the color of his hat or he is killed on the spot. As before, the prisoners have a chance to meet beforehand, but unlike before, once in line, no prisoner can hear what the other prisoners say. The question is, is there a way to ensure that only finitely many prisoners are killed (and hence, an infinite number are saved)?
[edit] Countably Infinite-Hat Solution
If one accepts the axiom of choice, the answer is yes. In fact, even if we allow an uncountable number of different colors for the hats, the axiom of choice provides a solution that guarantees that only finitely many prisoners must die. The solution for the two color case is as follows, and the solution for the uncountably infinite color case is essentially the same:
The prisoners standing in line form a sequence of 0's and 1's, where 0 is taken to represent blue, and 1 is taken to represent red. Before they are put into the line, the prisoners define the following equivalence relation over all possible sequences that they might be put into: Two sequences are equivalent if they are identical after a finite number of entries. From this equivalence relation, the prisoners get a collection of equivalence classes. Using the axiom of choice, they select and memorize a representative sequence from each equivalence class.
When they are put into their line, each prisoner can see what equivalence class the actual sequence of hats belongs to. They then proceed guessing their hat color as if they were in the representative sequence from the appropriate equivalence class. Since the actual sequence and the representative sequence are in the same equivalence class, their entries are the same after finitely many prisoners. The prisoners up to this finite point have a 1/2 chance of being killed. All prisoners after this point will be saved.
[edit] Infinite-Hat variation
The number of hats (prisoners) can be infinite provided a prior code is made by the prisoners using the same allowed word. (The rules state: one word, taken as using the same word, and not being taken as using a single word.) That is, the same one (correct) word may be repeated more than once.
With this prior collusion the prisoners can go free. E.g. if there were 20 prisoners inline with 20 various blue and red hats. The 20th, last in line, without any considered or prior information, would be at risk. However, by calling the hat colour of the 19th prisoner (in front of him) he has a 50/50 chance of going free; and guarantees the 19th prisoner can go free.
The 19th now calls (correctly) his own hat colour (as informed by number 20) and; if prisoner 18 (in front of number 19) has the same colour hat, the correct colour 19 calls will also confirmed the same colour to prisoner 18.
However, if prisoner 18 has the other colour hat, prisoner 19 repeats his own correct hat colour twice. As previously agreed between the prisoners, this repeat, of the same correct colour word, informs prisoner 18 that his hat colour is actually the opposite colour to that called by prisoner 19. Simply: the repeat of the same, correct colour word informs the next prisoner in line that his hat is of the other colour. That is, a repeat (of the correct colour) toggles that colour, for the prisoner in front. i.e. red=red. red,red,=blue.
This toggle can be used by all the prisoners each in turn, who will both correctly call their own colour every time; either once or twice, and so doing, will also directly inform the prisoner in front of the colour they have to correctly call. Enabling in this instance, at least 19 prisoners to go free, and possibly all 20.
If using the one (correct) word more than once is not allowed, the solution can be varied by different use of the toggle for one word. Just the one word could be said, e.g. either loudly or softly. i.e. If the hat in front is the same colour, the correct colour is called softly; and, if the hat in front is of the other colour, the correct colour could called loudly.
