Reliable Software Logo
Home > Science  >Three Hat Puzzle > Solution

Hat Guessing Game: The Answer

R R R
R R B
R B R
B R R
R B B
B B R
B R B
B B B

Notice that all possible distributions of hats can be grouped into two categories: either all three have the same color (uniform), or two have one color and the third the other color (mixed). If you have any doubts, consider all 23 possibilities (see the table on the right).

The mixed case accounts for 75% of all possibilities (6 out of 8), so let's concentrate on it. The crucial observation is that, in a mixed case, one person sees two hats of the same color, the other two persons see mixed colors. So the clever strategy is to always pass when you see two hats of different color; but when you see two hats of the same color, make a guess that your hat is the opposite color. In other words, if you see that your partners both have red hats, guess that your hat is blue. If both their hats are blue, guess that yours is red. Otherwise pass. You will win 75% of the time! Notice also, that when you are wrong, all three of you are wrong. This kind of pooling of wrong answers is good.

Analysis

It's a clever solution, but it's more of a guess than a method. So let's analyze the problem in detail. First of all, we have to find the right mathematical language. I propose to identify the three people as x, y and z and the colors of their hats as 0 for blue and 1 for red. So each situation can be described by assigning zeros and ones to three variables, x, y, and z. If we further interpret x, y, and z as coordinates in three-dimensional space, we can see that each combination correspond to a vertex of a unit cube (see Fig 1.).

Unit cube

Fig 1. Unit cube. Each of the 8 vertices corresponds to one combination of hat colors.


Person x can see the coordinates of person y and z, but doesn't know the value of x. So from the x's point of view, the vertices that differ by the value of x are undistinguishable. In Fig 2. I have connected these vertices using thicker blue lines.

x's view of the cube

Fig 2. Blue lines connect vertices that are indistinguishable from the point of view of person x


A strategy for person x requires assigning an action to each perceived situation. Since a situation perceived by x correspond to a blue edge in Fig 2., person x must decide on an action for each of the blue edges. An action could be: passing or guessing. A guess means selecting the value of x, either zero or one. Let's denote a guess by an arrow pointing towards the guessed value of x (no arrow means pass), see Fig 3. The guess is correct if the situation corresponds to the vertex pointed to by the arrow. If, on the other hand, the situation corresponds to the other vertex, the guess is incorrect.

x's guess strategy

Fig 3. X's strategy. Guess 0 when y=1 and z=1, guess 1 when y=0 and z=0, otherwise pass.


By the same argument, Y's strategy consists of assigning arrows to edges along the Y axis and Z's strategy consists of assigning arrows in Z direction. The complete strategy for the whole group can be described by a cube with arrows along some of the edges.

A winning situation is a cube vertex that has at least one arrow pointing towards it (correct guess) and no arrows pointing away from it (incorrect guesses). Of course, each time we draw an arrow we mark one vertex as a loser (the origin of the arrow). So we must necessarily have some losing vertices. The trick is to make a losing vertex the origin of as many arrows as possible (the pooling of wrong guesses). For instance, let's select the vertex (0, 0, 0) as a complete loser. We'll originate three arrows from it. This way we have one loser and three potential winners (see Fig 4.).

Selecting a loser vertex

Fig 4. Selecting (0, 0, 0) as a loser vertex


 

Now it's enough to select the opposite vertex as the second loser. The three arrows originating from it will designate three new winners. The rest of the edges will remain unmarked, thus corresponding to a pass (see Fig 5.).

The winning strategy cube

Fig 5. The winning strategy cube with two loser vertices


Can you see that Fig 5. describes the solution presented at the top of the page? What's more, it is immediately obvious that there are three other, more complex, solutions. They correspond to selecting (1, 0, 0), (0, 1, 0), or (0, 0, 1) as initial losers (and their opposite vertices as the secondary losers).

Finally, let me show you the solution to the same problem with seven people, instead of three. I have squashed the 7-dimensional hypercube in such a way that one loser vertex (0000000--seven zeros) is on the left, then there is a column of seven nearest neighbors (with six zeros and a single one), then a columns of its second-order neighbors (five zeros, two ones), etc., until we get to the opposite vertex (all ones) (see Fig 6.)

Best strategy for 7 people

Fig 6. Solution for seven people. Only edges with arrows are shown.


You can count 16 loser vertices out of the total 27 = 128. This is equivalent to 1/8 odds of losing, or 7/8 of winning. These are pretty good odds!

By the way, a general solution for any number of people is not known so far. There is a lot of interest in this type of problems, because of their application in communications. Not being able to see a given hat is equivalent to losing one bit in a transmission. Being able to guess this bit with high probability gives means towards restoring a garbled message.