Wrong guesses that arrive together

Seven players are led into a room and a hat is put on each head, red or blue, by the toss of a fair coin. Each player can see the other six hats but not their own. No one may speak or signal once the hats are on. At a given moment all seven, at once and independently, either write down a guess at the colour of their own hat or write “pass”. The team wins if at least one player guesses and nobody guesses wrong. They may agree a strategy beforehand.

Every player’s own hat is an independent coin toss, and nothing the player sees says anything about it. So any guess a player makes is right with probability exactly one half. The obvious plan is to let one player guess and the others pass, and it wins half the time. It is hard to believe that anything can do better, since every guess is a coin toss and the team needs a correct one. Yet a strategy built from the Hamming code wins seven times in eight.

Guesses that are coin tosses, and a team that is not #

The resolution is that the team’s chance is not a product of the players’ chances. Whether a particular player is right is a coin toss, but which players guess, and when, depends on what they see, and what they see is the other hats. The strategy correlates the guesses. It cannot make any single guess better than a coin, but it can arrange that when guesses are wrong, they are wrong together, all on the same few configurations, and when they are right, one right guess is enough.

The puzzle was posed by Todd Ebert in his doctoral thesis in 1998 and became widely known after a newspaper article in 2001. Its full answer, for every number of players, was given by Hendrik Lenstra and Gadiel Seroussi, and it turns a puzzle about guessing into a question about covering the cube with balls, which is the question every code before it here has been asking from the other side.

Three players first #

Three players show the whole mechanism. The rule is that a player who sees two hats of the same colour guesses the other colour, and a player who sees two different colours passes. Draw the eight configurations as the corners of a cube, as in the picture of distance that started these codes, with one coordinate for each player’s hat.

If all three hats are red, every player sees two reds, guesses blue, and is wrong. The same happens if all three are blue. Those are the two lost corners. In each of the other six corners two hats match and one differs. The player with the odd hat sees two matching hats, guesses the colour that is not theirs — the odd one, which is theirs — and is right. The other two each see two different hats and pass. So the team wins in six configurations of eight, three times in four.

The figure confirms that nothing does better by trying everything. A player has four possible views — the two hats they see — and three possible answers to each, so 81 strategies, and the team has $81^3 = 531{,}441$ joint strategies. Every one was evaluated on all eight configurations. The best win six of eight, and exactly four strategies reach six: the rule above and its three relatives, one for each pair of opposite corners of the cube that the team agrees to lose on.

Right and wrong guesses balance #

The reason three in four is the ceiling for three players, and the reason seven in eight is possible for seven, is a counting identity that holds for every strategy.

Take one player and one view — a particular colouring of the hats that player can see. Exactly two configurations show that view: the one where the player’s own hat is red and the one where it is blue. If the player’s strategy says to guess on that view, the guess is right in one of the two and wrong in the other. Summing over all players and all views, across all $2^n$ configurations the total number of right guesses equals the total number of wrong guesses, whatever the strategy.

That identity is a budget. A strategy cannot reduce the wrong guesses; it can only decide where they fall. A configuration with even one wrong guess is lost, so the best use of the wrong guesses is to concentrate them, as many as possible on each lost configuration. A configuration can hold at most $n$ wrong guesses, one per player. A won configuration needs only one right guess. If a strategy loses on $L$ configurations and wins on $W$, then the wrong guesses number at most $nL$ and the right ones at least $W$, and they are equal, so $W \le nL$. With $W + L = 2^n$ this gives a winning chance of at most $n/(n + 1)$.

For three players that is $3/4$, which the cube rule reaches. For seven it is $7/8$. The figure shows the Hamming strategy reaching it exactly: on each of the 16 lost configurations all seven players guess and all are wrong, 112 wrong guesses, and on each of the 112 won configurations exactly one player guesses and is right, 112 right guesses. No guess is wasted. The same balance holds for a strategy chosen at random for four players, which makes 24 right guesses and 24 wrong ones; it simply spends them badly.

The strategy is a code #

To reach the bound, every lost configuration must have all $n$ players guessing wrong, and every won configuration must have exactly one guessing right. Read on the cube, that says: the lost configurations are a set of corners, and every other corner is at distance one — one hat away — from exactly one of them.

