Prove optimality for hats riddle

expected valuegame theoryprobability

Riddle: There are White and Black hats. There are 3 people, who randomly get assigned white and black hats. Each person can't see his/her own hat color, but can see the others. At least one of the 3 people needs to guess their hat color right, and no one can get it wrong (they can choose to stay silent if they want). What strategy can they use to have max probability of winning?

Optimal solution: Whoever sees 2 of the same color hats on the other 2 people, will say the opposite of that color for their own hat color. This ensures 3/4 probability of winning. Here is the state space:

WWW BBB WBB BWB WBW BBW WWB BWW (the bolded person will speak out)

How can I rigorously prove that this is the optimal solution, and that getting 7/8 or 8/8 is not possible?

Best Answer

In any strategy, any given person's probability of guessing correctly equals their probability of guessing incorrectly. Summing over people, it follows that the expected number of correct guesses equals the expected number of incorrect guesses. Since at most three people can guess incorrectly in any given state, and you need at least one person to guess correctly in order to win, it follows that $$ P(\text{win}) \leq E[\#(\text{correct guesses})] = E[\#(\text{incorrect guesses})] \leq 3 \cdot P(\text{loss}), $$ which implies $$ 1 = P(\text{win}) + P(\text{loss}) \leq 4 \cdot P(\text{loss}), $$ so $P(\text{loss}) \geq 1/4$ and thus $P(\text{win}) \leq 3/4$. This generalizes readily to the $n$-player version for any $n$.

Related Question