Hamming Hats

So, I hope everybody is ready for the solution to the hat problem from last time. Its a pretty good one, and combines a bunch of ideas I have set forward in previous puzzles.

First, one would like to solve a few cases with small N. The N=1 case is trivial, of course, you can't get better than 1/2 chance of success. Sadly, the two person case is similar, you cannot do anything better than 1/2 again. In the three person case however, we can do better with the following strategy:

For each person, guess black if both hats you see are white, guess white if both hats you see are black, and pass otherwise.

So, if the hats are white, white, black, then the black hat guy will guess correctly and the other two will pass. If the hats are white, white, white, then everybody will guess black and be wrong.

This is good, because we know that in a puzzle where one person being right is sufficient, then we don't want two people to be right at the same time. Also, in a puzzle where one person being wrong makes it all fail, we know that we should try to make it that everybody is wrong at the same time. Our solution will work unless everybody has the same hat colour, so the chance of success is 3/4.

So, in the case of general N now. We want that in any given situation, one person will guess correctly, or everybody will guess and be wrong. I honestly can't remember the logic I followed to get to the solution in the general case, but here is the solution in the N=7 case:

Treat a distribution of hats as a binary sequence of 7 digits, call it X. Each person knows all the bits except their own. Construct the Hamming set S of binary sequences of length 7. Each person is to look at the hats around, and if it is possible (based on the one missing bit) that X is an element of S, then make a guess assuming that X is not an element of S. If it is not possible X is an element of S, then pass.

If you have forgotten about Hamming codes, take a look at the sam and ray solution. So, since each string of length N is within one bitflip of an element of S, then unless X is an element of S, exactly one person will guess and they will be correct. If X is an element of S then everybody will guess and be wrong. The probability of failure is 2⁴/2⁷ which is 1/8.

If you have 10 people, say, then you just split 7 of them off and have them use that solution, have the other 3 always pass. In general with N people, split off M people so that they construct the largest Hamming set you can (it will be when M+1 is a power of 2) and have the remaining N-M people pass. The M people have a 1/(M+1) chance of failure, which will go to zero as M goes to infinity (and M goes to infinity as N goes to infinity, just taking a different path).