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.

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; that each prisoner is wearing one of the hats; and that each of the prisoners only see the hats in front of him but not on himself or behind him. The fourth man behind the screen can't see or be seen by any other prisoner. No communication between the prisoners is allowed.

If any prisoner can figure out and say to the jailer what color hat he has on his head 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, regardless of how the jailer distributes the hats.

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 A's hat color) and C can see A and B. The prisoners know that there are only two hats of each color. So if C observes that A and B have hats of the same color, C would deduce that his own hat is the opposite colour. However, if A and B have hats of different colors, 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 color. 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").

Variants

Four-Hat Variant

In a variant of this puzzle, the prisoners know that there are 3 hats of one color 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.)

The solution
There are two cases: in the trivial case, one of the three prisoners wears the single off-color hat. Each of the other two prisoners can see that one prisoner is wearing the off-color hat. In the non-trivial case, the three prisoners wear hats of the same color, while D wears the off-color hat. After a while, all three prisoners should be able to deduce that, because neither of the others was able to state the color of his own hat, D must wear the off-color hat.

Five-Hat Variant

In another variant, 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. The first prisoner that is able to announce the color 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
Assume 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 wears a white hat, C will be unable to tell the color of his hat (because there is a black and a white). So B can quickly deduce from A's black hat and C's lack of response that he (B) is wearing a white hat. So if A wears a black hat there will be a fairly quick response from B or C. Assume that A wears a white hat: C cannot see two black hats, so he is unable to tell his hat color. B sees only a white hat, so he can't tell anything about his hat. In this case A, B and C would remain silent for some time, until A finally deduces that he must have a white hat because C and B have remained silent for some time.

Three-Hat Variant

Ten-Hat Variant

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?

The solution
The prisoners agree that if the first prisoner sees an odd number of red hats, he will say "red". This way, the nine other prisoners will know their own hat color after the prisoner behind them responds.

Ten-Hat Variant without Hearing

As before, 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 are distributed in the room such that they can see the hats of the others but not their own. Now, they must each, simultaneously, say only one word which must be "red" or "blue". If the word matches their hat color they are released, and if enough prisoners resume their liberty they can rescue the others. 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, 5 of the 10 prisoners will definitely be released, so that they are able to rescue the others. What is the plan to achieve the goal?

The solution
The prisoners pair off. In a pair (A,B) of the prisoners A says the color he can see on the head of B, who says the opposite color he sees on the head of A. Then, if both wear hats with the same color, A is released (and B is not), if the colors are different, B is released (and A is not). In total, 5 prisoners answer correctly and 5 do not. Alternatively, the prisoners build two groups of 5. One group assumes that the number of red hats is even, the other assumes that there is an odd number of red hats. Similar to the variant with hearing, they can deduce their hat color out of this assumption. Exactly one group will be right, so 5 prisoners answer correctly and 5 do not. Note that the prisoners cannot find a strategy guaranteeing the release of more than 5 prisoners. Indeed, for a single prisoner, there are as many distributions of hat colors where he says the correct answer than there are where he does not. Hence, there are as many distributions of hat colors where 6 or more prisoners say the correct answer than there are where 4 or less do so.

Countably Infinite-Hat Variant without Hearing

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?

The 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 and an uncountable number of prisoners, 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 0s and 1s, 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. Because the actual sequence and the representative sequence are in the same equivalence class, their entries are the same after finitely many prisoners. All prisoners after this point are saved. Because the prisoners have no information about the color of their own hat and would make the same guess whichever color it has, each prisoner has a 50% chance of being killed. It may seem paradoxical that an infinite number of prisoners each have an even chance of being killed and yet it is certain that only a finite number are killed. However, there is no contradiction here, because this finite number can be arbitrarily large and no probability can be assigned to any particular number being killed. This is easiest to see for the case of zero prisoners being killed. This happens if and only if the actual sequence is one of the selected representative sequences. If the sequences of 0s and 1s are viewed as binary representations of a real number between 0 and 1, the representative sequences form a non-measurable set. (This set is similar to a Vitali set, the only difference being that equivalence classes are formed with respect to numbers with finite binary representations rather than all rational numbers.) Hence no probability can be assigned to the event of zero prisoners being killed. The argument is similar for other finite numbers of prisoners being killed, corresponding to a finite number of variations of each representative. A simpler, but perhaps less optimal, solution is to agree that everyone says "red" if they see two or more red hats in front of them. This way, all the red-hatted prisoners, except the last, will survive. If they see zero or one red hat in front of them, they say "blue", and all the blues survive. However this doesn't satisfy the original terms of the problem as all of the blue or red hats (an infinite number) will die.

Countably Infinite Hat Problem with Hearing

This variant is the same as the last one except that prisoners can hear the colors called out by other prisoners. The question is, what is the optimal strategy for the prisoners such that the fewest of them die in the worst case?

The solution
It turns out that, if one allows the prisoners to hear the colors called out by the other prisoners, it is possible to guarantee the life of every prisoner except the first, who dies with a 50% probability. To do this, we define the same equivalence relation as above and again select a representative sequence from each equivalence class. Now, we label every sequence in each class with either a 0 or a 1. First, we label the representative sequence with a 0. Then, we label any sequence which differs from the representative sequence in an even number of places with a 0, and any sequence which differs from the representative sequence in an odd number of places with a 1. In this manner, we have labeled every possible infinite sequence with a 0 or a 1 with the important property that any two sequences which differ by only one digit have opposite labels. Now, when the warden asks the first person to say a color, or in our new interpretation, a 0 or a 1, he simply calls out the label of the sequence he sees. Given this information, everyone after him can determine exactly what his own hat color is. The second person sees all but the first digit of the sequence that the first person sees. Thus, as far as he knows, there are two possible sequences the first person could have been labeling: one starting with a 0, and one starting with a 1. Because of our labeling scheme, these two sequences would receive opposite labels, so based on what the first person says, the second person can determine which of the two possible strings the first person saw, and thus he can determine his own hat color. Similarly, every later person in the line knows every digit of the sequence except the one corresponding to his own hat color. He knows those before him because they were called out, and those after him because he can see them. With this information, he can use the label called out by the first person to determine his own hat color. Thus, everyone except the first person always guesses correctly.