Today I want to share with you one of my favorite brain teasers along with the solution and a walk through of my thought process as I solved it. I was first introduced to this marvelous puzzle several years ago when I was a student at Carnegie Mellon University and it has remained one of my favorites ever since. There are many similar puzzles but the solution to this one is especially nice. Here’s the puzzle:
15 people are going to play a game. They each have a hat placed on their head. Each hat is either white or black with an independent 50% probability. The 15 people then stand in a circle so that each person can see each other's hat but no one can see their own hat. Simultaneously each person must guess the color of their hat. They can guess “White”, “Black” or “I don’t know”. Then the game is scored as follows. If anyone guesses incorrectly they lose also if everyone guesses “I don’t know” then they also lose. Otherwise there will be at least one correct guess and no incorrect guesses and that will be a win. The 15 people are allowed to work together to figure out a strategy beforehand but once the hats are placed any communication of any kind is forbidden. The goal is to find a strategy with a win probability of at least 90%
This is a very nice puzzle. I strongly encourage you to work on it a little bit before reading the solution. Even if you don’t solve it, the time you spend will help you appreciate the solution.
SPOILERS BELOW
We can number off each of the 15 people with the numbers 1 to 15 written in binary. Then each person will follow this strategy. Look at the set of numbers of people you can see who are wearing black hats and take the bitwise XOR (*see footnote if you don’t know what bitwise XOR is) of the numbers in this set. If the result is 0 guess black, if the result is equal to your number guess white otherwise guess “I don’t know”.
So first thing’s first, why does this strategy work? Well suppose that you were one of the participants and you for some reason knew that taking the bitwise XOR of all of the black hats did not give 0, when would this let you deduce your own hat color? Well if the XOR of the black hats you could see did give 0 then this must imply that you can’t see all the black hats and thus your hat must be black. On the other hand if the XOR of the black hats you can see is equal to your number then if your hat was black the total XOR would be your number XOR your number which is equal to 0, which can’t be. Thus you can deduce that your hat must be white. In every other case you will not be able to deduce your hat color. We see that this lines up exactly with the guesses for the given strategy. This means that the strategy comes from each person assuming that the XOR of all the black hats is not 0.
Let’s analyze this a bit more precisely. Suppose that the XOR of all the black hats is x=/=0. Now consider person y=/=x. The XOR of all the black hats they can see will be either x (if their hat is white) or xXORy (if their hat is black) either way this is never equal to 0 or y so they will always guess “I don’t know”. Now consider person x. If their hat is white they will see black hats which XOR to x and correctly guess white. If their hat is black they must see black hats which XOR to 0 and they will correctly guess black. Thus we see that if the blacks hats XOR to a non zero value we will always get one correct guess and 14 “I don’t know”s and thus the group will win.
What happens if the black hats XOR to 0. In this case everyone with a white hat will see a collection of black hats that XORs to 0 and guess black and everyone with a black hat will see a collection of black hats which XORs to their number and guess white. So we will get 15 incorrect guesses and lose. (this structure is not a coincidence, more on this later)
So now figuring out the win probability of this strategy reduces to figuring out the probability that the set of black hat numbers XORs to 0. Intuitively we might expect that each of the 16 outcomes of the XOR, 0-15 are equally likely. This is in fact the case. It can be proven by noting that there is a bijection from the set of arrangements that XOR to x and those that XOR to y by flipping the color of hat number xXORy. This means the probability that the hats XOR to 0 is 1/16 and thus the win probability is 15/16 = 93.75% which is indeed greater than 90%.
If you’re like most people when you heard that solution your first thought was “That’s cute but how the hell would anyone ever think of that?” so for the rest of this essay I want to go through my thought process as I solved this puzzle.
The first thing I tried was a trick that I used a lot during my olympiad days which was to try to build intuition for the problem by solving a simpler version. The easiest way to reduce the complexity of this problem is to reduce the number of hats. With 15 hats there are 2^15=32768 possible combinations of colors which is way too many to analyze explicitly but if we reduce the number of hats down it becomes more tractable. The 1 hat version is trivial and analyzing the 2 hat version doesn’t seem to yield anything interesting but the 3 hat version is quite nice.
We notice that with 3 hats there are 2 possibilities either all of the hats are the same color or there are 2 hats of one color and 1 hat of the other color. The second case is 3x more likely than the first case so perhaps we can find a strategy which wins unless the 3 hats are all the same. After a little thought I came up with the following strategy. If you see two hats the same color guess the other color, otherwise guess “I don’t know”. If there are 3 hats of the same color this leads to everyone guessing wrong for a loss but if there are 2 and 1 the odd man out will guess correctly and the other 2 will guess “I don’t know” for a win. So this strategy has a 75% win chance.
It seemed unlikely I could do better with 3 hats so at this point I tried to generalize this strategy to 15 hats. I looked for guessing strategies based upon the number of hats of each color that were seen. Unfortunately this did not pan out. The numerical distribution for 15 hats is too spread out to get anywhere close to a 90% win probability with a strategy based on the number of hats.
Since a direct generalization did not seem forthcoming I went back to take a closer look at the strategy for 3 people to see if it had any key features that might be important. The first thing I noticed was that in the winning cases it was always only 1 person guessing correctly but in the losing cases it was always everyone guessing wrong. This didn’t seem likely to be a coincidence and in fact it’s not. For any person no matter what colors they see their hat is always still 50/50 so any guess has a 50% chance of being right. Given this info the only way to make the group win more than 50% of the time is to clump the wrong guesses together. This observation also allows us to put an upper bound on the win probability. The upper bound is achieved when all the wrong guesses are clumped together and all the correct guesses are spread out as much as possible. If this happened and there were n people there would be n wins for each loss for an overall win probability of n/(n+1).
So now that we have an upper bound we can work on trying to achieve it for the n=15 case. We know that we need to divide the possibility space into 16 cases, one where each of the 15 people guesses correctly and one where they all guess incorrectly.
When dividing up the cases my first thought was that maybe the cases corresponded to something mod 16 so I decided to investigate the strategy where we number the people off 1 to 15 and then everyone makes the collective assumption that the sum of the numbers of the black hats is not equal to 0 mod 16. Then each person guesses if and only if they can deduce their hat color from the hats they can see and the collective assumption. My hope with this strategy was that depending on what the actual sum was mod 16 one guy would be able to deduce his hat color and guess.
Unfortunately the modular strategy doesn’t quite work like I had hoped. Suppose the sum of the black hats is x then there are actually 2 people who potentially might be able to deduce their hat color. If person x has a black hat then the sum of the black hats he can see must be 0 mod 16 and thus in order for the total sum to not be 0 mod 16 he knows that his hat must be black. Also if person 16-x has a white hat they will see all the black hats and thus they will see a sum of x. They will then be able to deduce that their hat is black because adding it to x would make 0 mod 16 which would contradict the assumption.
So instead of always designating one guesser what this strategy does is nominate 0,1 or 2 guessers depending on the colors of hats x and 16-x. It feels like we’re on to something here but at the same time something is not quite right.
There is however one case that works perfectly, if x=8. In this case x=16-x so no matter what color hat 8 is the wearer will be able to deduce it. So now the question becomes how can we make the other cases work out like this case?
The special thing about 8 is that when working mod 16 adding 8 and subtracting 8 are the same thing. 8 is its own inverse.
The last observation I made before figuring out the answer was that this problem seems to have connections to powers of 2. The number of possible hat combinations is a power of 2 and 16, the number of cases we want to split into, is also a power of 2. This insight inspired me to write the numbers 1 to 15 in binary.
Once the numbers were written in binary the idea to use bitwise XOR is not too hard to come up with. XOR is similar to addition except every number is its own inverse so now every number works like 8 did and from here the solution I gave originally falls out.
As you can see, while the solution to this puzzle may at first seem very esoteric and unmotivated it actually can be arrived at quite naturally with a bit of cleverness.
FOOTNOTE: What is XOR? XOR is short for exclusive or, the xor of 2 bits will be 1 if exactly 1 of the bits is 1 and 0 otherwise. When we talk about the XOR of 2 numbers we mean writing the numbers in binary and then applying the XOR operation to each of their bits. So for example if we wanted to calculate 7XOR9 we would write them both in binary to get 0111XOR1001 then apply XOR to each bit to get 1110 or 14. Note that the bitwise XOR operation is equivalent to doing the addition algorithm but skipping all the carry steps. The XOR operation is commutative, associative, and every number is its own inverse. These properties make it the ideal fit for what we need in this problem.
This is really cool! I was totally nerdsniped by this problem and thought about it, on and off, for several days.
SPOILERS FOLLOW!
Like you, I found a solution for the 3-player problem first, then tried various ways of generalizing that: maybe more players had some way to agree on a subset of three people to play the 3-player version? Maybe 15 players were actually five sets of 3? None of these worked well.
My next thought was to look for some statistic of the hats that could be determined by all players, and where some values were more likely than others. First attempt: the number of black hats. This solves the 3-player problem: the correct value is either 0, 1, 2, or 3. 1 or 2 are most common, and so it pays off to guess that the real value is 1 or 2. For the 5-player game, this also works, but the probability of winning is less good. Players can guess that there are 0, 2, 3, or 5 black hats, which succeeds in 22/32 cases. With even more players, this gets worse and the success probability approaches 50%.
For the 5-player game, a better statistic is the maximum number of consecutive black hats. The distribution is:
0 x1
1 x10
2 x10
3 x5
4 x5
5 x1
There is a strategy that succeeds in all the 1, 2, and 4 cases => a win probability of 25/32 = 78%. This was the first strategy that I found with >75% win probability, and it felt like a breakthrough.
I don't know whether I would have arrived at the XOR strategy, had I continued down that road... But the journey thus far was interesting, and I hope this comment is fun to read for others.
---
If you like this type of puzzle, you might enjoy the following:
_100 people are playing a game: A room contains a cupboard with 100 drawers. The game director randomly puts one player's name in each closed drawer. The players then enter the room, one after another. Each player may open and look into 50 drawers in any order. The drawers are closed again afterwards. If, during this search, every player finds their name in one of the drawers, all players win. If even one player does not find their name, all players lose. Before the first player enters the room, the players may discuss strategy — but may not communicate once the first player enters to look in the drawers. What is the best strategy?_
From https://en.wikipedia.org/wiki/100_prisoners_problem
Hint: the best strategy has >30% win probability.