One hundred hats in a line.
The hundred hats puzzle: prisoners in a line each see only the hats in front of them and must call out their own colour. The obvious strategy saves 50. One bit of shared information saves 99, and the argument for why 100 is impossible is as instructive as the trick.
One hundred prisoners stand in a single file line, all facing forward. A guard places a hat on each head, red or blue, chosen however the guard likes. Each prisoner can see every hat in front of them and none behind, including their own. Starting from the back of the line, each prisoner in turn must call out a single word, "red" or "blue". A prisoner who names their own hat colour is freed; a wrong answer means they stay. Everyone hears every call, but nobody is told whether a call was right.
The prisoners may agree on a strategy the night before, and then no further communication is allowed beyond the calls themselves.
What is the largest number of prisoners who can be guaranteed to go free, no matter how the guard assigns the hats?
A first attempt is to pair the prisoners up: the person at the back of each pair calls the colour of the hat directly in front, sacrificing their own guess so that the person in front is certain. That guarantees 50. It is far from the best possible, and the reason is that each call is being used to carry one prisoner's colour when it could carry a fact about all of them.
Stuck? Open hints one at a time
Each hint gives away one more layer. Stop the moment something clicks.
Hint 1 a nudge
The prisoner at the very back sees 99 hats and has no information about their own. Whatever they say is a coin flip for them. But their word is heard by everyone, so it can encode one fact about the 99 hats they see. Which single fact would let every later prisoner work out their own colour?
Hint 2 the key move
Let the back prisoner say "red" if the number of red hats they see is even and "blue" if it is odd. The next prisoner sees 98 hats and knows the parity of 99. The difference is their own hat.
Hint 3 the finishing idea
Each later prisoner must track the parity as it changes: every "red" called by someone behind them was a correct call (after the first) and so is a red hat that must be subtracted from the running count. Nobody after the first needs to guess.
The solution
Reveal the full solution
Ninety-nine prisoners can be guaranteed freedom, and no strategy can guarantee one hundred.
The strategy uses a single bit. The prisoner at the back counts the red hats among the 99 in front and calls "red" if that count is even, "blue" if it is odd. This call is a guess about their own hat and has a one in two chance of being right, but it is also an announcement everyone else can use. Prisoner 99 now counts the red hats among the 98 in front. If that count has the same parity as the announced total, their own hat is not red, so they call "blue". If the parity differs, their hat is red. Prisoner 98 does the same, with one correction: they know prisoner 99's hat from the call just made, so they update the parity before comparing. Every prisoner from 99 down to 1 deduces their colour exactly, and the only uncertain call is the first.
Walk through a small case. Five prisoners, hats from back to front: blue, red, red, blue, red. The back prisoner sees red, red, blue, red, three reds, odd, so calls "blue". That happens to be correct. Prisoner 4 sees red, blue, red, two reds, even; the announced parity was odd, so prisoner 4 has a red hat and says "red". Prisoner 3 knows the parity of the four hats in front of prisoner 5 is odd and one of them, prisoner 4, is red, so the remaining three have even parity. Prisoner 3 sees blue, red, one red, odd; therefore prisoner 3 is red. The chain continues, and each call is a computation, not a guess.
The impossibility of 100 is a counting argument, not a failure of imagination. The back prisoner's call depends only on the 99 hats they see and the agreed strategy. Fix those 99 hats. The guard is free to choose the back prisoner's hat after the strategy is known, and can choose the colour that makes the call wrong. Since the call cannot depend on the hidden hat, at least one prisoner can always be made to fail. Ninety-nine is therefore optimal, and it is achieved by pushing all of the unavoidable uncertainty onto the one person who has no information anyway.
| Strategy | Guaranteed | Expected (random hats) | Information used per call |
|---|---|---|---|
| Everyone guesses | 0 | 50 | None |
| Pairs, back names front | 50 | 75 | One hat colour |
| Parity announcement | 99 | 99.5 | Parity of all hats ahead |
The pairs strategy wastes half the calls because each carries one bit about one hat. The parity strategy spends one call on one bit about all 99 hats, and that bit is exactly what each later person is missing. This is the same reason a checksum can be a single number: what a receiver lacks is not the whole message but the one fact that reconciles what they see with what was sent.
What this puzzle is really testing
Whether you can separate the information a message carries from the message's surface meaning. The word "red" from the back of the line is not a claim about a hat; it is a parity bit. The same idea appears in prefix XOR tricks, where a running exclusive-or over an array lets you recover any single missing element, and in the hundred prisoners and a light bulb puzzle, where one shared bit has to be reused across many visits. Interviewers who still ask puzzles, as discussed in are brain teasers still asked, tend to prefer this one because the solution has a clean generalisation and a clean impossibility proof.
Follow-ups to expect
Three hat colours, or k colours: assign the colours the numbers 0 to k minus 1, and the back prisoner announces the sum of the hats ahead modulo k. Each later prisoner subtracts what they see and what has been called, and recovers their own number. The guaranteed count stays at 99 for any k. A second follow-up removes the ability to hear earlier calls: then each prisoner has only the hats in front, the parity trick collapses, and the guaranteed number drops to zero, which shows that the strategy depends on the calls being public, not on the colours being few. A third asks whether it matters that nobody is told if a call was right. It does not; every call after the first is provably correct, so the feedback would carry no new information.