I heard about an interesting puzzle recently:

100 wizards are each given either a red or blue hat with 50% probability. Each wizard can see everyone’s hat except their own. The wizards have to guess the colour of their hat without communicating in any way, but will be allowed to devise a strategy to coordinate their guesses beforehand. How can they maximize the probability that all 100 of them guess correctly?

I like this puzzle because at first it seems impossible to do much better than guessing randomly—how could knowing the colour of other people’s hats help you guess the colour of your own, since the colours were chosen independently? However, there is a very simple strategy which allows them to do much better than guessing randomly.

The strategy is this: beforehand, the wizards simply agree that they will assume the total number of red hats is even. Since it is equally likely that the total number of red hats is even or odd, they have a 50% chance of guessing correctly. And it is easy for each wizard to know the colour of their own hat using the assumption that the total number of red hats is even, since they know the number of red hats worn by others.

I heard about this problem from Tanya Khovanova. She also gives an argument that the strategy is optimal. No matter how the hats are distributed, it is always the case that any specific wizard’s hat is equally likely to be red or blue—so no matter what strategy they use, each wizard will always guess correctly with 50%. Thus the expected number of wizards who guess correctly will always be 50, no matter what strategy is used. But a strategy with a >50% chance in which everyone guessed correctly would have an expected number of wizards guessing correctly of >50, and therefore cannot exist.

The puzzle really demonstrates the power of looking at a problem from the right angle. I spent a lot of my spare time one day thinking about it, and my conclusion kept being that it sounded impossible. I went to bed thinking about the problem, and believe it or not, by the time I had woken up I had thought of the answer. Like a magic trick, the problem suddenly transforms from seemingly impossible to easy with the introduction of the right bit of knowledge.