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.