Published 13 September 2026

100 prisoners and hats

One hundred people stand in a line wearing black or white hats. Each sees the hats ahead, but neither their own nor those behind. They speak from the back toward the front, each saying exactly one color as their guess. Everyone hears every earlier answer. They may agree on a strategy beforehand, but cannot gesture, change the timing to signal information, or use extra words.

At first it seems that everyone must guess. In fact, one person can use their answer to communicate a single bit that makes the remaining ninety-nine answers certain. The useful message is not an inventory of the hats. It is the parity of a count.

Inspect one person’s information

Black means one and white means zero. Number people in speaking order, so person one is at the back. Their word is black if they see an odd number of black hats and white if they see an even number. This is a statement about everyone ahead, not a claim based on seeing their own hat.

Select a later speaker and inspect their visible hats and heard words before revealing the actual assignment. The full grid is an omniscient view for checking the calculation; those actual hats are not extra information available to the speaker.

Why the second person knows

Suppose the first word is black: the total number of black hats among people two through one hundred is odd. Person two counts the black hats ahead. If that count is even, their own hat must be black; if it is odd, their own hat must be white. Their spoken answer is therefore correct, and everyone later can treat it as a known hat color.

Person three removes person two’s established color from the announced parity, then compares the remaining parity with the hats they can see. The same argument continues by induction. At every turn after the first, exactly one unknown hat remains in the parity equation.

In bit notation, the first answer is the exclusive-or of hats two onward. A later answer is that first bit, exclusive-or all established answers from person two up to the previous speaker, exclusive-or all visible hats ahead. Applying exclusive-or twice to the same bit cancels it. Only the current person’s bit survives.

For a four-person example with hats black, white, black, white, the visible black count for person one is one. They say black. Person two sees one black, so says white; person three sees zero black after removing person two’s white, so says black. Person four removes the already established black and says white. Here all four happen to be correct. Flipping only the first hat changes no spoken word and makes only that first answer wrong.

A guarantee and a probability are different claims

Every assignment gives at least ninety-nine correct answers. No randomness assumption is needed for this guarantee. If hats are independently fair, the first person’s own hat is independent of the parity they announce, so their probability of being correct is one half. The total correct count is then either ninety-nine or one hundred, with equal probability; its expectation is 99.5.

It would be wrong to multiply one hundred independent guessing probabilities. The later answers are certain under the agreed protocol. Conversely, no permitted strategy can guarantee all one hundred: the first speaker receives identical information in two assignments differing only in their own hat, so must give the same answer to both.

The Carnegie Mellon puzzle solution, problem one, describes this line-and-parity protocol. Changing who can see whom or allowing more colors creates a different information problem. Continue to entropy to connect the one-bit message with information, or Kruskal count for a different mechanism by which initially separate paths become predictable.