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.
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.