Prisoners with Hats
To celebrate a special occasion, a prison offered to let some prisoners go free if they could pass a test.
The prison had a very large collection of small hats of two colors – say, black and white. On the day of the test, three prisoners were selected and lined up blindfolded facing toward the front of the line. A small colored hat was placed on each prisoner and then the blindfolds were removed. Each prisoner could see all the hats of the prisoners in front of them, but they could not see their own hat or any of the hats behind them.
During the test, the last prisoner in line says a hat color. If that was their hat color, they are set free. Otherwise, they go back to prison. Each prisoner can hear each answer behind them before they give their own answer. No hints to other prisoners were allowed in the tone or manner that each answer was given.
All these rules were made clear to the prisoners the day before the test, and they were allowed to strategize together.
THE CHALLENGE
Describe a strategy that guarantees the largest number of prisoners will go free.
EXPLORATION
How does your solution change if there are four or even five prisoners? Devise a strategy that works for any number of prisoners.
Notes
THE CHALLENGE
Your students will be tempted to come up with schemes that involve cheating by having the color spoken in some sort of unusual way that gives a clue to the other prisoners. This of course is not allowed. They may also be tempted to think if both hats in front of them are the same color, then their hat is likely to be the other color – it is important to point out that there is a very large supply of hats so that there will be no bias regarding running out of one type of hat.
The other thing they will be tempted to do is to rely on good luck. This puzzle specifically looks for guarantees of success and not ways of being lucky.
One common strategy suggestion is to have the first prisoner say the hat color of the person directly in front of them. Unfortunately, that strategy only guarantees that one person will go free.
The best strategy is for the first prisoner to do the following. They count the number of black hats in front of them. If the number of black hats is even, they say “Black,” and if it is odd, they say “White.” This strategy does not guarantee that the first prisoner will go free, but there is no way to guarantee that.
After the first prisoner’s turn, the second prisoner can figure out their hat. Suppose the first prisoner said “Black.” Then the second prisoner knows that their hat and the third prisoner’s hat are either both black or both white – by looking at the hat on the third prisoner, it is easy to know which case it is. Similarly, if the first prisoner says “white,” then the two remaining hats must be opposite colors.
Finally, the third prisoner has heard the previous two hat announcements. If the first one said “Black,” then the two hats must be the same color and their hat must be the same as the second person’s hat. If the first one said “White,” then the two hats must be different colors and their hat is the opposite of the second person’s hat.
This strategy two prisoners will go free. If they’re lucky, the third prisoner will go free as well.
EXPLORATION
For more than three prisoners, the strategy starts off exactly the same.way. Note that if the original strategy is put in terms of the hats being the same or different (instead of using even and odd), then the jump to more than three prisoners requires a major insight. The best way to explain how this will work is to have your students put on pretend hats and act out how they can figure out their hat color using ideas about even and odd numbers.
TEDEd has a lovely video for the prisoner hat riddle: