100 Prisoners Hat Puzzle - The Parity Strategy That Saves 99

The setup

A hundred prisoners stand in a line, each seeing only the hats in front of them - black or white, assigned by coin flip. From the back forward, each must call out a colour; a wrong call about their own hat is fatal. They may agree a strategy the night before. How many can be saved?

Short answer: Ninety-nine guaranteed, plus a coin flip for the first speaker: the person at the back announces the PARITY of the black hats they see.

One bit, spent perfectly

The prisoner at the back cannot know their own hat - their guess is genuinely a coin flip. But their one word can carry one bit of information to everyone else. The pact: say 'black' if the number of black hats you see is odd, 'white' if it is even.

The next prisoner counts the black hats ahead of THEM. If that count's parity matches what the back announced, their own hat must be white; if it differs, black. They answer with certainty - and in doing so, update the running parity for everyone remaining. Each subsequent prisoner tracks the announced parity, every answer heard so far, and the hats still visible, and deduces their own colour exactly.

Why you cannot do better

The first speaker sees nothing that correlates with their own hat, which was an independent coin flip - no strategy gives them better than 50%. So 99-and-a-coin-flip is optimal, and the parity code achieves it with the simplest possible encoding.

The structure generalises: with k colours, announcing the sum of visible hats mod k saves everyone but the first speaker. It is error-free communication over a channel exactly one symbol wide - a checksum, agreed the night before.

Why interviews ask it

This is an information-theory question wearing a story: the interviewer wants you to notice the strategy space is 'what can one public word encode', reach for parity, and prove optimality by pointing at the first speaker's independence.