Prisoners in a Line Guessing Hat Colours

$n$ prisoners stand in a single-file line, each facing forward, each wearing a black or white hat assigned however the warden likes. Each prisoner can see the hats of everyone in front of them but not their own or anyone behind. Starting from the back, each prisoner in turn must announce a guess of their own hat colour — everyone in the line hears every guess. Any prisoner who guesses correctly is freed. The prisoners get to agree on a strategy beforehand, but not after they see the hats. What strategy saves the most people, and how many are guaranteed?

The answer: all but the very back prisoner are guaranteed to survive, no matter how the hats are assigned — using nothing but one bit of sacrifice from the first speaker.

The core idea: the first answer is a message, not a guess

The back prisoner sees every other hat but has no way to know their own colour — they're stuck with a 50/50 guess. But that 50/50 guess is the only piece of information that gets broadcast to everyone still guessing, so the group's strategy should spend it as efficiently as possible rather than wasting it on an honest guess of a colour nobody but the speaker needs. With two colours, one bit is exactly enough to convey one fact to the rest of the line — the trick is choosing which fact.

Working the strategy

Agree beforehand: the back-most prisoner counts the number of black hats they see among everyone in front of them, and announces "black" if that count is odd, "white" if it's even. This sentence itself is very likely wrong as a guess of their own hat — but that's fine, they were never going to be able to guess correctly anyway. What matters is that everyone in front has now heard the parity of black hats among the $n-1$ people ahead of the back prisoner.

The next prisoner (second from back) can see everyone in front of them — one fewer person than the back prisoner saw. They combine two pieces of information: the parity just announced (covering all $n-1$ hats ahead of the back prisoner, which includes this prisoner's own hat) and the count of black hats they can personally see among the remaining $n-2$ people ahead of them. If those two counts disagree in parity, their own hat must be black; if they agree, it must be white — because their own hat is exactly the difference between the two counts. They announce their own colour correctly, and in doing so, also update the running parity that later prisoners can use, since everyone can hear and recompute from the sequence of announcements and hat colours revealed so far.

Every subsequent prisoner repeats this: they know the parity of all hats behind (and including) their own position from the original announcement plus every correct answer given since, and they can see every hat still in front of them, so their own hat colour is forced by parity — always solvable exactly, never a guess.

What this means in practice

This is a small, exact model of how a single broadcast signal can carry enough structure for everyone downstream to extract their own precise information from it — the same logic behind how a compressed settlement price, an index level, or a single reference rate lets many market participants each back out something specific to their own position without needing every underlying data point. Interviewers use this puzzle to see whether a candidate treats "what should the first move communicate" as a design question, rather than just solving each prisoner's guess independently.