Application: The hats problem

Students from a coding theory class meet in a classroom. To be specific, suppose that there are $7$ of them. Each are told to close their eyes and a white or black hat is placed on their head. The color of each hat is determined by a coin toss, with the outcome of one coin toss having no effect on the others. Each can see the other players' hats but not his own. No communication of any sort is allowed, except for an initial strategy session before the game begins. Once they have had a chance to look at the other hats, the players must simultaneously guess the color of their own hats or pass. The group shares a hypothetical $ 1 million prize if at least one player guesses correctly and no players guess incorrectly. The general problem is to find a strategy for the group that maximizes its chances of winning the prize.

Here is a solution that connects to coding theory: A strategy induced by a binary code $C$ of length $7$ is as follows. Player $i$ looks at the hat colors of the other players, and obtains a vector $(x_1,..,x_{i-1},*,x_{i+1},...,x_n)$, wherein $x_j$ is the hat color of player $j$, and $*$ is the unknown hat color of player $i$. If this vector has distance at most $1$ from a codeword, i.e., if $*$ can be chosen such that the resulting word is a codeword, then player $i$ guesses his hat color to be the opposite of $*$; otherwise, the player passes.

What is the success probability of this strategy? All players guess wrong, if the vector of hat colors is in fact a codeword. All players pass if the vector of hat colors has distance larger than $1$ from a codeword (and the team loses). All guessing players guess correct only if the vector has distance exactly one from a codeword. Therefore, the probability of success of this strategy is equal to the fraction of words of distance $1$ from the code. The $[7,4,3]$ Hamming code maximize this fraction. It turns out that if we replace $7$ by $n$ students and let $n$ go to infinity, there is an analogous strategy using punctured Hamming codes for which the success probability goes to $1$.