Brain Teasers
The Line of Hats
The hundred-prisoner hat line as a story: one word each, and a parity code that saves 99.
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, not just 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.