There are 100 people standing in a circle. Each person is given one hat to wear. A hat is either colored red or blue. A person cannot see his own hat color, but he can see the colors of the hats of all other people standing in the circle.
At the same time, each person is asked to guess their own hat color and all of them have to answer at the same time. They only win if all 100 people guess their own hat color correctly.
The 100 people are allowed to devise a strategy before they are given their hats. They agree on a strategy that maximizes their chance of winning. What is their probability of winning and how could this strategy look like?
Details of assumption: * no cheeky tricks (no way of communicating etc. after devising the strategy) * they have to answer at the same time - no information gained by other answers. * they don't know in advance how much of each hat color there is.
BONUS: generalize for n different hat colors.
One strategy that maximizes the chance of winning is the following:
If you see an even amount of blue hats, guess blue. If not, guess red.
Note that every person that wears a blue hat gives the same answer, as they see the same amount of blue hats. Someone who wears a red hat sees 1 blue hat more than a person who wears a blue hat and therefore guesses the other answer. Thus there are only two equally likely possible outcomes left: all people with blue hats guess blue and all people with red hats guess red, or all people with blue hats guess red and all people with red hats guess blue. This yields a probability of 1/2.
We can be sure that this strategy maximizes the chance of winning since the average number of correct guesses always has to stay at 1/2, regardless of the strategy.
CORRECT ANSWER FOR BONUS: spoiler1/n