The Hats Puzzle
Solution

Puzzle 1: Since everyone raised a hand, everyone sees a black hat. So there is at least one black hat on someone's head. This means, in particular, that no one sees two white hats. Everyone is seeing either two black, or a black and a white. When the king asks if anyone can guess the color of their hat, and everyone's hand drops, they have to think for a minute about what's going on. Suppose I see a black and a white hat. Then I reason as follows: if my hat were white, then the man with a black hat would not have seen a black hat, and would not have raised his hand. So my hat must be black. And this also means that anyone else who sees a black and a white hat can quickly figure that their own hat is black. Suppose, on the other hand, that I see two black hats. If my hat is actually white, then each of the other ministers sees a black and a white hat, so they've already figured out that their hats are black. But they are silent. Hence,..., my hat is black. Thus, assuming perfect reasoning, and allowing a decent interval for each thought, we can deduce that each minister can determine their hat color based on the silence of the others.

Puzzle 2: If D sees two hats of the same color, then he knows his hat is the opposite color, so he will speak almost immediately. However, if after a reasonable interval, he does not speak, then C knows that D must be seeing two hats of opposite color. Since C knows the color of B's hat, he knows his hat is the other color, and so he can correctly announce his hat color.

Puzzle 3: If there was only one cheating husband, then on the day of the announcement, 999 wives would know there was one cheating husband, as they had already assumed; one wife, the one being cheated on, thought there were no cheaters, and now knows there is at least one. Hence, she realizes, it must be her husband who is cheating. So she turns him in.

Suppose instead there were two cheating husbands. On the first day, 998 wives know what's up; wife #999 knows that husband #1000 is cheating, and wife #1000 knows that husband #999 is cheating. They both expect the one cheating husband to be executed. But neither one turns in their own husband, so nothing actually happens. Thus, after the executioner gets no offers, both wives realize that the only explanation is that there must be two cheating husbands, not one. So on day 2 there is a double execution. Reasoning this way, for our original problem, on the 50th day, all 50 cheated wives realize that their own husband is a cheater, and all 50 husbands get the chop.

Puzzle 4: If each minister simply guesses their hat color, then the chances are 7 in 8 that at least one will guess wrongly, so they will die. Supposing one minister agrees to guess, and the other two will remain silent, then their chances of surviving increase to 1/2. The surprising thing is, this is not the best they can do!

Suppose the ministers agree to the following strategy: Any minister who sees two hats of the same color guesses that his is the opposite color. Anyone who sees one hat of each color stays silent. Then the odds that they will survive increase to 3/4!

Here are the 8 equally likely cases of hat color, the guesses made, and the results:

           Hats     Guess     Result
         1  2  3   1  2  3
         -------   -------
         B  B  B   W  W  W    Death
         B  B  W   -  -  W    Survive
         B  W  B   -  W  -    Survive
         B  W  W   B  -  -    Survive
         W  B  B   W  -  -    Survive
         W  B  W   -  B  -    Survive
         W  W  B   -  -  B    Survive
         W  W  W   B  B  B    Death
      

The same puzzle can be solved, with similar results, when the number of players is one less than a power of two. For 15 players, for instance, there is a strategy for which the probability of winning is 15/16. For a general number of players, a solution is possible using Hamming codes.

Puzzle 5: If you sit in seat N, you have the advantage of seeing N-1 hats, but you don't hear what any other minister says. It turns out that seeing the N-1 hats is enough to tell you what color your hat is, so when the king comes to you, you will always answer "YES", you know what color your hat is.

But this means seat N-1 is bad. You can see N-2 hats, and if any one of them is white, you know your hat color. But suppose all the hats are black. Then your hat is white, or else minister N's hat is white. You get to hear what minister N says, but that's no advantage, because we already know he will say "YES". So if you only see black hats in front of you, you must answer "NO".

