Solution: A Hat Trick + 1 of Hat Puzzles
In this month’s Quanta Insights puzzle, we explored three examples of hat puzzles, in which hats of different colors are placed on the heads of a number of participants who can see the colors of some or all of the other players’ hats but not their own. The players then have to guess the color of their own hats based on logic. Classically, there is a reward for being right, and a punishment for being wrong. As I explained, there are endless variations in the conditions of the game that completely transform the nature of the answers. But the common thread is that there are clever ways to get a better payoff than you expect when you first encounter the problem.
We presented the puzzles in the context of a modern TV game show with a hefty prize purse that the players had to maximize. In our three puzzles, the naive expectations of random guessing were: 75 percent of maximum for Puzzle 1, 33.3 percent for Puzzle 2 and 33.3 percent for Puzzle 3. Yet the best solutions can enable the contestants to win, respectively, 100 percent, 90 percent and 98.3 percent of the maximum. Here’s how this magic is achieved:
Puzzle 1: 2 Hats, 2 Colors
There are only two contestants. They are given instructions by the host and allowed to confer before the game to come up with a strategy. At the start of the game, a hat that may be either blue or red is chosen at random from a large number of hats and placed on each contestant’s head. As is standard, each contestant can see the other’s hat but not her own. The host then sounds a buzzer, and each contestant must write the color of her hat on her own private tablet. If either of the contestants is correct, both of them win $1,000. If there are 10 rounds, what is the maximum amount of money the contestants can expect to make? Can you explain how the strategy works?
If the two players guess randomly, there would be a 1 in 4 chance that both were wrong in any particular round. Hence, random guessing would only net each contestant $7,500 in 10 rounds. Here is the clever way to improve on this, as explained by kayue. It seems truly magical if you didn’t think of it:
Let the two contestants be P and Q. They can write down the color of their hats in the following way: P writes down the color of Q’s hat, and Q always writes down the color different from P’s hat. Since either they wear hats with the same color or different colors, one of them must be correct, and they will always win.
Note that neither contestant is exceeding her expectation: As before, both can expect to be right half of the time and wrong the other half. What their trick does is spread out their right and wrong guesses so that they are never both right or both wrong, but one of them is right in every single round. This principle — that even when you can’t improve the error rate of each individual guess, you can still arrange things so that a bunch of guesses can guarantee a far higher degree of accuracy — is the basis of error-correcting codes used in data transmission, such as the Hamming code.
Puzzle 2: 10 Hats, 3 Colors, 1 Bug
(This puzzle was brought to Quanta’s attention by reader Ian Hoffecker. He heard about it from his friend Hikaru Saito, who is currently a postdoc in physics at Kyushu University.)
In this game, there are 10 contestants. As before, they are given instructions by the host and allowed to confer before the game. The room, however, is bugged, and the host can overhear the contestants’ plan and adapt his hat-placement choices accordingly. The contestants know about the bug but can’t do anything about it. During the game, the contestants are lined up single-file. Colored hats that are either blue, red or yellow are placed on each of their heads. As expected, each contestant can see the colors of the hats of everyone in front of her but does not know the color of her own hat or that of anyone behind. The host, starting from the back of the line, asks each contestant to state aloud the color of her hat. The contestants are not permitted to say anything other than a color (blue, red or yellow), and they can only speak once. (All of the contestants hear what each of the others says aloud.) The host then goes to the next contestant and repeats the question, continuing until all contestants have spoken. At the end, if there are x correct answers, a purse of x times $10,000 is distributed equally among all players. Note that the host is trying his best to save money for the house. For example, if all the contestants decide to announce blue as their color, on the presumption that this could guarantee a third of the prize money, the host could simply put red hats on everyone. What strategy maximizes the amount the contestants win? And what is the expected amount?
The winning strategy here can be called the “checksum modulo-3” method. It uses two mathematical principles: the checksum (you add a bunch of numbers and take the last digit); and using the appropriate base — in this case, base 3, in which you find a remainder. Here’s how it works:
The players come up with a three-digit code for the hat colors: thus, yellow = 0, blue = 1 and red = 2. Let’s use the illustration above for the hat colors, and assume that the two unseen players in our illustration both have yellow hats. Then the sequence of hats, from the point of view of player 1, is YYRBRBRYY (she doesn’t see her own blue hat). The sum is therefore 0 + 0 + 2 + 1 + 2 + 1 + 2 + 1 + 1 = 8. The first player divides 8 by 3 to get 2, which is the code for red, so she says, “Red.” She is wrong in this instance, but this information allows all the other players to be right. Each other player now has to get the checksum of the hats she sees and subtract it from the original number minus all the previous guesses, divide by 3 and find the remainder to get the color of her own hat. Here’s how she would do this in practice. (Note that the following procedure does away with the need for negative numbers). Each player starts with the number 30 and adds the first player’s color code to it. Any large enough multiple of 3 will do: 10 people times three colors is good enough. In this case, she obtains 32. Every time any other player before her (besides player 1) speaks, she subtracts that person’s color number from this number, keeping a running tally. Then she adds all the hat numbers she sees and subtracts the sum from her running tally. This is her final number, which she divides by 3 to get her hat color. Let’s do this for players 2, 3, 4 and 5.
Player 2: 30 + 2 = 32. No other player before her. Running tally = 32. She sees YRBRBRYY = 0 + 2 + 1 + 2 + 1 + 2 + 0 + 0 = 8. 32 – 8 = 24. Divide by 3, remainder = 0. She says yellow. Right!
Player 3: Previous running tally = 32. Player before her said Y = 0. 32 – 0 = 32. Running tally = 32. She sees RBRBRYY = 2 + 1 + 2 + 1 + 2 + 0 + 0 = 8. 32 – 8 = 24. Divide by 3, remainder = 0. She says yellow. Right!
Player 4: Previous running tally = 32. Player before her said Y = 0. 32 – 0 = 32. Running tally = 32. She sees BRBRYY = 1 + 2 + 1 + 2 + 0 + 0 = 6. 32 – 6 = 26. Divide by 3, remainder = 2. She says red. Right!
Player 5: Previous running tally = 32. Player before her said R = 2. 32 – 2 = 30. Running tally = 30. She sees RBRYY 2 + 1 + 2 + 0 + 0 = 5. 30 – 5 = 25. Divide by 3, remainder = 1. She says blue. Right!
And so on for the others:
In our example, player 1 ends up making the wrong guess. In an unbugged game, player 1 will be right one third of the time. But because of the bugging, the host knows the contestants’ strategy and can always make sure that player 1 is wrong. Satisfy yourself that the host is powerless to do anything about the correct guesses of the other players, even though he can figure out exactly what they’ll be!
Puzzle 3: 10 Hats, 3 Colors, Pass Allowed, Forfeiture on Wrong Guess
(This puzzle is a three-hat version that I created based on a simpler puzzle proposed and solved by ninth grader Alex Smith of St. Mark’s School in Massachusetts. Alex’s puzzle was one of 12 hat problems discussed in an article by Ezra Brown and James Tanton in the journal Math Horizons.)
As in Puzzle 2, this game features 10 contestants and hats of the same three colors, with the contestants lined up in a row and in formal Victorian garb as shown above. They have been allowed to confer before the game, but in this game there is no bug. The hat colors are chosen at random, and the contestants know this. This time the contestants are also allowed to say “pass” instead of guessing a color. As before, the questioning starts at the back of the line and proceeds to the front. If a single contestant guesses incorrectly, or all 10 contestants pass, the purse is forfeited and no one receives any money. If any one of the contestants guesses correctly, with no wrong guesses, the entire purse of $100,000 is distributed equally among all the players.
What strategy will maximize the probability that the contestants win? How often will that be?
Here’s Alex R.’s answer:
The best strategy is: Pass if you see red or if someone has guessed; guess red otherwise (or equivalently for another color). If and only if any of the hats are red, they win.
Here’s how: If none of the hats are red, they can’t win, since they will only guess red; otherwise, the first (in guessing order) contestant who doesn’t see red will guess red; they must be wearing red because by assumption, at least one hat is red, and by the strategy, the contestant behind them would only have passed if they saw red. This strategy wins with 1 – (2/3)10 probability.
The quantity (2/3)10 is the probability that none of the hats are a certain color, in this case red. The winning probability is 98.3 percent. For further details, consult Wiley’s detailed solution. Wiley, our Quanta T-shirt winner from last month, was the first person to get all three puzzles correct, and also proved that you cannot do better than 98.3 percent in Puzzle 3.
Notice that the high penalty for an incorrect guess in Puzzle 3 requires a different strategy from that used in Puzzle 2. But what if the players get rewarded for every correct guess? Which strategy would win out? In order to elicit an answer, I proposed a fourth puzzle in the comments.
Puzzle 4
The game is played the same way as in Puzzle 3, but the purse is multiplied by the number of correct guesses. So if four people guess correctly, the total purse is $400,000. A single incorrect guess still forfeits as before.
How can the players maximize the average expectation per game, and how much will it be?
This puzzle was brilliantly answered by Ben, using a sophisticated version of the checksum modulo-3 technique from Puzzle 3. Here it is, in his words:
Best solution for puzzle 4 that I found is to use a variation of the checksum trick that works in problem 3, as follows. Players are numbered from the first player to speak, who sees all the remaining hats, to the 10th player to speak.
Players 1–3 pass if the sum of players 4–10 is 0 mod 3. Otherwise, players 1–2 pass if the sum of players 3–10 is 0 mod 3. Otherwise, player 1 passes if the sum of 2–10 is 0 mod 3. Otherwise, player 1 encodes the sum of players 2–10, and takes a 2/3 chance of losing everything.
He added: “The calculation for expected value is (1/3)7 + (2/3)(1/3)8 + (2/3)^2(1/3)9 + (2/3)^3(1/3)10.”
The expected payoff is about $643,210, in spite of the forfeit for a single wrong guess. Astounding!
Reader Anil showed that Ben’s method could also be applied to Puzzle 3, and Ben was able to generalize to the whole class of similar puzzles with arbitrary payoffs. Wiley then extended this to the general case, for any number of hat colors.
I love these kinds of conversations in the comments thread. It’s fascinating to follow the development of ideas as commenters build on what others have written and take the idea in different directions. It’s indeed a microcosm of science. Something very similar happened in the last Insights column as well, when a bunch of us created a complex dance floor that had a forced winner after 13 rounds without having an unequal number of different colored cells.
Keep the ideas and insights coming. Someday, we may together discover something that could be publishable in a scientific journal.
The Quanta T-shirt for this month goes to Ben for his brilliant solution to Puzzle 4 and its generalization.
Cheers, and see you all again soon.
