This is a problem of collective discipline under a severe restriction: one word per person and almost no second chances. Its beauty appears when the prisoners stop trying to save themselves individually and begin to act as a single system.
The hundred prisoners with hats
Riddle statement
One hundred prisoners stand in a line. Each is given either a red or a blue hat at random.
Each prisoner can see every hat in front of them, but not their own hat or any hat behind them. Starting with the prisoner at the back of the line and moving forward, each person must say exactly one word aloud: “red” or “blue.” Nothing else may be said.
A prisoner survives if the word matches the color of their own hat; otherwise, they die.
Beforehand, the prisoners may agree on a strategy.
What is the best possible strategy, and how many prisoners can it guarantee will survive?
Show solution
Solution
Answer: the prisoners can guarantee that 99 survive, and this is the best possible guarantee.
Beforehand, they agree to use the words “red” and “blue” as a parity code.
The prisoner at the back of the line—the first to speak—counts the red hats visible ahead:
- they say “red” if the number is odd;
- they say “blue” if the number is even.
This prisoner is not trying to save themselves. Since they cannot see their own hat, they use their answer to communicate one bit of global information to everyone else.
Each subsequent prisoner knows:
- the parity announced at the start;
- the hats still visible ahead;
- the colors already deduced and spoken by the prisoners behind them.
By comparing those pieces of information, each prisoner can determine the color of their own hat with certainty. Their answer then supplies the information needed for the process to continue.
Thus the 99 prisoners who speak after the first are guaranteed to be correct.
Why can no strategy guarantee that all 100 survive?
Fix the 99 hats visible to the first speaker. Now consider two arrangements that are identical except for that prisoner’s own hat: it is red in one arrangement and blue in the other.
The first prisoner sees exactly the same thing in both arrangements, so any strategy must make them give the same answer in both. That answer must be wrong in one of the two arrangements.
Therefore, the first prisoner cannot be guaranteed to survive.
Conclusion: 99 survivors is the largest possible guarantee.