Hat-Colour Problems

Ten people stand in a line, each wearing a black or white hat. Everyone can see every hat in front of them but not their own, and not the hats behind them. Starting from the back, each person must call out "black" or "white" — nothing else — loud enough for everyone to hear. Anyone who names their own hat colour correctly survives; anyone who doesn't, doesn't. They can agree on a strategy beforehand but cannot communicate once the hats go on. What is the best strategy, and how many people can you guarantee to save?

Try it with three or four people before reading on. Most people's first guess is "half of them, since it's a coin flip" — the real answer is far better, and the reason why is the whole point of the puzzle.

The trap: treating each guess as an isolated coin flip

If everyone just guesses their own hat colour at random, each person is right with probability 1/2, independent of everyone else. On average you save half the room. That's the naive answer, and it's a huge underestimate, because it throws away the one resource the group actually has: the first person to speak can see everybody else's hat.

The insight is that the first speaker doesn't have to try to save themselves. They can sacrifice their own certainty to broadcast one bit of information that lets everyone behind them deduce their own hat colour with certainty.

Worked example: ten people, saving nine for sure

Number the people 1 (back, sees everyone) through 10 (front, sees no one). Agree beforehand: person 1 will count the black hats among people 2 through 10. If that count is odd, they say "black"; if even, they say "white." Person 1 has now announced the parity of black hats in front of them — sacrificing their own 50/50 chance, since their word choice carries no information about their own hat.

Now person 2 hears person 1's parity announcement and can see people 3 through 10. They compute what the parity of hats 2 through 10 should be, compare it to person 1's declared parity of hats 2 through 10, and the difference tells them their own hat colour exactly. Say person 1 declared "odd number of black hats among 2–10." Person 2 looks at hats 3–10 and counts, say, 3 black hats there. For the total (2 through 10) to be odd, hat 2 must be even-contributing, i.e. white would keep it at 3 (odd) — so person 2 deduces their hat is white and says so, correctly.

Every subsequent person repeats the trick: they've heard all previous correct answers (which they can verify are consistent, since everyone but person 1 answers with certainty), they can see everyone ahead of them, and they still know the original parity person 1 announced. Each person recomputes their own hat colour from the running parity and calls it correctly.

Result: person 1 is right only half the time (they were guessing, not deducing), but persons 2 through 10 — nine people — are right with certainty, every single time. Compare that to the "everyone guesses independently" strategy, which saves an expected 5 out of 10 with huge variance. Parity coding saves 9 guaranteed, 100% of the time.

Why it works: one bit, spent well

The deep reason this succeeds is that "black or white" is a genuine bit of information, and the group agreed in advance on a code for using it — parity — rather than letting the first speaker waste it on a private guess. Each subsequent person effectively receives a running update: "given what you already know plus what's been said, here is the one missing fact." That's not luck; it's an algorithm. The information was always available (everyone can see almost every hat) — the only scarce resource was a channel to communicate it, and parity of a count is a maximally efficient way to pack "one bit that resolves an ambiguity" into a single word.

The transferable technique

Whenever a puzzle gives a group a single narrow communication channel — one word, one bit, one number mod $k$ — ask what invariant of the unseen information that channel could encode. Parity of a count is the workhorse because it's cheap to compute, cheap to verify, and exactly one bit. The same move reappears in prisoner-line hat puzzles with more colours, in coin-flip signalling puzzles, and in any interview question that starts "a group can agree on a strategy beforehand but not communicate afterward" — that phrase is always inviting you to find the code.