Prisoners and hats puzzle

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

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.

Prisoners and hats.PNG

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.

Variants[edit]

Four-Hat Variant[edit]

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.)

Five-Hat Variant[edit]

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?

Three-Hat Variant[edit]

See also: Hat puzzle

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.

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[edit]

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 Variant without Hearing[edit]

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?

Countably Infinite-Hat Variant without Hearing[edit]

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 Problem with Hearing[edit]

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?

See also[edit]