Ebert's Hat puzzle with [7,4] hamming code

Question

I've been researching Ebert's hat puzzle and I keep reading that the 7 person case can be optimized using the [7,4] Hamming code. Can someone explain to me how the players could use Hamming codes to maximize their chances of winning?

Answer 1

Here is one strategy. Number the players from 1 to 2^k-1 in binary (for instance with seven players we would have Anna = 001, Bethany = 010,..Fred =110, George = 111. Each player plays according to the following algorithm: Look at the players you can see who are wearing black hats. Xor their numbers together (add the digits mod 2, with no carry) to get a subtotal. If you do not see any black hats the subtotal is zero. Having computed the subtotal you should

• Guess black if the subtotal is zero.
• Guess white if the subtotal is YOUR number.
• PASS if the subtotal is anything else.

Basically we are betting that if we XOR together the numbers of ALL the players with black hats (call this the total) then we get something other than zero. Two things can happen. If the total is something other than zero then exactly one person guess correctly and the rest pass. If the total is zero then EVERY player guesses incorrectly. Exactly 1/2^k of the bit patterns total to zero in this way, so you lose with probability 1/2^k.

In terms of the Hamming code the strategy is as follows. Lets say black hats are 1 bits and white hats are zero bits, and assign each person a bit number in some way. For instance if Anna and Bethany have black hats and the rest of the players have white hats we have the hat word 0000011. We are betting that the hat word is NOT a code word for the Hamming (7,4) code. Your strategy is to look at the bit pattern of your friends. If the bit pattern you see is consistent with one of the (7,4) code words you guess that your hat is the color that would make the hat word NOT be a code word. If the bit pattern is not consistent with a (7,4) code word you pass. For instance

• If I see 100000? the I should pass, since neither 1000001 nor 1000000 are Hamming code words, so I know that whatever my hat color the hat word cannot be a code word.
• If I see 000000? then I should guess black (1) since 0000000 is a (7,4) code word but 0000001 is not.

This has the same property: if the hat word is a code word then every player guesses incorrectly. If the hat word is not a code word then EXACTLY one player guesses right and the rest pass. There are 16 (7,4) code words, and 2^7 = 128 hat words, so your odds of losing are 16/128 = 1/8.

This is really two slightly different descriptions of the same strategy since the Hamming code words are exactly those where, if you XOR the numbers of the set bits together you get zero.