Thank you for visiting this site. This article covers a masterpiece of the logic puzzle canon: “the hat puzzle.”
One hundred prisoners are lined up single file, and a red or blue hat is placed on each head. Each prisoner can see only the hats of those ahead in line — not their own, not those behind. Starting from the back of the line, each must declare their own hat’s color: right means release, wrong means execution. Given one strategy meeting beforehand, how many can be saved with certainty? Intuition says half at best. The correct answer is 99 — and the only tool required is the single word “even or odd.”
What Is the Hat Puzzle?
The hat puzzle (this version is the prisoners-and-hats puzzle) is the umbrella name for logic puzzles where you deduce information about yourself — which you cannot see — from what others can see and say. The rules of the 100-person version:
- 100 people stand in a line; each receives a red or blue hat. Any mix is possible (all red included)
- Each sees all the hats ahead of them; not their own, not those behind
- From the back of the line forward, each declares exactly one word, “red” or “blue.” Everyone hears every declaration
- Before the hats go on, the 100 may confer on a strategy
Try the naive plans first. With no coordination, each person guesses at 1/2, so only 50 survive in expectation. The next idea: “each person announces the color of the hat in front of them.” That guarantees the 50 even-positioned people — but the 50 announcers are saying words unrelated to their own hats, so they’re back to luck. Certainty: 50. That is about where intuition tops out.
The Answer: Compress Everything into the First Word
The winning strategy: the prisoner at the very back, who speaks first, declares “red” if the number of red hats among the 99 he sees is even, “blue” if it is odd. That one convention is the entire strategy meeting.
Stand in the second prisoner’s shoes. She sees the 98 hats ahead. Suppose the first call was “red” — that is, “the reds among the 99 ahead of me are even in number.” If the reds she counts among her 98 are odd, then to make the parity work out, her own hat must be red. If even, she is blue. She answers with certainty.
The third and beyond work the same. Each person cross-checks three things — the parity declared first, the reds declared since, and the reds visible ahead — and their own color is uniquely determined. Since everyone ahead of you in the speaking order answers correctly, every declaration you hear is a true color. Prisoners 2 through 100 — all 99 — are saved by logic alone, guaranteed.
Only the first speaker is at risk; his call is a signal unrelated to his own hat, so his survival odds stay at 1/2. The strategy thus saves 99 for certain, 99.5 in expectation. And this is provably the theoretical ceiling: not one bit of information about the first prisoner’s own hat ever reaches him, so no strategy can guarantee all 100.
The Lineage of Induction Puzzles, from Three Wise Men On
The hat puzzle has long been the flagship of the family called “induction puzzles,” whose famous prototype is the tale of the three wise men.
A king has three wise men close their eyes and tells them: “I have placed on each of you one of three red hats and two white hats.” In fact, all three are red. Eyes open, each sees the others’ hats but not his own. Told “whoever knows his own color, speak,” a silence stretches — until the wisest declares, correctly: “I am red.”
His reasoning: if I were white, the other two would each be seeing “one red, one white.” In that case, the one wearing red would think: “only two whites exist — if I were white too, the third man would have spoken instantly. He hasn’t, so I am red” — and would have answered. The silence of the others was itself the proof that I am not white. This craft of squeezing information from other people’s failure to speak passes straight down to the blue-eyed islanders puzzle.
Then, at the end of the 20th century, the hat puzzle underwent a dramatic evolution. In 1998, the computer scientist Todd Ebert published the “hat game” in his doctoral thesis; it became a craze that spilled far beyond mathematics, and by 2001 the New York Times was running a feature on it.
Ebert’s Hat Game and Error-Correcting Codes
Ebert’s rules look simple. Three players receive red or blue hats by coin flip. Everyone sees the others’ hats; no one sees their own. No communication; at a signal, all simultaneously declare “red,” “blue,” or “pass.” The team wins if at least one player names their color correctly and no one names wrongly. All-pass loses.
Have one player guess and the rest pass: 50%. That looks like the ceiling — but the winning strategy achieves 75%. The rule: “if the other two look the same color, declare the opposite; if they differ, pass.”
Of the 8 hat combinations, all three match in only 2. In those, all three players declare wrongly and the team loses. But in the other 6, exactly one player — the one wearing the minority color — speaks, and speaks correctly. The strategy’s essence: each individual’s accuracy stays pinned at 1/2, but the errors are herded into the 2 all-wrong-together cases while the successes are spread thinly across 6. Lose loudly and rarely; win quietly, on a single voice, often. That skew lifts the team to 75%.
Astonishingly, the generalization of this strategy turns out to be precisely the theory of Hamming codes — error-correcting codes. With 7 players, the win rate rises to 87.5%, and the optimal strategy is mathematically identical to the design of codes that self-repair corrupted transmission data. The discovery that a parlor puzzle stood on the same ground as cutting-edge coding theory is what made the problem famous.
Parity Is Working All Around You
The “even or odd” key to the 100-person version is called parity in information science — and it quietly holds up daily life.
Credit card numbers carry a check digit to catch typos; book ISBNs and national ID numbers do the same. RAID storage keeps one disk’s worth of parity computed across the others, so that if any single disk dies outright, its contents can be rebuilt from the rest. Exactly the principle of the signal the lead prisoner called out.
Two ideas are worth carrying home. First: “most of the information everyone needs has already been distributed.” The 100 prisoners need 100 facts, but 99 of them are already in each person’s field of view — the missing piece was a single bit, the total’s parity. In a team rich in shared context, what needs communicating is not everything but the delta. Second, Ebert’s game shows that individual performance and team performance are different quantities. Without raising anyone’s personal odds a millimeter, you can raise the team’s odds purely by designing how failures coincide — the same thinking as choosing whether to spread or deliberately concentrate risk in a portfolio.
More Colors? Simultaneous Declarations?
Does the Strategy Break with Three or More Colors?
No. Instead of parity, number the colors 0, 1, 2 and have the leader declare the sum of visible numbers modulo 3 — and the identical logic lets everyone downstream compute their color. Only the leader remains at risk, same as before. With k colors, work modulo k; the two-color parity trick is just the special case. That is the beauty of it.
What If Everyone Declares Simultaneously?
Without sequential declarations, no one can use the previous answers, and the 99-person guarantee becomes impossible. But there are delightful variants. With two people declaring simultaneously after seeing each other’s hats, agree that “one says the color they see, the other says the color they don’t see” — and for any configuration, exactly one of the two is always right. With n colors and n people, a similar division of modular labor guarantees at least one correct answer, always. You cannot aim for everyone right — but “at least one right” can be engineered.
Any Lessons for Real Team Play?
The power of agreeing on the meaning of a signal in advance. The prisoners cannot confer during the event, yet one small convention synchronized 100 people completely. In incident response, disaster planning — any situation where communication is restricted during the real thing — the value of small protocols agreed in peacetime multiplies. Often, designing conventions that convey much with little beats adding more channels.
Related Logic Puzzles and Paradoxes
See the ultimate form of reasoning from others’ silence, “the blue-eyed islanders”; neutralizing lies through question design in “the guards of heaven and hell”; and induction leading somewhere unexpected in “the unexpected hanging paradox.”
Summary
This article covered the logic puzzle masterpiece “the hat puzzle.”
What divided the fates of 100 people was neither telepathy nor elaborate cryptography but a single-bit convention: are the red hats even or odd? Nearly all the needed information was already distributed across everyone’s sightlines; the lead prisoner filled in only the one missing piece. And that same principle — as card-number error detection and RAID recovery — is protecting your data at this very moment.
Perhaps information is never missing — merely unaggregated. Whenever I wrestle with a team’s information sharing, this puzzle comes back to me.
To return to the full list of logic and probability puzzles, follow the link below.
Thank you for reading. We hope to see you in the next article.
📚 Series: Logic & Probability Puzzles (3/11)
