The Wizards’ Hats
I collect hats puzzles. A puzzle about hats that I hadn’t heard before appeared on the Konstantin Knop’s blog (in Russian):
The sultan decides to test his hundred wizards. Tomorrow at noon he will randomly put a red or a blue hat — for both of which he has an 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 on a strategy to maximize the number of survivors. Suggest a strategy for them.
I’ll start the discussion with a rather simple idea: Each wizard writes down a color randomly. In this case the expected number of survivors is 50. Actually, if each wizard writes “red”, then the expected number of survivors is 50, too. Can you find a better strategy, with a greater expected number of survivors or prove that such a strategy doesn’t exist?
As a bonus question, can you suggest a strategy that guarantees 50 survivors?
Now that you’ve solved that issue, here’s my own variation of the problem.
Share:The wizards are all very good friends with each other. They decide that executions are very sad events and they do not wish to witness their friends’ deaths. They would rather die themselves. They realize that they will only be happy if all of them survive together. Suggest a strategy that maximizes the probability of them being happy, that is, the probability that all of them will survive.
Cherry:
Are we allowed to take the solution to the wizards, hats, and rooms puzzle (https://blog.tanyakhovanova.com/?p=258) and then, after the wizards have sorted themselves out, they will know the color of their own hat by looking either at their own group members or at the members of the other group?
22 February 2011, 8:13 pmPaul:
My solution is all about the parity of red hats. If the first wizard sees an even number of reds, the he (I am assuming the witch/wizard standard) says red. Else blue. The next wizard does a red hat parity check, and if they match, his hat must be blue. Else his hat must be read. This process continues.
You are guaranteed to save the lives of 99 wizards, and you have a 50/50 shot at the perfect performance, happily saving all lives.
22 February 2011, 10:03 pmTanya Khovanova:
Paul,
They do not know each other’s answers. They have to write simultaneously.
22 February 2011, 10:25 pmAsher:
Since the color of any given hat worn by another wizard gives you no information, I would take that to mean that there is no solution for this problem that does not at least implicitly have the wizards exchange information.
22 February 2011, 10:35 pmPaul:
OK. Interesting. Well, if everyone just writes down the color they see the most of, then a lot of people will be saved, particularly if there is a large majority for one color. An interesting thing happens if its 50/50 for red/blue. Everyone dies!!! In any other case though, more than half are saved. I’ll keep thinking.
22 February 2011, 11:13 pmChrist Schlacta:
So each of the 100 wizards counts all the other hats, if they’re 50/49, they write the opposite colour, otherwise they write the colour they see the most of. This strategy assumes that at 50/50, 100% survival ensues, and at any other ratio, that the number of wizards surviving will correlate with the number of hats of the more frequent colour issued.
23 February 2011, 12:50 amChrist Schlacta:
s/assumes/ensures/
23 February 2011, 12:51 amBill:
In Tanya’s variation, each wizard will see 99 hats, which is an odd number. Therefore, an odd number of these hats will be one color, and an even number of them will be the other color. Each wizard writes down the color of which he sees an odd number. Everyone lives with 50 percent odds.
23 February 2011, 6:56 amPaul:
@Christ Schlacta-
That is like what I said, but seemingly fixes the 50/50 prob, except here’s the trouble. If I see 49/50, it could in reality be 50/50 or it could be 51/49. Can’t tell! In your solution, 51 people die in the 51/49, and in mine they all live. in yours 50 people die in the 50/50 case for me, while you’ve saved them all. In those two cases survivals are 101 for me and 100 for you.
That is literally one up on you.
23 February 2011, 7:49 amPaul:
actually nm. I missed something key. That was a really nice twist!
23 February 2011, 7:53 amOnyebuchi:
For your variation, I have a strategy that gives a 50% chance that they all live, and a 50% chance they all die. Is this the maximum living probability? I’m pretty sure it is, as it’s hard to imagine that all of them living is more likely than any single one of them living. Stop reading now if you don’t want to read the answer:
I figured, their are either an even number red hats, or an odd number of red hats, with equal probability. If everybody assumes the number of red hats is even, they can look around and calculate what their own hat color has to be. If the number of red hats is even, they all will be right. If the number of red hats is odd, they all will be wrong. 50-50 shot.
23 February 2011, 8:43 amEamonn:
They are wizards, can’t they just use magic 🙂
Barring that, Best I can think of is for each wizard to guess whichever colour he sees on most hats except in the case where he sees 50 of one and 49 of another in which case he guesses whichever colour he sees 49 of.
This should give a survival rate of worst case 50% when the hat distribution is even and in all other cases the survival rate would be equal to the most common hat colour.
23 February 2011, 10:37 amBrenda:
So much depends on how close the ratio of red:blue hats is to 1:1. If we allow them to self-select by sorting each other, then we can get to 100%, but that certainly is an implicit exchange of information.
If there are exactly 50 red hats and 50 blue ones, the solution is simple, as the color of a wizard’s hat can be derived from the colors of the others. Choosing the color for ones own hat which is in the minority of what they see would, if the hats are truly chosen randomly, give a better than 50% chance of getting their own hat color correct.
23 February 2011, 10:58 amFelix:
That was a really really mean one.
I have spent time designing strategies and computing the associated expectation… Only to find out, in each case, that I only managed to get N/2…
There is no way to achieve better (or worse) expectation! That is, if the hats are assigned to wizards independently.
To see this: whatever the strategy of a given wizard, be it deterministic or random, it cannot depend on the color of his own hat, so it will always be right with 0.5 probability, and wrong with 0.5 probability! So individually speaking, each wizard will survive with probability 0.5. Taking the sum, that yields an expectancy of N/2, whatever their strategy.
Surprisingly, though, there is a strategy that will guarantee exactly N/2 survivors.
23 February 2011, 12:13 pmFirst divide in two groups of N/2: those who will by default say red, those who will by default say blue. Then each wizard counts the number of red hats, and if the parity is odd, changes his default choice to the opposite. This should achieve N/2 survivors, in each hat distribution situation. (this can be proven by induction on the number of red hats)
Brenda:
Nah, that doesn’t work. If a wizard sees more than 50 of any color hat, he should put down that color. That will guarantee that at least 50% of the wizards survive.
23 February 2011, 12:22 pmBrenda:
… and continuing in this train of thought, where the strategy is to guess your own hat is the color of the majority you can see, if the division IS exactly 50:50, everyone dies. Since choosing the LEAST popular doesn’t fail in this situation, this brings the survival rate slightly above 50%, and the “choose most” strategy slightly below 50%, overall.
23 February 2011, 12:51 pmBrenda:
Hate to keep spamming your blog. I really should be doing work.
Okay, the day before, the wizards get together and number themselves from 0 through 99.
When they receive their hats, they look around and if their number is less than the number of red hats they see, they write down “red”, otherwise they write “blue”.
This should beat random chance and doesn’t require the implied condition that there are exactly 50 red hats and 50 blue hats.
23 February 2011, 1:28 pmpruwyben:
Choosing the 49 color in a 50/49 situation yields a problem: if it is indeed a 50/50 split, all will live, but if it is a 49/51 split, the ones on the 51 side will see 49/50, choose the 49 color and die, and the others will see 51/48, choose the majority, and die. Since 51/49 splits occur about twice as often as 50/50 splits, this will give a more than 50% death rate.
23 February 2011, 1:46 pmBrenda:
If the wizards get their hats one at a time, and have a chance to move around after they get their hat, then wizard #2 stands to the left of wizard #1 if #1 is wearing a blue hat, to the right if #1 is wearing a red hat. This continues on until the last wizard has made his choice, at which point wizard #1 moves to stand by his right or left depending on his hat color, and all wizards write down the correct color of their own hat based on the position of their partner.
This is really an implicit sharing of information.
23 February 2011, 2:11 pmCherry:
Here’s my attempt:
The wizards decide ahead of time to only count red hats. If the number of red hats that a wizard sees is odd, s/he stands in one corner. If the number of red hats that a wizard sees is even, s/he stands in another corner. This will ensure that the reds and blues are separated, since a blue-hat-wearer will count N red hats while a red-hat-wearer will only count N-1 red hats.
After all the wizards have been split up, any wizard can deduce the color of his/her own hat by looking at their group members or at the members of the group
23 February 2011, 7:06 pmJenny:
Sadly, Brenda and Cherry, “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.”
At first I thought this was similar to a problem about monks that I saw before; however, that one permitted the monks ears to turn red. 🙂
23 February 2011, 7:49 pmVincent:
It can be proved by pairing that any deterministic strategy has an expected survival rate of exactly 50%: Consider wizard n, who is using a deterministic strategy. For every arrangement of hats where he survives, there is exactly one corresponding arrangement where he dies. Specifically, the corresponding arrangement is the one where wizard n’s hat color is switched. All arrangements have the same probability, so the expected survival rate of wizard n is 50%. The situation is symmetric over all the wizards, so the total expected survival rate is also 50%.
This proof doesn’t immediately work for probabilistic strategies.
23 February 2011, 9:44 pmK:
@Vincent I think your argument extends naturally to probabilistic strategies (which can be written as a weighted average of deterministic strategies).
24 February 2011, 11:11 amBrenda:
For the best chance that they all survive to be happy together or die together, I propose an escape attempt. If they succeed, they all live. If they fail, they all die.
24 February 2011, 2:17 pmVishal:
Tanya, I have a question:
>>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.
Do every wizard have to write down the color of his own hat at the same time? Or does the sultan goes from one wizard to the next?
If the latter is true, then after the first iteration, the remaining 99 wizards can infer a lot from the 1st wizard’s fate.
24 February 2011, 3:09 pmJonathan:
the “see 50” case is challenging.
If they don’t see 50, they are in 1 of 4 situations:
They see 50 red and 49 white. Their hat is red. The 49 whites are writing down red, and all will be wrong.
They see 50 red and 49 white. Their hat is white. ==
They see 49 red and 50 white. Their hat is red.
They see 49 red and 50 white. Their hat is white. The 49 reds are writing down white, and all will be wrong.
What if, “see 50 or 51” = write the opposite, and
See at least 52, write down the majority?
Well, that leads to disaster at 52-48.
Each time we add one “opposite” case, we push the disaster further and further away. But if we always “write the opposite” then we will get some pretty small (yet all positive) results, down to 100 red.
How can we measure which is better, going with opposites, or going with majority, and losing 50/50?
26 February 2011, 2:31 amVincent 2:
I feel that the second puzzle is much more interesting than the first. In the first puzzle it is clear that each individual has probability 1/2 of surviving. There are various ways to make this precise, I partcicularly like the comment of the other Vincent above. Now suppose that exactly one of the wizzards is called John. The expected number of living Johns on the next day is 1/2 as John dies or survives with equal probabillity. It is a well know, although counterintuitive, fact that the total expected number of survivors is the sum of all these expected numbers of surviving individuals, NO MATTER how the probablitiy distributions of wizzard John surviving and wizzard Jack surviving are interdependent or not.
Now for the second puzzle. Since each wizzard has probabillity 1/2 of surviving, it is clear that the probability of them all surviving cannot exceed 1/2. The miracle is that with a simple strategy (which I will not spoil) this upperbound CAN be attained! In spite of the simplicity of the solution I still find this a bit of a miracle, as on first glance you would expect a probability of (1/2)^100 of all surviving.
Tanya’s nice formulation of the problem alows for a different way to phrase the miracle: suppose that the wizzard agree on following a strategy that maximizes the probabillity of all of them surviving, but some of them are secretly thinking “screw it, if I can improve my own chances of survival by changing strategy last moment, I will do so, no matter how much lives it costs.” Then all these wizzards will find out after some contemplation that there is nothing they can do to make their individual chances better and they might as well stick to the strategy that is best for the collective.
5 March 2011, 6:32 amVincent 2:
I knew the second puzzle before in a form where the sultan will kill ALL wizzards, unless ALL of them guess the color of their own hat right. In that case there is no incentive to deviate from the strategy. I like Tanya’s version much better because now the wizzard should do some reasoning to see that there is no point in not sticking to the stategy.
On the other hand: the way the wizzards are portaited here they wouldn’t even dream of putting theire own interest over that of the group. We can take this view of wizzard psychology even further and assume that they don’t care if they live or die, as long as all of them do the same. Thus ariving at a new riddle where they want to maximize the probability of either all of them surviving or all of them dying, rather than the probabillity of all of them surviving.
Of course in this riddle the solution with leads to the highest probabillity of all of them surviving (1/2) gives also the highest probabillity of all wizzards ending up with the same fate (1). So the real new riddle is:
Can you cook up a new hat-riddle where maximizing the probabillity of all of them surviving does not yield the highest probabillity of alle of them ending up the same way?
5 March 2011, 6:44 amCarlos Cabrera:
The average survival is not 50% but 75% with the majority algorithm (extended to real numbers, of course).
There are 100 cases, but 101. (0, 100) / / (50-50) / / (100, 0).
Whenever they can not exchange information will be a deterministic algorithm. There are only two possible income: (reds – 1, blues) and (reds, blues – 1). Therefore all of the same color wizards choose the same color. Therefore the optimal solution is that the wizards from both colors choose the majority color.
Applying the algorithm of the majority would survive an average of 74,752 .. wizards.
(((100 + 51) / 2.) * (50 (red majority) + 50 (blue majority)) + 0 (tragic middle)) / 101 (total cases)
I’m writing the proof that is impossible to avoid total catastrophe (I can barely write in English).
Best regards
24 March 2011, 7:56 amCarlos Cabrera:
s/There are/There are not/
24 March 2011, 7:58 ammashplum:
Pair the wizards off in a buddy system. At the signal each wizards writes down his buddy’s color and signs his buddy’s name.
3 April 2011, 8:44 pmBrett:
To guarantee exactly 50 wizards’ survival:
The parity of the total number of red hats will be either 0 or 1.
The wizards divide evenly into two groups:
a) those who will work off of the assumption that the parity is 0
b) those who will work off of the assumption that the parity is 1
Note that exactly one of the groups is correct. All of the wizards in the group whose assumption is correct will live, while the others will die.
For example:
There are 22 total red hats, and 78 total blue hats. Note that the parity of red hats is 0.
Consider each wizard in group a). Each and every one of these 50 wizards sees one of two things:
– If he has a red hat, he sees 21/78. As a member of group a), he assumes that the total parity of red hats is 0. This means his hat must be red to bring the total red hats to 22. He guesses red and lives.
– If he has a blue hat, he sees 22/77. As a member of group a), he assumes that the total parity of red hats is 0. This means his hat must be red to keep the total red hats at 22. He guesses red and lives.
Consider each wizard in group b). Each and every one of these 50 wizards sees one of two things:
30 January 2012, 3:20 pm– If he has a red hat, he sees 21/78. As a member of group b), he assumes that the total parity of red hats is 1. This means his hat must be blue to keep the total red hats at 22. He guesses blue and dies.
– If he has a blue hat, he sees 22/77. As a member of group b), he assumes that the total parity of red hats is 1. This means his hat must be blue to bring the total red hats at 23. He guesses blue and dies.
Brett:
And as for the second variation, there is a 50% chance of all the wizards surviving if you assign all the wizards in either group a) or group b).
30 January 2012, 3:22 pmReila:
For the second problem:
Every wizard sees x red hats and 99-x blue, one of these is even and one odd. In reality the number of red hats could be either even or odd. We work with the assumption that the number of red hats should be even. Every wizard chooses his or her hat colour so that the total number of red hats is even. Thus we have a 50% chance of saving everyone and 50% chance of having everyone killed.
1 July 2013, 11:08 amTanya Khovanova’s Math Blog » Blog Archive » Hat Puzzle: Create a Distribution:
[…] 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 […]
4 June 2014, 9:33 am