Given the following variant of the hat guessing game: There are n players and two colors, everybody has to guess his hat color. The aim is to find a strategy guaranteeing as many correct guesses as possible.
The optimal strategy guarantees $\lfloor{\frac{n}{2}\rfloor}$ and involves to have players paired up. If the number of players is odd, then the unpaired one always guesses he has, let us say, a blue hat. In each pair one player guesses he has a hat of the same color as the other player, while
the other player guesses he has a hat of the color another than the first player.
How to prove that this strategy is optimal?
Best Answer
No matter what strategy the players use, each player has a probability of $1/2$ of guessing their hat correctly. This is because, for each player, the $n-1$ hats they see will cause them to guess a particular color, and then their own hat will match that color with probability $1/2$. Linearity of expectation implies the expected number of correct guesses is $n/2$. Therefore, there cannot exist a strategy which guarantees getting more than $n/2$ guesses correct; if you could guarantee getting $x$ correct, the expected number correct would have to be at least $x$. This proves $\lfloor n/2\rfloor$ is optimal.