# A Hat Trick of Hat Puzzles

In three new variations of a famous logic puzzle, what are the best strategies for guessing the color of the hat on your head?

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 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. (Update: The solution is now available here.) 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.