Can You Solve The Prisoner Hat Riddle?
“I use game theory to help myself understand conflict situations and opportunities. —— thomas schelling“
This is an awesome classic puzzle presented by the awesome “TED-Ed” .
So it goes out like this:
“If people were lined up from tallest to shortest (meaning a person can see everything in front of them) and all wearing black or white hats, can you figure out which color hat you were wearing even if you had no idea how many black or white hats there were total? Well, of course you can, but you got to use your brain a little.”
Let’s talk about the puzzle itself and it’s mechanics and variations.
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.
*induction puzzle, 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 case, and then repeating the reasoning that: “as soon as one of the participants realizes that the obvious case has not happened, they can eliminate it from their reasoning, so creating a new obvious case”.
*logic puzzle, is a puzzle deriving from the mathematics field of deduction.
*Game Theory, is “the study of mathematical models of conflict and cooperation between intelligent rational decision-makers.” Game theory is mainly used in economics, political science, and psychology, as well as logic, computer science, biology and poker.
Ten-Hat Variant without Hearing
Countably Infinite-Hat Variant without Hearing
Countably Infinite Hat Problem with Hearing
Is the Ten-Hat Variant
In this variant there are 10 prisoners and 10 hats. Each prisoner is assigned a random hat, either red or blue (or black and white), 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?
Short: 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.
Long: Please watch the video for the full explanation.