Why is a raven like a writing-desk?

[big_bad_al]

I recently learned about The Hat Puzzle, which is a surprisingly tough little conundrum that goes like this: N people walk into a room and a hat is placed on each person's head. Each hat is either red or blue, and the chances that any given hat is red are 1 in 2. Each person can see the colours of everyone else's hat, but not the colour of their

Comments

[dhalps]

The Hamming codes are [2^r-1, 2^r-1-r, 3] binary linear codes. Let (n = 2^r-1) be the number of people (hats) -- this is also the length of the codewords. Let (k=2^r-1-r) be the number of codewords (error-free messages in the Hamming code). It is a property of Hamming codes that they are perfect -- e.g. every point is either a codeword, or within [floor((3-1)/2) = 1] Hamming distance of a codeword.

The short explanation is that because the Hamming codes are perfect, all of the 2^n assignments of hats are either a codeword or within 1 flipped hat of a codeword. If you assign everyone a bit in the word, the algorithm is "if what I see could be a codeword, I set my bit so that it's not a codeword". Else, I pass. The only case where everyone passes is if you're on a codeword, with probability 2^k/2^n which ends up being 2^(-r) e.g. 1/(n+1).

[big_bad_al]

Ooh, nice idea! So, if the bits of the whole group represent a valid Hamming code, everyone guesses wrong together. Otherwise, everyone passes except the one person who could bit-flip themselves into a Hamming code, who guesses correctly. and since there are n non-Hamming numbers for every valid Hamming number (since there are n ways to be off by 1 of the n bits), the chances of success are n out of n+1.

That's very clever. Thanks for explaining!