Math puzzle with a surprising answer
16 mathematicians are imprisoned by the evil emperor. They are told that in the morning they will each be assigned a hat, either white or black. Each hat is assigned randomly (50/50) and independently. Each mathematician will be able to see everyone else’s hat but not their own. After one minute to observe the hats, they will simultaneously be sent back to their private cells where they have to guess the color of their own hat. If a single mathematician guesses incorrectly, they will all be executed. If all 16 guess correctly, they go free.
What is the probability that the mathematicians will be set free, and how should they guess?
If you’d like a hint, look at this problem. Thanks to Dwight for suggesting more complex problems in that spirit; if this isn’t hard enough I’ll add another twist next week.
— Max
Max Schireson's blog 
I’ll start off with a partial solution: The equi-partitioned distribution (8 black 8 white hats) is the most likely distribution (under the assumption the hats are assigned randomly and independently). So each mathematician looks around and counts how many white hats and black hats he sees. If he sees fewer white hats, he guesses white for his own hat; if he sees fewer black hats, he guesses black. When the hats are in fact equi-distributed, then all mathematicians will guess correctly and they will be freed. There are 2^16 possible distributions. I think (16 choose 8) of them are equi-partitioned so a lower bound is that they will be freed (16 choose 8) / 2^16 times = 12870 / 65536 = ~20%. This scheme seems to systematically fail when the hats are not split 8 and 8. I imagine there are some improvements you can make in such cases.
This is certainly better than them each guessing at random independently (well under 1%) but you can do quite a bit better. Good start though!
— Max
Each mathematician guesses the xor of all the other hats. If the xor of all hats is zero, everyone lives, otherwise everyone dies. p = 50%
Very good. Easiest to think of it as guessing even/odd number of black hats.
Stay tuned for next week’s puzzle, it has a twist which makes it a little harder…
— Max
The question doesn’t specify the size of the pool the hats are drawn from. If there’s an infinite pool of black and white hats, then it can’t be anything but 1 / 2^16 since the assignment has no “memory” — it’s the same as flipping a coin. If you’re drawing from a fixed buffer of hats, then with 16+N hats in the buffer, the chances of each correct guess should be the minimum 50%, plus the combined odds on a 50/50 shot for each extra hat in the pool, which gets diluted the more hats there are in the pool, and eventually approaches zero. Or 100% minus the odds of guessing wrong once in N times. This is… a guess… I’m an alcoholic dammit, not a doctor! But I think it should be (1/2)+(1/2^(N+1)) per guess, and that figure to the 16th for all of them.
It is an infinite pool. But it is not 1/2^16.
I was a bit lost by your discussion around the limited pool of hats but that is not the situation.
— max
Okay. So maybe this is a semantic issue with the way the question was phrased — and if so, maybe clarification is in order? But with an infinite pool of hats, the next variant is always a 50/50 shot. The prior distribution of hats has no bearing on which hat you’re wearing…just like the prior spins on a roulette wheel have no bearing on which color will come up next. The odds of choosing the correct next color on a roulette wheel 16 times in a row are (18/38)^16.
If the pool of hats is infinite, that is if there’s no reason to believe that the 16th hat (the one you’re wearing) is part of a limited subset, then the entire first part of the premise can be thrown out. In other words, it does absolutely no good for anyone to look at anyone else’s hat — at best that would only establish that distribution was approaching 50/50, and at worst it would be misleading. The chances of guessing the 16th item in an unlimited set of random distribution are 1/2, and therefore the chances of all 16 guessing correctly as it was phrased in the puzzle are 1/2^16.
Looking at other people’s hat does nothing to increase the chance of your guess being correct. You are absolutely right that it cannot be better than 50/50 if each hat is independently assigned (either from an infinite pool as you describe, or from a pool of 16 of each with each color selected by an independent random choice like a coin flip).
However, I am not asking for each player to independently improve the odds of their own guess being correct. I am asking to maximize the odds that all are correct at the same time. For example, if you could ensure that all the guesses would either be correct or incorrect, then the overall probability would be 50/50, much better than 1/2^16th.
Can looking at the hats help with this?
— Max
Just to clarify, my response about a limited pool relies on the same math people use to count cards in blackjack, given a known size of a buffer in the shoe. But if you’re talking about roulette — where the previous deals have no bearing on the next — then the question of whether the prior count is even or odd is totally superfluous. And the xor argument is wrong.
It is not relevant to the correctness of any individual guess, but quite relevant to maximizing the odds of everyone guessing correctly at the same time.
Think about it a little more 🙂
— Max
Sorry — should have read minus the odds of guessing wrong once in N times, over two.
Okay. Maybe this is a stupid question, but, if they all have the means to communicate with each other to produce the best possible answers for all, then where’s the question? I feel like the parameters are missing. If an observer saw 15 guys wearing black and white hats, and had to figure out what the next one would be, he’d have a 50% chance of guessing correctly. If he could then tell everyone what to pick in tandem, they’d all have a 50% chance. And if you were to find that the variance of the distribution over time was less than 1/16, you might have a shot at squeezing out a couple extra points…. other than that, even with perfect communication it’s not possible to get better than a 100% RTP / 50% average for these guys. The only way you could do it is if you counted cards, or hats as the case may be… and then you’d have to have a ballpark of how many were left in the shoe. Allowing for perfect communication just takes that ^16 and turns it into a ^1, but it doesn’t alter the underlying odds unless you’re dealing out of a limited set of hats.
The challenge is to create just as good synchronization as you would have with perfect communications without the communications occurring.
That is the question/challenge. To be fair, I posed it as “how well can they do”, so part of the problem was realizing that they can do just as well as if they communicate.
— Max
Interesting. In fairness — I found this post from HN so this isn’t my bag, but this sounds like it’s a prisoner’s dilemma rather than a pure probability question. Still, I don’t see how they could beat a 50% guess, even if they were all on the same wavelength. They could all XOR anything they agreed on, and arrive at the same probability, hats aside.
I’ve enjoyed this, btw. I run an online casino with a focus on untested/original games, and I spend a lot of time feeling my way through probability problems. If I seem like I’m being picky, it’s just that living on probabilities has given me a sense of how drastically communication, or other situational circumstances can affect the actual outcome of a question like this… including how many hats or cards are left in a shoe. Mathematically, I’ll admit I’m an idiot and I’d like to know the perfect answer here, but the xor’ing a number out of 15 doesn’t make sense to me; it’s a stand-in for collusion, and we ban people for that 😉
It is similar to the prisoners dilemma in that the outcome depends on each players strategy given a set of inputs and the strategies interact in complex ways. The goal is formulating a strategy across the players that optimizes their outcome. It is different in that the game is completely cooperative: there is no way that one player can benefit themselves while hurting other players.
They can’t individually beat a 50% guess, but they can time themselves to synchronize their correct and incorrect guesses and improve the odds of survival from one in 65536 to one in two.
You are absolutely correct about the impact of communications on these types of problems. Next week I’ll add another twist that highlights that in an even more surprising way. I have never been much of an online poker player, partly because of fear of collusion. (Also partly because I can’t remember players behavior patterns as well when I’m looking at avatars on a screen). Where is your online casino?
— Max
I think I see it now, about the xor 😉
Collusion detection’s an interesting problem you’d probably have a lot of fun with. I wrote a few algorithms that crunch poker hands and hunt for patterns of suspicious chip-dumping and also possible foreknowledge of one or more other hands at the table. They’re based on the idea that different players seem to have different levels of “prescience” when it comes to dealing with other individual players, but these fit into a general range. Spikes of “intuition” that fall outside that range are graphed and correlated.
My casino’s at strikesapphire.com — but it’s not available in the US.
[…] few weeks ago I posted a puzzle about two mathematicians guessing the results of coin tosses. Dwight asked me about generalizations […]