How Many Hats Can Fit on Your Head?
Lionel Levine invented a new hat puzzle.
The sultan decides to torture his hundred wise men again. He has an unlimited supply of red and blue hats. Tomorrow he will pile an infinite, randomly-colored sequence of hats on each wise man’s head. Each wise man will be able to see the colors of everyone else’s hats, but will not be able to see the colors of his own hats. The wise men are not allowed to pass any information to each other.
At the sultan’s signal each has to write a natural number. The sultan will then check the color of the hat that corresponds to that number in the pile of hats. For example, if the wise man writes down “four,” the sultan will check the color of the fourth hat in that man’s pile. If any of the numbers correspond to a red hat, all the wise men will have their heads chopped off along with their hats. The numbers must correspond to blue hats. What should be their strategy to maximize their chance of survival?
Suppose each wise man writes “one.” The first hat in each pile is blue with a probability of one-half. Hence, they will survive as a group with a probability of 1 over 2100. Wise men are so wise that they can do much better than that. Can you figure it out?
Inspired by Lionel, I decided to suggest the following variation:
This time the sultan puts two hats randomly on each wise man’s head. Each wise man will see the colors of other people’s hats, but not the colors of his own. The men are not allowed to pass any info to each other. At the sultan’s signal each has to write the number of blue hats on his head. If they are all correct, all of them survive. If at least one of them is wrong, all of them die. What should be their strategy to maximize their chance of survival?
Suppose there is only one wise man. It is clear that he should write that he has exactly one blue hat. He survives with the probability of one-half. Suppose now that there are two wise men. Each of them can write “one.” With this strategy, they will survive with a probability of 1/4. Can they do better than that? What can you suggest if, instead of two, there is any number of wise men?
Share:
Jonathan:
I find your variation more appealing than the original. And, I should add, I generally avoid hats problems altogether.
But in this case it does us no good if most are right. It is all, or everyone dies.
So let’s assume that the number of blue hats is a multiple of 3. So, if a wise man sees a multiple of 3, he guesses 0. If he sees one more than a multiple of 3, he says two. And if he sees one less than (or two more than) a multiple of 3, he says one.
What is the chance the actual number of hats is a multiple of 3? At least 1/3, improving the chance of all surviving.
Why “at least” 1/3? Consider the case where there are 3 wise men. There can be 0, 1, 2, 3, 4, 5, or 6 blue hats. In 3 of 7 cases, there is a multiple of 3. Consider 4 wise men. 0,1,2,3,4,5,6,7,8. Three out of nine, or exactly one third. Five wise men give us 4/11. 6 give us 5/13. And 3n yields (3n-1)/(6n+1)…
8 April 2011, 8:50 pmBill:
First problem:
Every wise man should look at the first number where everyone else is blue, and choose that number.
This strategy will be successful 1 in 101 times.
I say this because there is one way for a horizontal row of hats to be all blue, but 100 ways for them to be 99 blue and one red. Whichever of those 101 patterns appears first in the random sequence will determine success.
9 April 2011, 3:09 pmThird Xamuel.com Linkfest:
[…] Khovanova: How Many Hats Can Fit on Your Head?, Subtleties of […]
10 April 2011, 11:00 amChrist Schlacta:
there is no way to guarantee all wise men survive in the first question. However, if we arrange hats in a 2d array, such that it can be represented as hats[wiseman, n]. and our wiseman examines all wisemen at hats[,n], the more red hats he sees, the higher the probability his will be blue, and vice versa.
This breaks down when we examine how the sultan applies hats. if he is applying hats one row at a time (incrementing n only), he is more likely to apply a row of all one colour or another colour. if we see wisemen-1 hat of the desired colour, we should assume our hat is the same colour. however, if the sultan places infinitely many hats on each wiseman, then moves to the next (incrementing wisemen only), we know statistically that this doesn’t apply. therefore, we should assume that the more hats of a given colour in the same row, the more likely that our hat is a different colour, and we should assume our hat is a different colour.
What we must remember though, is as the number of hats on our wisemen approaches infinity, our wisemen approach 0. the weight of the hats pushing down on our wisemen would crush them sometime after 200 hats.
Reasoning: world record for most hats worn at once is 22, world record for most shirts worn at once is jsut over 200, which resulted in medical complications due to gravity and material weight.
11 April 2011, 2:03 amSources: https://urdb.org/world-record/hats-worn/746 https://www.youtube.com/watch?v=H7NsNpSkxbc
Tanya Khovanova:
Jonathan,
For 1 wise man, the answer is 1/2, which is better than your 1/3. I would like someone to consider the case of 2 wise men.
12 April 2011, 3:23 pmFelix:
Let me consider the sevond problem
For two wise men, the best I could achieve was 6/16, essentially using the idea of Jonathan, with a twist.
The strategy would be to count the hats of the other wise man, and complement to 2. That is, bet on the probability that the total number of hats is 2, which is 6 / 16 (binomial random variable with parameters (4, 1/2)).
For n wise men, the same strategy allows to save them with probability strictly more than 1/3. Indeed, take the distribution of the remainder of the total number of hats modulo 3, it can take values in {0,1,2}, so at least one of the three has probability strictly more than 1/3 (beacause they are sum of biinomial probabilities with a denominator that is a power of 2, so none of them can be exactly 1/3), then choose it and stick to it.
The strategy is then to count the hats of the other wise men, and complement to the chosen remainder (modulo 3). It is essentially Jonathan’s solution.
However, I have not proven it is the best solution.
13 April 2011, 2:34 amI have no clue about the first problem, nor how it precisely relates to the second one.
JBL:
Exhaustive computer search confirms that for 2 wizards with 2 hats each, in the best case they win with probability 3/8 = 6/16.
14 April 2011, 7:57 pmJBL:
Okay, another couple of comments:
Consider the following variation of Tanya’s game. We have n wizards, and each gets one of the numbers {0, 1, 2} pasted on his or her forehead, with equal probability. The goal again is for every wizard to state the number pasted on his or her own head. In this case, it’s easy to see that 1/3 is an upper bound on the probability of success: Wizard 1 can only be right 1/3 of the time, so all wizards can only be right 1/3 of the time at most. And the strategy “guess that the total sum is divisible by 3” achieves this bound exactly. So, in the problem we’re actually given, any ability to beat 1/3 comes entirely from the lack of uniform distribution. (And this makes some intuitive sense: anything that causes some concentration helps our poor wizards.) Similarly, this gives us a hard upper bound of 1/2 for the wizards’ probability of winning under any strategy.
On the other hand, it’s not clear to me whether the fact that we have the hats on each wizard’s head in some particular order matters; I conjecture that the optimal solution in this puzzle is the same as if each wizard has one of the numbers {0, 1, 2} pasted on his or her forehead, where 0 and 2 appear with probability 1/4 and 1 appears with probability 1/2. Is there an easy proof of this?
14 April 2011, 8:17 pmJames:
I would like to know the answer to Lionel’s problem! The best I can do is a strategy that succeeds with probability about 1/(log_2 n) when there are n wise men, for large n.
Namely, let A_i be the number of the LOWEST hat on the head of wise man i which is blue. Let S_n be A_1 + A_2 + … + A_n. Fix some constant c_n.
Each wise man will guess on the basis of the following:
(i) S_n is a multiple of c_n.
(ii) All the A_i are at most c_n.
For man i, who can see all the other A_j but not A_i itself, there is at most one value of A_i which is consistent with (i) and (ii). If there is one, then man i writes down this number. When (i) and (ii) both hold, each man has written down a number corresponding to a blue hat on his head.
The A_i are i.i.d. geometric with parameter 1/2. If c_n – log_2 n goes to infinity as n goes to infinity, but not too fast, then the probability of event (ii) goes to 1 as n goes to infinity, and the probability of event (i) is approximately 1/c_n, and the two are approximately independent. So they succeed with probability around 1/c_n. (All this can be made more precise).
So, this gives a success probability on the order of 1/(log_2 n). However, it’s actually succeeding at a tougher task (name the LOWEST blue hat on your head, rather than naming ANY blue hat on your head). So far, I haven’t seen how to take advantage of the easier task….
For n=2, the best I can see is that man 1 guesses A_2 and man 2 guesses A_1. Then they succeed whenever A_1=A_2, which has probability (1/2)^2 + (1/4)^2 + (1/8)^2 + … = 1/3. Again, it actually succeeds in the tougher task of finding the lowest blue hat.
22 April 2011, 12:21 pmLionel Levine:
Dear James, I would also like to know the answer! When I wrote to Peter Winkler about this problem last year, he came up with a solution very similar to yours: the wise men choose to assume that S_n is congruent to n-1 mod c_n. David Wilson worked out the optimal choice of c_n to be about lg n + lg lg n – lg lg lg n, which gives success probability about 1/(lg n). Ori Gurel-Gurevich came up with an argument for why the wise men cannot do better if required to point to their lowest blue hat. But for the original problem I do not even know how to improve on the trivial upper bound of 1/2 probability of success.
Now I’ve told you everything I know.
23 April 2011, 5:34 pmStudent:
For the second one, they will look at all the hats, counting the number of blue hats. the number of blue hats modulo 3 will be either 0, 1 or 2. before hand, they all decide upon which they will count for, and they all assume that the number of blue hats on their head will bring the total number of blue hats to the desired modulous. this insures that they will either all be right, or all be wrong, and is about a 1/3 chance of them getting it right, (with the most likely mod to be 1, since it occurs the most frequently)
26 April 2011, 9:00 amJoseph:
So, I just found my way over here from Cory Stevens’s “Standard Hat Rules Apply” blog. And it looks like the discussion over here on this problem is over, so chances are my comment won’t be read by anyone. C’est la vie.
I am with James when there are only 2 wise men. I don’t think they can do any better than for each to guess the number of the other wise man’s lowest blue hat. But as for how to extend this strategy to multiple wise men, I have the following variation.
As before, let A_i be the number of the lowest hat on wise man i’s head which is blue. But rather than numbering the hats starting from 1, number the hats starting from 0. For example, say the 5th wise man has two red hats on the bottom, followed by a blue hat. Then A_5=2, not 3.
Now, rather than letting S_n be the sum of the A_i’s, let S_n be the NIM-SUM of the A_i’s. That is, write all the A_i’s in binary, and add without carrying. All the wise men make their guesses under the assumption that S_n=0.
This is identical to James’s strategy for the case of 2 wise men. But I’m not yet sure how it does for multiple wise men; summing the probabilities seems to be a tough task. I needed Mathematica to get a probability of 0.276205 for 3 wise men, and that’s only marginally better than Bill’s 1/(n+1) strategy. For all I know, my strategy might be worse than Bill’s in the long run.
I’ll keep thinking about this.
29 April 2011, 11:00 amAnimesh:
Assuming probability of blue hat is 1/2. The expected sum is number of wise men….or n – number of blue hats(base 3).
30 April 2011, 7:15 amThat way probability is always > 1/3,and goes to 1/3 as n goes to infinity
Stan Wagon:
I’ve programmed the strategy attributed to Winkler and “James” above and there are some surprises.
1. For n = 2 or n = 3, no choice of c (the modulus) or target sum s (which is n-1 in L Levine’s post above) yields a result better than the basic 1/(n+1) strategy.
2. For n = 4: using c = 3 and s = 1 yields a prob. of 101/512, a little greater than 1/5.
And here’s a surprise: Suppose the n wise men agree on an integer i chosen from 0,1,…,n-1, and agree to choose the first index j so that, among the n-1 hats they see, there are exactly i BLACKs. So the basic strategy has i = n-1. It appears that this strategy succeeds with prob. 1/(n+1), the same as the all-black strategy. I learned this from simulations, and some small cases, but I do not have a proof. There must be a simple proof.
Finally, there is a simple recursion that allows one to compute F(n,c,s) — the NUMBER of good hat assignments for which the best-known strategy succeeds, as a rational number for any n, c, s. One just recurses on n. It is:
F[n, c, s] = Sum[ 2^(c-k) F[n-1, c, Mod[s-k,s]] , {k, 1, c}]
F[1, c, 0] = 1
F[1, c, s] = 2^c-s
The probability of course is just F / 2^-(n c).
AND: I used the recursion to find the best c and s for n up to 5000. The evidence does not support the view that a target sum s = n -1 is best. I see no pattern in the best value of s.
1 April 2014, 3:49 pmLuke Pebody:
For the second problem, I believe I can prove that the solution of everyone answering as if the total number of hats is n (mod 3) is optimal.
Idea 1: We do not lose generality by assuming that the strategy is non random.
Idea 2: Instead of putting red/blue hats on their heads, we can have him put hats labelled 0,1,2,3 on their heads with equal probability, and each person has to guess 0, 3 or (either 1 or 2).
Idea 3: The set of labellings whereby all the chumps guess correctly has the property that it is a subset of [4]^n such that for any two elements that differ in exactly one location, the two elements are labelled 1 and 2 in that location. Let us call such a labelling special.
Idea 4: Given a special labelling, the chumps can assume they are labelled specially, and they will all be correct whenever they are. Therefore the optimal probability is equal to (1/4)^n times the size of the largest special labelling. Let F(n) denote the size of the largest special labelling.
Idea 5: Given a special labelling X for n chumps, let X_0, X_1, X_2, X_3 denote the labellings possible for chumps 1, 2, …, n-1 given that chump n is labelled 0, 1, 2 or 3. Then X_0, X_1, X_2 and X_3 are special labellings for n-1 chumps, and they are all disjoint, except possibly X_1 and X_2.
Idea 6: If the larger of X_1 and X_2 has k elements, then X_0 and X_3 can have between them at most 4^(n-1)-k elements, so the size of X is at most (4^(n-1)-k)+k+k=4^(n-1)+k. Thus, since k <= F(n-1), the size of X is at most 4^(n-1)+F(n-1). Since this holds for all special labellings X for n chumps, F(n) <= 4^(n-1) + F(n-1).
Idea 7: Thus, since F(1) = 2, F(n) <= 4^(n-1) + … + 4 + 2 = (4^n + 2) / 3. So the optimal probability is at most 1/3 + 2/(3 x 4^n)
Finally, I show that the strategy of assuming the number of blue hats is equivalent to the number of people (mod 3) achieves the upper bound from idea 7.
Idea 8: Let P(x) = sum_{i=-n}^{i=n}P(n+i blue hats)x^i. Then by Binomial Thm, P(x)=(1+x)^{2n}/(4x)^n.
Idea 9: If v and w are the nontrivial cube roots of unity, then for all integers i, 1^i + v^i + w^i = 3 if i is divisible by 3, and 0 otherwise. Thus P(number of hats is equivalent to n mod 3) is (P(1) + P(v) + P(w)) / 3.
Idea 10: P(1) = 1 and for x=v,w, 1+x is -x^2, so (1+x)^(2n)=x^(4n)=x^n, so P(x)=1/4^n. Thus the probability is equal to 1/3+2/(3*4^n), which by idea 7 is optimal
11 April 2014, 11:50 amJack Collins:
There is a strategy between 1/(n+1) and the 1/log(n), which seems to go as 1/sqrt(n):
Take the sum of the numbers of the lowest black hat on everyone else’s head, call it q. If possible, pick the number x on your head to make q + x = 2n (this is the most likely value of the sum of the number of the lowest black hat over all prisoners). I haven’t gotten a nice analytic form for the large n behaviour, but it matches very closely with 1/(5 n^(1/2)) when plotting in mathematica.
2 July 2014, 11:26 amOpen problem session of HUJI-COMBSEM: Problem #3, Ehud Friedgut – Independent sets and Lionel Levin’s infamous hat problem. | Combinatorics and more:
[…] problem was presented in this 2011 post on Tanya Khovanova’s Math Blog. Tanya also offered a new variant of her own. It was also […]
12 December 2020, 11:07 amBabette Galfayan:
I like your blog. Its one of the best blogs online
23 July 2021, 5:03 am