A Hat Trick of Hat Puzzles

Hat puzzles are a delightful genre of logic puzzles whose number and diversity have swelled as enthusiasts concoct variation upon variation. The general theme of hat puzzles goes as follows: There are a bunch of prisoners who have been incarcerated by an evil tribe. The captors tell the prisoners that later in the day, they will participate in an execution ceremony. They will all be placed in a circle or in row, and a hat of some color will be placed on each prisoner’s head. Each will be able to see the color of the hats atop the heads of the others (or the people ahead of them if they are in a row) but will not be able to see the color of the hat that is on their own head. Each prisoner will be asked, either simultaneously or one after the other, to state aloud the color of the hat that he thinks is on his head, based on some instructions provided beforehand and on what the other prisoners said. If a prisoner gives the wrong answer, he or she, or perhaps all of the prisoners together, are executed. If they all guess correctly, the prisoners are freed. Such a game would usually be a grisly variation of Russian roulette, but fortunately, there almost always happens to be a friendly jailer around who allows the prisoners to confer before the event to decide on their best strategy in a cooperative manner. The goal is to come up with a strategy that allows as many of the prisoners to be freed as possible.

As you can see, there are enough places inside this template where different details can be inserted — the number of prisoners, the number of hat colors, whether they have to announce their hat color one at a time or all together, whether they are allowed to pass, whether they going to be freed together or individually, whether the game is competitive or cooperative or adversarial, and so on — allowing for a great deal of variation. The charm of such hat puzzles is that when you hear the puzzle, the first thought that comes to mind is that the prisoners, or most of them, are probably done for. The odds seem stacked against them. But there is almost always a clever way to save most of them, or sometimes even all of them, that is quite unexpected and elegant. Of course, there are some hat puzzles that have extremely sophisticated solutions or are still unsolved as the number of prisoners is increased. Some such puzzles are a subject of ongoing mathematical research and doctoral theses. One class of solutions for some hat puzzles is linked to error-correcting Hamming codes, which are used in data transmission. Don’t worry, none of our puzzles require anything more than high school mathematics, and in fact one of them is based on a puzzle invented by a ninth-grader. So do try your hand at them — and don’t give up too easily. The ideas behind them are quite clever and beautiful.

We have three such hat puzzles for you in this month’s Insights column. In order to modernize the theme, we are dispensing with the evil-tribes scenario and setting it instead in a modern reality-TV show where the hat-color guessers are game-show contestants, given their instructions by the host and competing for thousands of dollars.

The three hat puzzles below are arranged roughly in order of difficulty. In all these cases, the best strategy earns the contestants more than random guessing — sometimes quite a lot more. The first puzzle is a classic.

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?

Puzzle 2: 10 Hats, 3 Colors, 1 Bug

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 this plan and adapt his hat-placement choices so as to counter any attempts to win big. The contestants know this but cannot do anything about it. During the game, the contestants are lined up single-file, and 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 those 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 speak it only once. All contestants hear what each one 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 that the contestants win? What is the expected amount?

Puzzle 3: 10 Hats, 3 Colors, Pass Allowed, Forfeiture on Wrong Guess

As in Puzzle 2, there are 10 contestants and hats of the same three colors, with the contestants lined up in a row, 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 the wrong color, 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?

That completes our hat trick, which, as you probably know, is a term used to signify three of anything in various sports. The term first appeared in 1858 in cricket, to describe a bowler (pitcher, in baseball parlance) who took three wickets (retired three batters) with three consecutive deliveries (pitches). Apparently, fans held a collection for the player, H. H. Stephenson, and presented him with a hat. We have come a long way from a winning a modest prize of a hat for the hat trick to winning a sum of hundreds of thousands of dollars! Unfortunately, we cannot match the fantasy game show of our puzzles — the only thing we can offer is a Quanta Magazine T-shirt. And the joy of puzzle-solving.

Happy puzzling — and may the insight be with you!

Editor’s note: The reader who submits the most interesting, creative or insightful solution (as judged by the columnist) in the comments section will receive a Quanta Magazine T-shirt. And if you’d like to suggest a favorite puzzle for a future Insights column, submit it as a comment below, clearly marked “NEW PUZZLE SUGGESTION” (it will not appear online, so solutions to the puzzle above should be submitted separately).

Note that we will hold comments for the first day to allow for independent contributions.

Update: The solution has been published here.