That is the definition of a perfect code of radius one. The Hamming code of length 7 is one: 16 codewords, each with a ball of eight words around it, $16 \times 8 = 128$ — sixteen spheres that fill the cube with no overlaps and no gaps. The strategy uses it directly. Each player looks at the six hats they can see and asks whether one of the two possible colours of their own hat would make the whole configuration a codeword. If so, they guess the other colour. If neither would, they pass.

When the configuration is a codeword, every player finds that their actual colour completes a codeword, so every player guesses the other colour, and all seven are wrong. When the configuration is not a codeword, it lies at distance one from exactly one codeword; the player whose hat differs from that codeword sees that the other colour would complete it, guesses their actual colour, and is right; every other player finds that neither colour completes a codeword, because two codewords are always at least three hats apart, and passes.

The players do not need a table of 16 codewords. The check is the one in finding the error without reading the message: number the players 1 to 7, and add up in binary, without carries, the numbers of the players wearing blue. A configuration is a codeword exactly when that sum is zero. Each player computes the sum over the hats they can see and checks whether it is zero, in which case wearing red would make a codeword, or equal to their own number, in which case wearing blue would.

Losses that cover the cube #

When the number of players is not of the form $2^m - 1$, no perfect code exists and the bound $n/(n + 1)$ cannot be reached. The exact best chance comes from a second look at the argument.

Suppose a strategy wins on some configuration. Then some player guesses right there. That player’s view is the same in the configuration with their hat flipped, so they make the same guess there and are wrong; that neighbouring configuration is lost. So every won configuration is at distance one from a lost one, which means the lost configurations form a covering code: every corner of the cube is within distance one of a lost corner. Conversely, any covering code can be made the losing set of a strategy, by the same rule as before — guess against completing a member of the covering set when only one colour would complete one.

The best chance is therefore $1 - K(n, 1)/2^n$, where $K(n, 1)$ is the fewest corners of the $n$-cube whose radius-one balls cover it, called the covering number.

The figure computes $K(n, 1)$ by search for $n$ up to 7 — 1, 2, 2, 4, 7, 12, 16 — and quotes 32 and 62 for eight and nine players. The bound is met at 1, 3 and 7, and nowhere else in the range. The next player count where it can be met is 15, with the Hamming code of length 15, which has 2,048 codewords covering the 32,768 configurations perfectly, and the team wins 15 times in 16.

Between the perfect lengths the best chance stalls. Four players do no better than three, at $3/4$, because $K(4, 1) = 4$ and $4/16$ is the same loss as $2/8$. Eight players do no better than seven, at $7/8$, since $K(8, 1) = 32$, and they can reach it by having one of them always pass while the other seven play the Hamming game. A player more is not automatically worth anything; a player is worth something only when the extra dimension lets the losses cover more efficiently.

Covering against packing #

The usual question about codes is a packing question: how many words can be chosen so that the balls around them do not overlap? The best a code can be computed those maxima by exhaustive search and set them against the Hamming bound, which says the balls cannot hold more words than the cube has. The hat game asks the opposite question: how few words can be chosen so that their balls leave nothing out? The counting bound for that, $K(n, 1) \ge 2^n/(n + 1)$, is the same arithmetic read the other way, and it is the bound $n/(n+1)$ on the team’s chance in disguise.

A perfect code is a set that answers both questions at once, a packing that is also a covering. That is why it is rare. For binary words and balls of radius one, perfect codes exist only at lengths $2^m - 1$; for larger radii the only non-trivial perfect binary code is the Golay code of length 23, what remains when one position is deleted from the twenty-four-bit code built from an icosahedron, a classification completed by Tietäväinen and van Lint in the early 1970s. Away from those lengths, packings and coverings come apart, the best packing is smaller than the counting bound allows and the best covering larger, and the hat game inherits the gap.

Covering the cube with few words is also close to fixing a word with few distances, where a handful of landmark words were chosen so that the distances to them identify every word. A covering asks only that every word be near some chosen word; a landmark set asks that every word be told apart from every other by its distances. The second is harder to satisfy, and the two numbers grow at different rates.

Five players and seven losses #

Five players are the first case where the covering is visibly imperfect.

A lost configuration can absorb five wrong guesses and so protect itself and its five neighbours, six configurations in all. Thirty-two is not a multiple of six, so at least six losses are needed by counting, and in fact six do not suffice: the search, which repeatedly takes the first configuration not yet covered and tries each of the six ways to cover it, closes every branch with six losses. Seven are needed and seven are enough, and the best chance is $25/32$, about 0.781, against the bound of $5/6$.

