Brain Teasers · The Line of Hats
100 Prisoners Hat Puzzle - The Parity Strategy
The hundred-prisoner hat line as a story: one word each, and a parity code that saves 99.
What is the hat-guessing puzzle?
Hat-guessing puzzles are a family of logic puzzles in which a group of people, each wearing a hat of some colour they cannot see, must deduce or communicate information about their own hat using only what they can see on others and a tightly limited channel of communication - often a single guess, spoken once, per person. They sit alongside puzzles like the muddy children problem and the hundred prisoners and a light bulb problem as classic exercises in reasoning about what limited, shared information can and cannot establish.
The version at the centre of this puzzle is a line of people, each seeing every hat in front of them but none behind, each allowed to say exactly one word - a guess at their own hat's colour - starting from the back of the line, with every earlier guess audible to everyone still waiting to speak. Agreeing on a strategy beforehand is allowed; communicating during the exercise is not, beyond the single permitted word.
The key idea is that one shared bit of information, chosen carefully, is worth far more than it looks. The very first speaker gives up his own guess to broadcast a parity - whether the number of, say, black hats he sees is even or odd - functioning exactly like a parity check bit in error-correcting codes. Every person after him can compare that announced parity against what they see and what they've heard guessed so far, and their own hat colour becomes logically forced.
This is why the strategy can guarantee all but one correct answer: the first speaker's own hat is, by construction, independent of anything he can observe, so no strategy can do better than sacrificing exactly one guess to purchase certainty for everyone else. The puzzle is a small exercise in information theory dressed as a logic puzzle - it asks how much a single shared signal can encode, and the parity trick is the answer.
How it works
A hundred prisoners stand in a line, each wearing a black or white hat assigned by coin flip. Each sees every hat in front, none behind, and their own least of all. From the back forward each must say exactly one word - 'black' or 'white' - heard by everyone; a correct call about your own hat means survival. They may agree a strategy the night before. The story asks for the best strategy and how many it guarantees. You lock in a guess, then step through the answer and breakdown.
How scoring works
No grading - your guess is displayed back beside the answer. The story teasers share one lifetime unlock for free users.
The key insight
The back prisoner cannot beat a coin flip, so his word is spent as a checksum: 'black' for an even count of black hats ahead, 'white' for odd (the game's telling). Every later prisoner compares the announced parity with the hats they see and the guesses they have heard, and their own colour is forced - 99 guaranteed, 99.5 expected, and provably optimal since the first speaker's hat is independent of everything he can observe.
The full step-by-step solution lives at /brain-teasers/hat-colours/solution.
A worked example
Prisoner 100 announces the parity of the 99 hats he sees. Prisoner 99 counts the black hats ahead: if his count's parity differs from the announcement, his own hat is black; if it matches, white. Each prisoner after that folds every heard guess into the running parity and deduces their own hat with certainty.
Common mistakes
• Guessing strategies that save about 50 - pairing people up wastes the fact that one public word informs everyone at once.
• Trying to save all 100; the back prisoner's hat is independent of his view, so 99 is the ceiling.
• Forgetting that later prisoners must track every guess heard, on top of the first announcement.
Why interviews test this
This is an information-theory question in costume: notice the strategy space is what one public word can encode, reach for parity, and prove optimality via the first speaker's independence. The written solution is at /brain-teasers/hat-colours/solution.
Play The Line of Hats on Outcry
The Line of Hats is free to play on Outcry, in the Brain Teasers section, and every run is timed and scored. Read the guide once, then play The Line of Hats and check your score against the strategy above. The guide book has a written guide for every other game, and the practice hub and mock assessments put the same skills under a real screen's clock.