Overview
A row of prisoners can save almost everyone using nothing but one shared convention and the parity of what they see — a striking use of a single bit of public information.
How to solve The Prisoners' Hats
- Agree that the back prisoner announces the parity of red hats they can see.
- Each prisoner ahead tracks the guesses already made and the hats still visible.
- By comparing the announced parity with what they see and hear, each deduces their own colour.
The key insight
One bit — the parity of all hidden hats — is enough for everyone downstream to solve for their unknown, because each guess reveals another hat and updates the parity.
Variations & echoes
- With infinitely many prisoners the puzzle connects to deep results using the axiom of choice.
- Parity/checksum tricks recur in error-correcting codes.
Frequently asked questions
How many are guaranteed to survive?
Everyone except possibly the first speaker — so n−1 of n, with the first having a 50% chance.