The same search finds 12 for six players and 16 for seven. At seven, sixteen is forced by counting alone, because each ball holds eight configurations and the 128 must all be covered, and the Hamming code meets it exactly. Above seven the search grows quickly and the values for eight and nine players were found by others, by more elaborate methods.

Playing it #

Simulated play shows what the averages mean. Over ten thousand rounds the Hamming strategy wins 0.8734 of them, a single guesser 0.5077, and a team in which everyone guesses red only when all seven happen to be red, 0.0068 against an expected $1/128$. Within each round under the Hamming strategy, a player who guesses is right exactly half the time. What the code changes is the pattern: the right guesses arrive one at a time, in seven rounds out of eight, and the wrong ones arrive seven at a time, in the eighth.

A code used backwards #

In its usual work a code protects a message: the sender picks a codeword, the channel flips a bit, and the receiver finds the nearest codeword. Here nobody sends anything. The configuration is random and the codewords are the configurations the team gives up on. The perfection that made the Hamming code an efficient error-corrector — every word within one flip of exactly one codeword — is exactly what makes it an efficient loser: it gives up the fewest configurations possible, and loses each of them as badly as possible.

The connection to the hundred prisoners is close. There, each prisoner opening half the boxes at random finds their number with probability one half, and a hundred independent searches almost never all succeed; following the cycles of the permutation makes the successes and failures happen together, and the team survives about 31% of the time. In both puzzles nothing improves the individual odds. The strategy correlates the outcomes, so that the team’s success depends on a single structural fact — one long cycle, one codeword — rather than on a hundred or seven independent coins.

What the pictures cannot show #

Only deterministic strategies are counted, but a randomised strategy is a mixture of deterministic ones and cannot do better than the best of them, so nothing is lost. The exhaustive search over strategies stops at three players; four players already have $3^8 = 6{,}561$ strategies each and more than $10^{15}$ joint ones, and from there the covering argument replaces enumeration. The covering numbers for eight and nine players are quoted, not computed. And the game assumes hats are independent and fair; with biased or correlated hats the balance of right and wrong guesses fails, and the best strategies change.

What was computed and what was quoted #

Computed here: the outcome of the Hamming strategy on all 128 configurations of seven hats, with 112 won and every loss a codeword where all seven guess wrong; every one of the 531,441 joint strategies for three players, with the best winning 6 of 8 and exactly four reaching it, and the balance of right and wrong guesses checked for each; the balance for seven players, 112 and 112, and for a random four-player strategy, 24 and 24; the covering numbers $K(n, 1)$ for $n$ from 1 to 7 by branch-and-bound search, with a covering of 32 configurations by 7 and the failure of 6; and ten thousand simulated rounds for three strategies.

Quoted: the origin of the puzzle with Ebert; the covering-code characterisation of the optimum by Lenstra and Seroussi; the covering numbers 32 and 62 for eight and nine players.

Still open: covering the cube #

The best chance in the hat game is known exactly only as far as the covering numbers $K(n, 1)$ are known, and the covering numbers of the binary cube are known only for small lengths; from ten players on, only bounds are available. Lower bounds come from counting and from refinements of it that account for how balls must overlap when they cannot tile; upper bounds come from explicit constructions found by computer. The gap is small in relative terms but has resisted closing, and every value would settle a version of the hat game outright.

The game also has many open variants. With more than two hat colours, perfect codes are rarer and the best strategies are known in fewer cases. If players speak in turn rather than at once, the problem becomes a different one, solved by parity. And if each player sees only some of the others, arranged on a graph, the best chance depends on the graph in ways that are understood only for special families.

Guesses that cannot improve, and a team that can #

Every guess in the hat game is a coin toss, and across all configurations right and wrong guesses balance exactly, so the only freedom a team has is where its wrong guesses fall. Piling them onto as few configurations as possible means choosing those configurations as a covering code of the cube, and the team wins with probability $1 - K(n, 1)/2^n$. For seven players the Hamming code is a perfect covering, the bound $n/(n + 1)$ is met, and the team wins 112 of the 128 configurations; three players win 6 of 8, as every one of 531,441 strategies confirms, and five players, needing seven losses where counting asks for six, win 25 of 32.