100 Prisoners and Hats: Puzzle and Step-by-Step Solution
Logic & Strategy
Hard
Reported at Jane Street, Hudson River Trading, Citadel, Two Sigma
The puzzle
One hundred prisoners stand in a line, each able to see only the hats in front of them. Each hat is black or white, assigned by coin flip. Starting from the back, each prisoner must call out a colour; anyone wrong about their own hat is executed. Everyone hears every call. They may agree a strategy the night before. How many can be guaranteed to survive?
Short answer: Ninety-nine are guaranteed, and the first speaker survives with probability 1/2: the person at the back announces the parity of the black hats they can see.
Step 1: One word, one bit
The prisoner at the back sees 99 hats but not their own, which was an independent coin flip. Nothing they see tells them anything about it, so their guess is a coin flip whatever the strategy. But their one word is heard by everyone, and it can carry one bit of information.
The pact: the back prisoner says 'black' if the number of black hats they see is odd, and 'white' if it is even.
Step 2: How the second prisoner deduces their hat
The second prisoner counts the black hats in front of them. If that count has the same parity as the one announced, their own hat cannot be black, because a black hat would have changed the parity the back prisoner saw. So it is white. If the parity differs, their hat is black. They answer correctly with certainty.
Every later prisoner does the same bookkeeping: start with the announced parity, flip it for each 'black' they have heard called by the prisoners behind them (those calls are now all correct), and compare with the black hats they see in front. The difference is their own hat. All 99 are saved.
Step 3: Why you cannot do better
The first speaker's hat is independent of everything they can observe, so no strategy gives them better than a 50% chance. Saving 99 with certainty and the first with probability 1/2 is therefore optimal, and the parity code achieves it.
A useful way to see it: the 99 visible hats determine one bit, the parity, and that single bit is exactly enough for everyone else, because each later prisoner is missing exactly one bit, their own hat.
Step 4: Generalisations interviewers ask next
With k colours, number them 0 to k - 1 and have the back prisoner announce the sum of the visible hats modulo k. Each later prisoner subtracts what they see and what they have heard and reads off their own colour. Everyone but the first speaker is saved again.
This is a checksum, agreed in advance, sent over a channel exactly one symbol wide. Recognising the coding-theory structure is what the question is really about.
Why interviewers ask it
Frame the strategy space as 'what can one public word encode', reach for parity, and prove optimality by pointing at the first speaker's independence.
Knowing the proof is half of it. Work 100 Prisoners and Hats interactively, then take it under a clock with the rest of the Outcry simulators.