100 people stand in a line, one behind another, all facing forward. Each gets a black or a white hat. Everyone sees all the hats in front of them, but not their own and not those behind. Starting from the back, each says one word aloud: "black" or "white". Those who name the colour of their own hat win. They may agree on a strategy in advance. How many can be guaranteed to win?
It seems you cannot beat "half": the back person tips off the one in front, and so on in pairs. But the back person can say one word about everyone at once: whether the number of black hats they see is even or odd. After that, every next person knows their own colour for sure. Only the back person takes a risk, so 99 are guaranteed to win, and 99.5 on average.
A classic interview puzzle for programmers: William Poundstone includes it in his book on Google's interview puzzles (2012). Do not confuse it with the 100 prisoners and boxes: there people cannot pass anything to each other, while here everyone hears every word.
100 people stand one behind another, all facing forward. Number them from the back: person 1 stands behind everyone, person 100 at the front.
Each person gets a black or a white hat at random. Any combination is possible: all black, all white, anything in between.
Everyone sees every hat in front of them. Not their own, and not those behind. Person 1 sees 99 hats, person 100 sees none.
In turn, from person 1 to person 100, each says one word aloud: "black" or "white". Everyone hears everything. Those who name the colour of their own hat win.
The people agree on a strategy in advance. How many of them can be guaranteed to win, whatever hats they get?
"50: split into pairs, and the back one names the colour of the one in front"
Some say "0", since nobody sees their own hat. In fact 99 are guaranteed to win. Only person 1 takes a risk, with a 1/2 chance. The trick is that their word carries information not about one neighbour but about the whole line.
100 people, the best strategy, the worst hats. Lock in how many of them, in your view, are guaranteed to name their own colour.
A breakdown of your answer will appear here.
Hard to decide? Open the hints one at a time: the easy one first, then stronger ones.
Person 1's word is heard by all 99 people in front. It's a waste to spend it on a tip for just one neighbour.
Let person 1 say one word about the whole line at once: whether the number of black hats they see is even or odd.
Person 2 knows the parity person 1 saw and can see everyone in front. What is missing for them to know their own colour? And can anyone in the line know person 1's colour?
The hat-maker knows your strategy and hands out hats so that as few people as possible win. You can also dress the line yourself: click a hat to change its colour and press "Let them speak". Under each hat a small box shows the colour that person named.
–
Now the hats are random, with no evil hat-maker. Each line of 100 people is played in full: in turn, people hear, look and say a word. The bars show how often exactly that many people won, the thin line shows the exact distribution.
"Name the hat in front" and "at random" have the same distribution, so their bars overlap. The bars of the "even/odd" strategy are cut off: each of the two reaches about 50%.
Person 1's word looks useless: they do not know their own hat. But all 99 people in front hear it, and that is exactly what makes it so valuable.
The agreement: "black" from person 1 means "I see an odd number of black hats", "white" means even. Person 2 sees the same hats except their own. If their count has a different parity, the difference is their own hat, so it is black. After that, everyone adds to what they see the "blacks" already said by the people behind them, since all of those people named their own colour correctly.
Person 1 speaks first, so they hear nothing and see only other people's hats. Their word depends on those alone. A hat-maker who knows the strategy checks what they will say and gives them the other colour. So 100 cannot be guaranteed, and the best possible average is 99 + 1/2 = 99.5.
In the pair strategy, the back person of each pair spends their word on a neighbour, even though everyone hears it. Each such tip carries one bit about one person. The word "even or odd" is also one bit, but about the sum of all the hats at once. Everyone in front knows every term of that sum except one, and that is enough.
This is induction: person 2 surely knows their colour, so their word is true. Then person 3 knows everything about hats 2 and 4 to 100, and so on up to person 100, who sees no hats at all but knows their own.
In pairs the back one wins with chance 1/2 and the front one always: 50 · 1/2 + 50 = 75. At random everyone wins with chance 1/2: 100 · 1/2 = 50. With even/odd, 99 always win and person 1 wins with chance 1/2.
| ⊕ | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
a ⊕ b ⊕ b = a
white = 0, black = 1
Write white as 0 and black as 1. The parity of a sum equals the XOR of all digits: 1 ⊕ 1 = 0, since two ones make an even number. The key property: XOR cancels itself, b ⊕ b = 0. So you can "take out" the known hats from the XOR of all of them, and the unknown one remains: hj = s ⊕ (heard) ⊕ (seen).
The same works for k colours: number them 0, 1, …, k − 1 and take the sum modulo k, that is, the remainder after dividing by k. Person 1 names the colour whose number is "the sum of everyone they see, mod k". Again n − 1 are guaranteed to win.
Colours are numbered 0, …, k − 1, and hi is person i's colour. Person 1 sees hats 2…n and names the colour s, their sum modulo k.
Person j heard s and the correct colours of people 2…j − 1, and sees hats j + 1…n. Only their own is unknown.
Two colours: subtraction mod 2 is the same as addition, and the formula becomes a chain of XORs.
Result: everyone except person 1 is guaranteed to win, and person 1 wins with chance 1/k.
For 100 people and two colours, that is 99 guaranteed winners and 99.5 on average. No strategy can do better: person 1 knows nothing about their own hat whatever the plan.
Hats in a line open the door to three worlds. In mathematics they lead to modular arithmetic and Hamming codes. In logic they show how one check bit protects all the others. In practice the same XOR rebuilds a lost disk and catches a wrong digit in a card number.
Mathematics
Number the colours 0, 1, …, k − 1. Person 1 adds up the numbers of all the hats they see, takes the remainder after dividing by k and names the colour with that number. Each next person subtracts what they heard and saw, and the remainder gives the number of their own colour.
The guarantee is the same: n − 1. But person 1's chance drops to 1/k, so the average is n − 1 + 1/k. For 100 people and three colours that is 99⅓. Remainders mod k form a group: every number has an opposite, and that is why the known terms can be subtracted.
Each sees the two other hats. All at once, each says "black", "white" or "pass". The team wins if at least one guesses right and nobody guesses wrong. Choose one rule for all three.
It seems you cannot beat 1/2 here: each person guesses right with chance 1/2. But the rule "if I see two alike, I name the other colour, otherwise I pass" wins in 6 hat sets out of 8, a 3/4 chance. It loses only when all three hats match, and then all three are wrong together.
Each guess is right in one hat set and wrong in the neighbouring one where only that hat differs. So right and wrong guesses come in equal numbers. A win needs just one right guess, and one losing set can soak up as many as n wrong ones. Hence the bound: the chance is at most n/(n + 1). For n = 3 that is 3/4, and a full search over all 81³ = 531,441 combinations of rules confirms that nothing does better.
For n = 2m − 1 the bound is reached by the Hamming code, the same one as in the poisoned wine puzzle: 7 players win in 112 of 128 hat sets (7/8), 15 players in 30,720 of 32,768 (15/16). Each player checks whether the hats could form a codeword, and if so names the colour that breaks it.
Logic
10 people, the even/odd strategy. Click a person, and they will say the opposite of what they worked out. You can pick several.
Person 1's word says nothing about person 1. It is a check bit: the parity of all the other hats. If you know the sum and all the terms but one, that one can be recovered. The rest of the strategy is this thought applied 99 times.
A curious consequence: one slip does not bring the line down. If person j in the middle of the line names the wrong colour, person j + 1 is wrong too, but their wrong word cancels the first mistake, and everyone after is right again. One mistake costs exactly two people. Check it with a click.
Practice
One stripe of the array: bytes from data disks A, B, C and the parity byte P = A ⊕ B ⊕ C. In RAID 5 the parity of different stripes sits on different disks, but the arithmetic is the same. Choose the disk that "burns out".
The simplest data protection is a parity bit: one more bit is added to a group so that the number of ones becomes even. If one bit gets corrupted, the parity no longer matches and the error shows. This is how characters on serial links and memory in old computers were checked.
RAID 5 goes one step further. The failed disk is known: like the person in the line who knows it is their own hat that is unknown. Then parity does not just catch an error, it restores what was lost: B = A ⊕ C ⊕ P. The array survives the loss of any one disk while spending a single disk on protection, not a mirror copy of each.
The last digit of a bank card number is a check digit, like person 1's word. It is chosen so that a special sum of all the digits is divisible by 10. Going from right to left, every second digit is doubled, and if the result exceeds 9, subtract 9. For the standard example 79927398713 the sum is 70, so the number is valid.
It is a sum modulo 10, like the sum of colours modulo k. It catches any single wrong digit and almost any swap of two neighbouring digits. It misses only 09 ↔ 90. The IBM engineer Hans Peter Luhn patented the algorithm, and card numbers are still checked with it, in payment forms for example, before the bank is even contacted.
The game in which players guess at once and may pass was described by Todd Ebert in his PhD thesis (University of California, Santa Barbara, 1998). It spread when Ebert, by then teaching computer science at UC Irvine, offered his students extra credit for a seven-player version, the "seven prisoners puzzle".
On 10 April 2001 Sara Robinson wrote a New York Times article, "Why Mathematicians Now Care About Their Hat Color", about how Ebert's puzzle unexpectedly led to coding theory.
Hendrik Lenstra and Gadiel Seroussi, in the paper "On Hats and Other Covers" (IEEE ISIT, Lausanne, July 2002), linked the best strategies of the game to covering codes: sets from which any hat set can be reached by changing at most one hat.
Hans Peter Luhn of IBM filed for a "Computer for Verifying Numbers" in 1954 and received US patent 2,950,048 in 1960. The device checked numbers with the very algorithm used to check card numbers today.
David Patterson, Garth Gibson and Randy Katz at Berkeley published "A Case for Redundant Arrays of Inexpensive Disks (RAID)". It describes several RAID levels, including RAID 5, where the parity blocks are spread across all the disks.
If there are infinitely many people and each sees everyone in front, then with the axiom of choice there is a strategy under which only finitely many people are wrong. Gabay and O'Connor, graduate students at Cornell, found it in 2004. Christopher Hardin and Alan Taylor cover this and other strange versions in their book "The Mathematics of Coordinated Inference" (2013).
Share your own explanation, an objection or a variant of the puzzle. You need a GitHub account to comment.
I keep adding new puzzles, new ways to explain them and write-ups of the discussions they start. Leave your email and I'll write when something new is out. No spam, one-click unsubscribe.
The sign-up form will appear here soon.