The Line of Hats

The hundred-prisoner hat line as a story: one word each, and a parity code that saves 99.

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.

Why quant 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.

The The Line of Hats guide covers how scoring works, the strategy that wins, a worked example and the mistakes most players make.

More Brain Teasers games

• Screwy Pirates - Five rational pirates vote on how to split 100 gold coins, and you work out the split by backward induction from a one-pirate crew up.
• Tiger and Sheep - A hundred rational tigers and one sheep on a magic island, where any tiger that eats becomes a sheep itself - solved by induction on parity.
• The Split Deal - The prisoner's dilemma played as a story: two thieves, separate rooms, and one offer each.
• Stag or Hare - The stag hunt as a story: two equilibria, and a choice that comes down to trust.
• One Offer, No Discussion - The ultimatum game as a story: one split of 100 pounds, one accept-or-reject, no negotiation.
• The Growing Pot - The centipede game as a story: a pot that doubles on every pass, and logic that says take it immediately.
• All Brain Teasers practice
• Every game guide