Another Take on the 7-Hats problem

Consider the problem described here.

Let 0 denote Red and 1 denote Blue. Fix an order among the n players. So the different ways to put hats is all possible n-bit strings, each occurring with equal
probability. Any assignment is an n-bit string.

The players could decide the following strategy. They split all n-bit strings into two disjoint sets S and S' (S'=complement of S). They try to split it in a certain way so that they are able to correctly guess (which means at least one guesses correctly and others pass) when the assignment is in S'. Then their probability of success will be |S'|/|S|+|S'|.

Property of S,S': Let the actual assignment be s. They want, if s is in S, someone to be able to guess correctly and no one wrongly. One way to ensure this is if for all s in S', there is some i in 1...n (at least one bit position), such that flipping the i-th bit of s gives a string in S. The players will decide in advance a suitable S and S' satisfying this property.

Then then need to decide a strategy based on S and S'. Here is a simple one. Each person i can see (n-1) bits. He considers the two possible n-bit assignments, s₀ using 0 in the i-th bit and s₁ with 1 in the i-th bit. These are the cases,

• s₀ is in S and s₁ is in S': Guess 1 as his bit. If s is in S', guess is correct.
• s₀ is in S' and s₁ is in S: Guess 0 as his bit. If s is in S', guess is correct.
• Both s₀,s₁ are in S: So, the actual string s must also be in S. He can just say pass.
• Both s₀,s₁ are in S': So, the actual string s is in S'. He can say pass. By the property above, there is some j such that s is obtained from S by flipping bit j. Then person-j will guess correctly.
  

By the strategy above, they win if the string s is in S'. The tricky part is to find the correct S and S' satisfying the property above. They can be found using various algorithms e.g. using brute force or greedy approach. For example when n=3, one possiblity is S={000,001,010,011} and S'={100,101,110,111} (so the success probability is 1/2).

It turns out the above property is satisfied by error detecting codes detecting 1-bit error. All the non-codewords in a 1-bit error detecting code are obtained by flipping 1-bit of some codeword; so S is the set of codewords. Any such error detecting code with k codewords will give a strategy with error probability k/2^n. The probability can be maximized by finding a error detecting code with the smallest set of codewords. The (7,4)-Hamming code is one such example with 16 codewords; so using its codewords as S gives a strategy with error probability 16/128=1/8.

Note that, the game does not allow the players to collaborate once the game starts, which means they are not allowed to pass hints to others by choosing which order to make their guess or listening to others before making guess. If colloboration is allowed, the error can be made very small 2/2^n.