I've been reading about how hamming codes are used to 'solve' the [Hat Problem](http://en.wikipedia.org/wiki/Hat_puzzle), and I understand how it 'assigns' one person to be the speaker, and how that speaker knows the answer. Everything I read says that it worked $1-\frac1{2^n}$ times, but what I don't understand is why it fails where it does. Apparently there's one case where every person guesses wrong, but I can't figure out which case that is, or (more importantly) why. Anyone care to explain?



Hat Problem/Hamming Codes
So I looked at Loepp and Wootters and it does seem to answer your question. Here's roughly how the argument goes.


**Strategy** During the strategy session prior to the game the players agree on some binary [$n,n-r$] Hamming code *C* and a check matrix *H* for *C*. The players also number themselves 1 through *n*. The agree on the convention that 0 represents blue and 1 represents red and the convention that the vector $\bar{v}\in \mathbb{Z}^{n}\_{2}$ represents the correct description of the way the hats are distributed. So, for example, suppose $n=3$ and the distribution is that the first two people have red and the third has blue. In this case $\bar{v}=(110)$. After the game begins the $i$th person will knows all of the entries of $\bar{v}$ $except$ for the $i$th entry. This person then forms two possible vectors for $\bar{v}$, e.g. $\bar{v}\_{0}$ if that person has on a blue hat and $\bar{v}\_{1}$ if that person has on a red hat. The $i$th person then does the following:


If $H\bar{v}^{T}\_{0} \ne \bar{0}$ and $H\bar{v}^{T}\_{1} \ne \bar{0}$ he/she passes.


If $H\bar{v}^{T}\_{0} = \bar{0}$ and $H\bar{v}^{T}\_{1} \ne \bar{0}$ he/she guesses red.


If $H\bar{v}^{T}\_{0} \ne \bar{0}$ and $H\bar{v}^{T}\_{1} = \bar{0}$ he/she guesses blue.


The case where $H\bar{v}^{T}\_{0} = \bar{0}$ and $H\bar{v}^{T}\_{1} = \bar{0}$ never occurs.


[Note: $\bar{v}^{T}$ is the transpose of $\bar{v}$.]


**Winning and losing** If they use this strategy the team wins whenever $H\bar{v}^{T}\ne 0$ and they lose whenever $H\bar{v}^{T} = 0$. The probability that the team will win turns out to be $\frac{n}{n+1}$.


