We conclude this chapter with a puzzle whose answer may surprise you.

We consider a game show with a team of three contestants; call them players 1, 2,  3 in some order. (Alphabetically, maybe.) The contestants can meet before the show in order to discuss strategies. But then they are taken to separate dressingrooms,  and each is given a hat. They cannot see the hats that they are allocated; the player only knows that the hat is either red or black. For any given player, there is an equal chance that red or black will be allocated—for example, a coin is tossed for each player, out of the player’s sight; heads means red, tails means black.

The players then go onto a stage; they are too far apart to communicate, but each player can see the colors of the teammates’ hats. Then the players vote simultaneously. (A “vote” consists of the statement “my hat is black” or the statement “my hat is red.”) There is no way for any of them even to give a hint to their partners about the hat colors.

The players do not have to vote; at their turn they can pass instead. But the requirement is that at least one player must vote correctly, and no player can vote incorrectly. so, in order to win, every player must either pass or get his or her own hat color correct.

Obviously, the players will talk before the game, and try to come up with a strategy. After all, if all three players vote, and each would be correct about half the time, there would be only one chance in eight of winning the prize. One obvious plan is to appoint a spokesman, who will say “my hat is red,” while the others pass.

This has a 50% chance of being correct. But can they do better?

Yes, they can! The players work on the assumption that not all the hats are the same color. Each player looks at her two partners. If their hat colors are both red,  hers is black; if both black, hers is red; if they are different, she must pass. For example, if the colors are red, black, red in the order of the players, then both 1 and 3 see two different colors, so they pass. Two sees both red, so votes “black.” The players win.

Consider the eight possibilities.

• BBB All three vote R. They lose.

• RBB 1 votes R; others pass. They win.

• BRB 2 votes R; others pass. They win.

• BBR 3 votes R; others pass. They win.

• BRR 1 votes B; others pass. They win.

• RBR 2 votes B; others pass. They win.

• RRB 3 votes B; others pass. They win.

• RRR All three vote B. They lose.

So they win in six of the eight cases, or 75%.

To understand what we have done here, suppose we represent red hats by 1 and black hats by 0. The actual hat configuration is represented by a binary string of length 3. Think of them as possible codewords in a particularly simple binary code with only two messages, 1 and 0. To encode a message, simply send the message three times. If you receive 110 in this code, you know that there has been either one error (the intended transmission was 111) or two (it should have been 000). In nearest-neighbor decoding, you would assume there was only one error, so it was intended to send 111 and the message was 1.

Now suppose you are told that a codeword was sent incorrectly, but you can only see two of the characters. If those two characters are different, you cannot tell what was the third character sent, but if two were the same then the third must have been different from them.

We turn this coding problem into a game for three players as follows. A threesymbol binary string is transmitted at random; the strings are equally likely. Each player sees two of the symbols (a different pair for each player), but cannot see the third. They are asked if they know the missing symbol. They can either identify it or pass; the players win if at least one identifies the symbol correctly and none identify it incorrectly.

This code game corresponds to the hat game. A player receiving a red hat in the hat game is the same as if that player cannot see a 1 in the code game. The players work on the assumption that the string was not a codeword. If the string transmitted was actually a codeword, all three players would think they knew the missing symbol but would be wrong. If there was a transmission error, one player would give a correct answer while the other two would pass. So the players would lose if the string was a codeword and win if it was not. Since only two of the eight possible strings are codewords, they would win in 75% of cases.

We can generalize the hat game to seven players by using the Hamming code.

Again, a red hat corresponds to a 1 in the code and a black hat to an R. The players are ordered, and each player can see the other hats and construct a seven-digit string with one digit missing—the one corresponding to the player’s own hat. She then asks, “what would the missing symbol be if this is not a codeword?” It can be shown that, if the string is not a codeword, exactly one player can answer this question; the others will pass, and the team will win. If the original string was a codeword, all the player will make a wrong answer. Since there are 16 possible codewords and 27 = 128 possible strings, the probability of winning this game is 7/8.