But this actually means that seat N-2 is good. The only thing we have to worry about is the case when all the hats we see are black. Minister N will say "YES" all the time, so that's no help. But Minister N-1 will say "YES" only if he sees a white hat in front of him. So if you don't see a white hat, it's you. If Minister N-1 says "NO", then he must only be seeing black, and so your hat is black. So you can always say "YES".

This pattern repeats. Seats N, N-2, N-4 and so on always are able to determine their hat color, while seats N-1, N-3, and so on will always be unable to be sure of their hat color if they only see black hats in front of them. Thus, roughly speaking, half the seats are safe. But here's another question: if you have to sit in one of the unsafe seats, and you have your choice, what should you choose? The front? The back? Does it matter? Remember the tradeoff: sitting towards the front, you see less information, but you hear more.

Puzzle 6: The other two hats have the values B = 20 and C = 30.

One stumbling block to solving this problem is the fact that, in general, you can't solve it. Or more precisely, in most case, no matter how many chances they are given, A, B and C will not be able to determine their numbers. So keep in mind that there must have been something special about the particular numbers that made it possible in this case. The fact that A was able to solve the problem is a clue as to what the numbers must have been.

Secondly, imagine that A sees that B and C both have a 25 on their hats. Since his number can't be 0 (the numbers were specified to be positive), it must be 50. And he knows this immediately. So we can rule out the case of (50,25,25).

But more importantly, we have discovered a rule. If any player sees the other two players have the same number of their hats, then that player knows immediately that his number is the sum of those numbers, and the game is over.

Now let's assume that the numbers 50, 20 and 30 are correct, and show how A figured out his number.

When A is about to make his first statement, he sees a 20 and a 30. This means his number is either 10 or 50. But he has no other information to go on, hence his statement "I cannot determine my number."

After B and C have spoken, it is A's turn again. Although B and C can't guess, this itself is an important and new piece of information for A. A now knows that there is not enough information for B or C to determine their values. And A now thinks about how this can be possible.

Remember, A knows his value is either 50 or 10. A now examines the consequences if his number is 10. In particular, he imagines the current game from C's perspective.

If A's number was 10, then when it was C's turn to speak, C would realize that his own number must be 10 or 30. But C would also know that B could not guess his own number. However, C would realize, if C's number were 10, then B would have seen two 10's and won the game. And that didn't happen.

Therefore, (still assuming that A's number is 10), and B did not see two 10's. Therefore, C would have realized that his own number cannot be 10, and so must be 30. So if A's number was 10, C would have had enough information to win the game.

But C did not say anything. Therefore, A now realizes that his own number cannot be 10, and that it must be 50. And so A can win the game.

Now, this shows that for the given data (50,20,30), A's answer is reasonable. It does not show that there is no other set of numbers for B and C for which a similar process would allow A to determine his number.

Thanks to Scott Hansen for nailing this problem!

Puzzle 7: If the ministers agree on a proper stategy, they can guarantee their survival no matter how the hats are placed.

However, one of the ministers must have taken set theory, and be very persuasive. Also, the ministers will all have to remember a lot of information and act quickly.

To see why a sure-fire survival strategy exists, let us assign numbers to the ministers, and then consider the set H of all possible hat mappings

h:N -> {black,white}

We must assume that the ministers can work out this list of representatives for the equivalence classes in the five minutes grace time they have!

Now let the hats be assigned according to the mapping h that the king has chosen. Each minister sees all the elements of the mapping except its value for his own head. But each minister realizes that not knowing the color of the hat on his own head will not keep him from determining the equivalence class to which h must belong, since the value of a single hat does not affect the class assignment. Now each minister considers the representative of the equivalence class, and looks up what his hat assignment would be in that mapping. This is his guess. And, because h is a member of this equivalence class, only finitely many of the ministers can be wrong. And therefore, the king will always be satisfied, and the ministers will always survive!

(This puzzle has been told and considered by Peter Winkler)

Reference:

1. Sara Robinson,
   Why Mathematicians Now Care About Their Hat Color,
   The New York Times,
   10 April 2001.

Back to The Hats Puzzle;