tag removed - Hat Problem/Hamming Codes

Well, I wouldn't say there's just one case where they lose, but it depends on how you count cases. Remember, the idea is that the number of people is of the form $2^n - 1$. Accordingly, if we take a case to be an ordered assignment of colors, then there are $2^{2^n - 1}$ different cases. The fraction of these in which the prisoners is win is $(2^n - 1)/2^n$, but the denominator here isn't the number of cases, on this method of counting them; there's more than one case in which they lose.

Anyway, the way it works is that in a Hamming code, some cases (specifically, $2^{2^n - 1 - n}$ of them) are picked as "well-formed" such that for every case A, there is a unique well-formed case B such that the number of color changes between A and B is at most 1.

So, suppose the prisoners use the strategy "Consider both possible cases compatible with the information available to you. If one of them is well-formed (they won't both be), then guess in accordance with the other one. Otherwise, in the case where neither of them is well-formed, you should refrain from guessing". What will the outcome be?

What happens is that, in those cases which are well-formed, every prisoner guesses wrong, since every prisoner will take the first branch of the above strategy. On the other hand, in those cases which aren't well-formed, there is a unique prisoner who goes down the first branch and guesses correctly, while every other prisoner goes down the second branch and refrains.

Accordingly, the number of cases in which the prisoners lose is the number of well-formed cases; that is, $2^{2^n - 1 - n}$. So the fraction of cases in which the prisoners lose is $2^{2^n - 1 - n}/2^{2^n - 1} = 1/2^n$. Like I said, though, this isn't just one case (if we identify cases with ordered assignments of colors).

(Incidentally, if you'd like to know how to actually construct a Hamming code, you can take the well-formed cases to be those with the property that, for every $i$, there are an even number of black hats at positions whose $i$th bit is 1 (using position numbering starting at 1). It should be straightforward to verify that this has all the properties mentioned above)