# Solution: A Hat Trick + 1 of Hat Puzzles

For four game show variations of the hat puzzle, four clever ways to earn a better payoff than you might expect.

Olena Shmahalo/Quanta Magazine; collage resources via Antique Images

6

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.

A monthly puzzle celebrating the sudden insights and unexpected twists of scientific problem solving. Your guide is Pradeep Mutalik, a medical research scientist at the Yale Center for Medical Informatics and a lifelong puzzle enthusiast.

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?

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.

• Phil and Steph says:

puzzle 3:

Everyone should pass except the first person who sees no blue hats – he should guess "Blue"and everyone after that should pass.

they are guaranteed to win if there is at least on blue hat: probability= 1 – ((2/3.0) **10) 0.9826584700841674

• Victor says:

I am curious. Suppose that we were playing game 3, and the players knew that there was some non-uniform distribution of probabilities (e.g., 50-25-25%), but they did not know which hat had which probability. How would the optimal strategy change with distribution? For example, if the distribution were known to be 50-50-0, then the pass-until-red strategy would only work 2/3 of the time, and another approach would surely be better (pass until one sees no repeats and then guess the same color as the hat in front, or pass until one sees only one of color and guess that color). I suspect that there are certain regimes in which different strategies are best and would be interested to see a map of them.

• Ben says:

Victor – interesting question.

The following is a tiny modification of a strategy that Anil and I came up with; in this case, it's not easy to analyze, and I don't have an opinion on whether/when it's optimal (as far as I know, it might always be optimal).

Let red=0, blue=1, yellow=2. Let i be the least integer such that the sum of the last i hats is 0 mod 3. The first 10-i people pass, and the next player knows exactly his or her hat color – if the sum mod 3 of the hats he sees is k mod 3, his hat is -k mod 3. If i=10 or is undefined, then the first player just guesses with the majority of the hats he sees, breaking ties arbitrarily.

The only case this strategy fails is if there is no i<10 such that the sum of the last i hats is 0, and the first hat does not agree with the majority. As pointed out by Anil, this matches the more obvious "choose red if you see no reds" strategy in the original formulation of problem 3; in your new formulation, it seems to be better.

• Ian Hoffecker says:

Since I didn't see it yet, I thought I'd add my solution to Puzzle 2 which uses cyclic group theory (ie not explicitly modulo) to guarantee 9 of 10 correct guesses. A thorough, visual explanation of the solution and theory behind it is on my github:
https://github.com/Intertangler/tutorials/blob/master/10%20prisoners%203%20colors%20-%20puzzle%20solution%20and%20theory.ipynb

• Michael Leece says:

There's another way to formulate a solution for Puzzle 2, which likely reduces to a similar approach, but I like.

If you reduce the worlds that the first person can see to just the counts of red, blue and yellow hats, the range of possible worlds becomes a triangular plane in 3d space with corners at (9,0,0), (0,9,0), and (0,0,9), with discrete points in between that sum to 9 (the "real" worlds). Similarly, the worlds that the other 9 people get to see are triangles with corners at (8,0,0), (0,8,0), and (0,0,8) (the "visible" worlds), since everyone in the line gets to "see" everyone else, assuming that the people before them will say the correct color.

If you overlay these triangles and connect "real" worlds to "visible" worlds, each point in each triangle will be connected to 3 points in the other triangle. For the "real" points, these will be the possible visible worlds that people in positions 2-10 will be seeing, and for the "visible" points, the connections will correspond to the possible real worlds from what I can see, given the three different options for my hat color.

Then all we need to do is assign each "real" world a color, such that each "visible" world's three neighbors are all different colors, so when the first person says the real world's color, I can deduce which of the three neighbors of my visible world are in fact the real world, which makes it trivial for me to deduce my own color. That coloring of the real worlds turns out to be both easy to do and remember, such that I'd feel comfortable doing it in my head if my life was on the line.

The explanation really works a lot better with a whiteboard ><

• Wiley says:

Just came across another reference for puzzle 3: Paterson & Stinson (2010)
http://www.emis.ams.org/journals/EJC/Volume_17/PDF/v17i1r86.pdf

@Victor,
To rephrase a bit: we want the optimal strategy given three non-negative probabilities p, q, r with p+q+r=1 that correspond to one of the color permutations that we don't know? If we assume it's uniformly sampled from all 3! permutations, I don't see the difference vs. the original problem. In general, as long as we are given how the correspondence is sampled, we can always pick the color with the largest weighted probability and apply the exact same strategy, no?

If there is absolutely no information regarding the sampling, then the advantage of using Ben's approach is due to the modulo central limit theorem (which can be proved by using Fourier analysis on the probability generating function). In this case, we sum up some reasonably large number of i.i.d. random integers then modulo 3, the resulting distribution exponentially approaches a uniform distribution.

Even though when p=q=r=1/3, the strategy using the partial sums is equivalent to that using the individual hat color, when the distribution departs from uniform, the partial sum seen by the contestants at the end of line would still be extremely close to uniform, no matter what the individual distribution is! Therefore I would expect very similar results to the original setup.

@Ian,
Maybe I misunderstand your illustration, but isn't Z/n a finite cyclic group? Is there any advantage of thinking in terms of cyclic group, e.g., to solve a more complicated version of the problem?