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:
Konstantin Knop:
> 100 wizards will survive with probability 0.25 and 50 wizards will survive with probability 0.5.
100+50 = 150 ??
4 June 2014, 10:45 amKonstantin Knop:
> 100 wizards will survive with probability 0.25 and 50 wizards will survive with probability 0.5.
May be, 75 wizards will survive with probability 1/3 and 25 wizards will be guaranteed ti survive?
4 June 2014, 10:48 amPer:
The wizards are not very good, if they can’t figure out their own hat color with some magic…
13 June 2014, 12:16 pmGeorge R.:
Just a linguistic remark. It’s interesting that in the English language the word “wizard” sustains its etymological connection with “wise”.
14 June 2014, 12:46 amOf course ,today one using this term mainly means some kind of magician (black or white magic,or how they call all these nonsense..)and not a wise man. In my mother-language (Greek) the ancient (Persian origin) word “magos” (Mάγος) which gave the Latin magus-magi and the modern magicienne(fr.) ,magician, e.t.c originally meant “wise man (of the east: Babylonian,Persian)” and not “Μagician”. This meaning is still existing in the linguistic tradition of the church, where the 3 wise men who brought gifts to baby Jesus are called the Magi (Οι Μάγοι).
Ι wonder if the difference in meaning exists also in other languages. For example I know the Russian маг (mag) of obvious etymology, and the word волшебник (balsέvnic). Perhaps Tanya,or some other Russian speaking friend could elaborate?
P.s Sorry for the irrelevant and highly unmathematical comment Tanya! 🙂
Tanya Khovanova:
George R.
Thank you for your comment. In Russian hat puzzles the word that is used is ‘mudrets’, which means wise man or sage.I do not actually know which word to use in English when I translate.
14 June 2014, 7:16 amThomas:
3) All wizards suppose that the number of red hats is divisible by four and answer correspondingly. If it is true (25% chance) all 100 will survive.
There are cases where it’s obvious that it can’t be true (when seeing one or two modulo four red hats). In this case, assign 50 wizards to believe the number of red hats to be even and 50 wizards to believe they are odd. So 50 wizards will survive with 50% chance.
4) Assign 75 wizards to believe the number of hats is even, and 25 to believe the number of hats is odd.
5) I don’t think so. My best argument (there must be a better one) is that we have 2^100 different possible allocations, and 2/3 is not a multiple of 1/2^100, so we cannot choose an event that has exactly 2/3 probability.
6) Assuming n groups of wizards of size w_i who should survive with probability p_i, we have at least
sum(w_i*p_i) <= 0.5
p_i is a multiple of 1/2^100.
but probably there are more restrictions.
24 June 2014, 5:45 amA hat puzzle | Blogarithm:
[…] heard about this problem from Tanya Khovanova. She also gives an argument that the strategy is optimal. No matter how the hats are distributed, […]
23 August 2023, 4:45 pm