It’s storytime! I’m going to tell one of my favorite stories, so please make yourself comfortable.
Once upon a time, there was an evil prison warden in charge of a bunch of prisoners. Being evil, the warden decided to force the prisoners to play the following game. The warden gives each prisoner a hat, which is either red or blue, at random and with equal probability. Each prisoner can see everyone else’s hat, but not eir own. They aren’t allowed to communicate with each other. Then, each prisoner is allowed to guess eir hat color, or else pass, and all guesses are done simultaneously and independently. If at least one prisoner guesses correctly, and no one is wrong, then all the prisoners go free. Otherwise, they remain imprisoned.
The prisoners turned to us for guidance. How do they maximize their chances of going free?
First, we might expect that the best they can do is to assign one person to guess randomly and have all the others pass. That way, they win half the time and lose half the time. We’d be likely to think this because each prisoner who answers has a 50% chance of being right, so we do well to allow as few people as possible to guess.
Remarkably, they can actually do better. Let’s look at the simplest interesting case, that of three prisoners. Then, either all the prisoners have the same hat color, or it’s 2 to 1. This suggests a possible strategy: if a prisoner sees two of the same colored hats on the other prisoners, ey guesses the other color. Otherwise, ey passes.
Here’s what happens with this strategy in all the possible cases. The first three letters are the actual hat colors; the last three letters are the guesses (with a “P” denoting a pass). I colored the wrong guesses in red and the right guesses in blue.
- BBB RRR
- BBR PPR
- BRB PRP
- BRR BPP
- RBB RPP
- RBR PBP
- RRB PPB
- RRR BBB
So, they win 75% of the time. Aha! An improvement!
But why did our basic intuition fail us? Actually, it didn’t; it just answered the wrong question. Let’s look carefully: in the list above, there are six correct guesses and six incorrect guesses. The trick is that they managed to group the wrong guesses together while spreading out the right ones. The point here is that there isn’t any additional penalty for having many people guessing wrong, so there’s a bit of asymmetry in the problem that we get to take advantage of.
Let’s figure out if we can do that more generally.
Suppose we can, and there are prisoners. Then there are possible hat configurations, and say they lose in of these cases under a strategy similar to the one above, with the wrong guesses concentrated and the right guesses spread out maximally. Then they make a total of wrong guesses ( wrong guesses in each of the losing positions) and right guesses. But we need for there to be the same number of right guesses and wrong guesses, so we must have . Solving for , we find that . In order for this to be an integer, must be a power of 2.
Hence, the next interesting case is , with .
We can dig out a bit more from the case of , in fact. In each hat sequence in which they win, there’s exactly one hat that could flip that would cause them to lose, and in all such cases, that’s the person who guesses. We can rephrase this slightly to get something more useful: each position where they win is one hat flip away from a position they lose, and in exactly one way. This implies that any two losing positions differ from each other in at least three positions.
This suggests a possible idea for constructing the losing positions. For simplicity, we’ll write a 0 for a red hat and 1 for a blue hat, so hat sequences are strings of zeros and ones. So, we want to write a sequence of binary strings each of which differs from each other one in at least three spots. So, let’s just to try to find the “smallest” string at each stage? There’s no guarantee that it’ll work, but it can’t hurt to try. Let’s do this for . The first possible string is . The first string that differs from in at least three positions is . The first string that differs from each of and in at least three positions is . Continuing on, we get the following list:
As we move on, it becomes increasingly annoying to find more strings that work by checking that each differs from all previous ones in at least three positions, but it can be done. In fact, I was able to write this list down quite quickly, for reasons we’ll soon see.
We call a set of strings of length with this property, that any word differs from exactly one of the strings in in at most one spot, a Hamming code. These are very important in coding theory, as they are almost the only perfect codes. (There are two other exceptional ones, known as the binary and ternary Golay codes. These are also the subject of some beautiful theory, and perhaps future evil prison wardens will construct a game based on them.)
So, that does it for . Let’s recall why we were looking for these strings, since we’ve moved a bit away from our original hat problem. Since every string of length 7 differs by at most 1 from a string on our list, each person compares what ey knows of the string to the list. If there’s a match, ey guesses that the actual string is not the one on the list. Otherwise, ey passes. If it’s not on the list, exactly one person guesses correctly, and no one gets it wrong. If it’s on the list, everyone gets it wrong.
Let’s look at some examples. Suppose our hat string is 0100110. Then the first person can observe that, among all the listed hat strings above, they might be in 1100110, and everyone else knows that they’re not in any of them. Hence, the first person will guess 0, and everyone else will pass. So, they win in this position.
If, instead, the hat string is 0110100, then everyone can see that they might be in the string 0110100, of the strings above. Hence, everyone will guess that they’re not in that position, so everyone gets it wrong.
That was our goal, for . It turns out that a completely analogous construction always works for . But how do we prove it? To do that, we must venture into the land of games.
But I think that’s enough for now; the story will continue shortly.