On prisoners and their hats (Part III)

This is the third part of the story. The first and second parts can be found here and here, respectively.

Previously, we showed that the lexicographic code we constructed consists exactly of the $\mathcal{P}$ positions of the game of nim.

But, there’s still one more thing to do: we need to check that every string differs from a string on the list in at most one position. Notice that we haven’t used anything about the length being $2^n-1$ yet, and here’s where that will be important.

To see that this really is important, look at strings of length 6. The $\mathcal{P}$ positions in nim with piles of length up to 6 are:

• 000000
• 000111
• 011001
• 011110
• 101010
• 101101
• 110011
• 110100

Here, there are indeed strings of length six that differ from each of these in more than one spot: one example is 001100. If we look all the way back to our length-seven strings near the beginning of this post, we see that if we pad the string with an extra 0 at the front, so that it becomes 0001100, then this one does differ from one of the length seven strings in one position, namely 1001100.

To understand this phenomenon, we need to understand the winning strategy for nim. (Exercise for the reader: I’d love to be able to do this without referring to the winning strategy, but I can’t see a way to do it. If you can figure it out, I’d be delighted to hear!)

So, I’ll tell you what it is. Suppose we have nim piles of size $a_1,a_2,\ldots,a_r$. We write each of the numbers $a_1,a_2,\ldots,a_r$ in binary, and then we add without carrying. This gives us the nim sum $s$ of the numbers. Let’s do an example.

Suppose I have piles of size 2, 3, 5, 7, and 8. These numbers in binary (padded with zeros at the beginning to make them all have the same length) are 0010, 0011, 0101, 0111, and 1000, respectively. So, in each column, we write a 1 if an odd number of them have a 1 in that position, and we write a 0 if an even number of them have a 1 in that position. Hence, the nim sum is 1011, which is 11 (when written in base ten).

The way this works is that if $s=0$, then the game is a $\mathcal{P}$ position; otherwise, it’s an $\mathcal{N}$ position. How do we make a winning move from an $\mathcal{N}$ position? We have to make it have nim sum zero after we move. So, the way to do that is to look at the leftmost nonzero column in the binary form of $s$; we can find one of the original piles that has a 1 in that position (or else we would have had a zero there). Now, we nim sum those two piles together, and that tells us how many to leave.

Why does this work? The point is that it satisfies our recursive determination of $\mathcal{N}$ and $\mathcal{P}$ positions. That is, from an $\mathcal{N}$ position, there is a move to a $\mathcal{P}$ position; on the other hand, from a $\mathcal{P}$ position, there are only moves to $\mathcal{N}$ positions.

So, in the example above, we had $s=1011$, so we find a pile with a 1 in the first column. The only one that has that is the 8, so this tells us that we must move in that pile. We replace it with the nim sum of $1011$ and $1000$, which is $0011$, or 3. So, our only winning move is to replace the pile of size 8 with a pile of size 3.

What’s important for us here is that, if one of the piles is much bigger than all the rest of them, in the sense that its binary expansion has more digits than all the rest of them, then we must be in an $\mathcal{N}$ position. (This is what I’d like to understand without referring to the winning strategy, but I don’t know how to see it otherwise.)

Okay, so what does that have to do with Hamming codes? The point is that if we have any nim position at all, we can add at most one pile (of some size) to make it a $\mathcal{P}$ position; the only worry is how big the pile might be. But, by what we saw above, that new pile can’t have more digits in binary than the other piles.

So, that’s what explains why the codes “close up” when their size is one less than a power of two, and not otherwise.

Well, we’re nearly done now! There’s only one question left, I think: suppose we’re playing the hat game. (Remember that from eons ago?) Do we have to memorize the list? Or, can we figure out what to play in some other way?

We can do it more intelligently. Here’s how: Give each person a number, from 1 to $n$, where $n$ is the number of players. So, each player should write down the numbers of all the other people with blue hats, then take their nim sum. Now, there are three possibilities. Case one is that we get a nim sum of zero. Then, our string is on the list if ey has a red hat, so ey should guess blue. The second case is that ey gets eir own number. In that case, the string is on the list if ey has a blue hat, so ey should guess red. Finally, ey might get a completely different number. In that case, ey should pass.

So, that’s the part of the story I wanted to tell here. There’s a lot more to say about games and error-correcting codes, as well as some other related topics, such as sporadic finite simple groups. It’s a really beautiful theory, and I may write more about it at some point in the future.

Also, I should give credit to those who helped me learn the story. I first saw the hat problem, together with some of the connections given here, in a talk Mira Bernstein gave at the Berkeley Math Circle when I was in high school. I learned about lexicographic codes (in a somewhat different form) initially from a video of a talk John Conway gave at Banff (unfortunately, the video seems to have been removed from the Banff website), and then I learned more from Conway and Neil Sloane’s fabulous paper “Lexicographic codes: error-correcting codes from game theory.” Also, thanks to two years of the SUMaC coding theory research group for listening to me tell this story in a primitive form and improving it.