## Hat Puzzle: Create a Distribution

Here is a setup that works for the several puzzles that follow it:

The sultan decides to test his hundred wizards. Tomorrow at noon he will randomly put a red or a blue hat—from his inexhaustible supply—on every wizard’s head. Each wizard will be able to see every hat but his own. The wizards will not be allowed to exchange any kind of information whatsoever. At the sultan’s signal, each wizard needs to write down the color of his own hat. Every wizard who guesses wrong will be executed. The wizards have one day to decide together on a strategy.

I wrote about puzzles with this setup before in my essay The Wizards’ Hats. My first request had been to maximize the number of wizards who are guaranteed to survive. It is easy to show that you cannot guarantee more than 50 survivors. Indeed, each wizard will be right with probability 0.5. That means whatever the strategy, the expected number of wizards guessing correctly is 50. My second request had been to maximize the probability that all of them will survive. Again, the counting argument shows that this probability can’t be more than 0.5.

Now here are some additional puzzles, including the first two mentioned above, based on the same setup. Suggest a strategy—or prove that it doesn’t exist—in which:

- 50 wizards will be guaranteed to survive.
- 100 wizards will survive with probability 0.5.
- 100 wizards will survive with probability 0.25 and 50 wizards will survive with probability 0.5.
- 75 wizards will survive with probability 1/2, and 25 wizards survive with probability 1/2.
- 75 wizards will survive with probability 2/3.
- The wizards will survive according to a given distribution. For which distributions is it possible?

As I mentioned, I already wrote about the first two questions. Below are the solutions to those questions. If you haven’t seen my post and want to think about it, now is a good time to stop reading.

To guarantee the survival of 50 wizards, designate 50 wizards who will assume that the total number of red hats is odd, and the rest of the wizards will assume that the total number of red hats is even. The total number of red hats is either even or odd, so one of the groups is guaranteed to survive.

To make sure that all of them survive together with probability 0.5, they all need to assume that the total number of red hats is even.

Share: