Prisoners and hats puzzle
Encyclopedia
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
.
ers 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 prisoners is allowed.
Then, prisoner C (see image) either calls out the color of his hat, or says he doesn't know. After this, prisoner B either calls out the color of his hat, or says he doesn't know. Similar for prisoner A. If any of the three prisoners can figure out what colour hat he has on his head all four prisoners go free. The puzzle is to find how the prisoners can escape.
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").
In the non-trivial case, the three prisoners wear hats of the same colour, while D wears the off-colour hat.
After a while, all four prisoners should be able to deduce that, since none of the others was able to state the colour of his own hat, D must wear the off-colour hat.
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 colour 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?
This therefore proves that A must not be wearing a black hat.
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).
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 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. All prisoners after this point are saved.
Since 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, since 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 0's and 1's 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.
Induction puzzles
Induction Puzzles are logic puzzles which are solved via the application of the principle of induction. In most cases, the puzzle's scenario will involve several participants with reasoning capability and the solution to the puzzle will be based on identifying what would happen in an obvious...
(a kind of logic puzzle
Logic puzzle
A logic puzzle is a puzzle deriving from the mathematics field of deduction.-History:The logic puzzle was first produced by Charles Lutwidge Dodgson, who is better known under his pen name Lewis Carroll, the author of Alice's Adventures in Wonderland...
) that involves reasoning about the actions of other people, drawing in aspects of Game theory
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...
. There are many variations, but the central theme remains the same. Not to be confused with the similar Hat Puzzle
Hat Puzzle
Hat puzzles are logic problems that date back to 1961 if not earlier.A number of players, at least 3, are each wearing a hat, which may be of various specified colours. Players can see the colours of at least some other players' hats, but not that of their own. With highly restricted...
.
The puzzle
According to the story, four prisonPrison
A prison is a place in which people are physically confined and, usually, deprived of a range of personal freedoms. Imprisonment or incarceration is a legal penalty that may be imposed by the state for the commission of a crime...
ers are arrested for a crime
Crime
Crime is the breach of rules or laws for which some governing authority can ultimately prescribe a conviction...
, 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.
Then, prisoner C (see image) either calls out the color of his hat, or says he doesn't know. After this, prisoner B either calls out the color of his hat, or says he doesn't know. Similar for prisoner A. If any of the three prisoners can figure out what colour hat he has on his head all four prisoners go free. The puzzle is to find how the prisoners can escape.
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 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
Communication
Communication is the activity of conveying meaningful information. Communication requires a sender, a message, and an intended recipient, although the receiver need not be present or aware of the sender's intent to communicate at the time of communication; thus communication can occur across vast...
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").
Four-Hat 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)The solution
There are two cases: in the trivial case, one of the three prisoners wears the single off-colour hat, and thus the other two can easily deduce the colour of theirs.In the non-trivial case, the three prisoners wear hats of the same colour, while D wears the off-colour hat.
After a while, all four prisoners should be able to deduce that, since none of the others was able to state the colour of his own hat, D must wear the off-colour 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 colour 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
Assuming 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 does not wear a black hat, C will be unable to tell the colour of his hat (since there is a black and a white). Hence, B can deduce from A's black hat and C's response that he (B) is not wearing a black hat (otherwise the above situation will happen) and is therefore wearing a white hat.
This therefore proves that A must not be wearing a black hat.
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 cue, 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
Coding theory
Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...
.
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).
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?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.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?Countably Infinite-Hat Solution
If one accepts the axiom of choice, the answer is yes. In fact, even if we allow an uncountableUncountable set
In mathematics, an uncountable set is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal number is larger than that of the set of all natural numbers.-Characterizations:There...
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 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
Equivalence relation
In mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...
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. All prisoners after this point are saved.
Since 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, since 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
If and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
the actual sequence is one of the selected representative sequences. If the sequences of 0's and 1's are viewed as binary representations of a real number between 0 and 1, the representative sequences form a non-measurable set
Non-measurable set
In mathematics, a non-measurable set is a set whose structure is so complicated that it cannot be assigned any meaningful measure. Such sets are constructed to shed light on the notions of length, area and volume in formal set theory....
. (This set is similar to a Vitali set
Vitali set
In mathematics, a Vitali set is an elementary example of a set of real numbers that is not Lebesgue measurable, found by . The Vitali theorem is the existence theorem that there are such sets. There are uncountably many Vitali sets, and their existence is proven on the assumption of the axiom of...
, 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.