There are 15 players who will play a cooperative game. They begin by closing their eyes. A referee will place either a black hat or a white hat (chosen by fair coin flip) on each player's head. The players may then open their eyes.
Each hat is visible to every player except the one wearing it. On a signal given by the referee, each player may call out a guess of her own hat color, or may remain silent. The calls are simultaneous.
The players all win if at least one player guesses correctly and nobody guesses incorrectly.
They all lose if anyone guesses incorrectly or everybody remains silent.
The players can agree on a strategy beforehand, but no further communication is allowed once the game starts.
Find a strategy for the players that maximizes the probability that they will win. What is that probability?
Bonus: What happens if we change the number of players?
Answer
The players can achieve $15/16$ win probability, which is optimal.
Associate the 15 players with nonzero vectors in $\mathbb{Z}_2^4$ like $(0,1,1,1)$. Let $S$ be the sum (entry-wise XOR, or Nim sum) of the players with black hats. Each player doesn't know $S$ because they don't know their own hat color, but they know the two possible values of $S$ depending on their hat color.
The players' strategy is to bet that $S$ is nonzero.
If one choice of your hat color would make $S$ be zero, guess the other one. Otherwise, remain silent.
We show that the players win exactly if $S$ is nonzero. This happens $15/16$ of the time, since flipping the presence of any of hats $(1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1)$ flips the corresponding entry of $S$, so $1$ of their $16$ joint settings makes the $S$ be $0$.
Proof: The two possible values of $S$ from a player's perspective differ by their own vector. If $S$ equals some nonzero vector $v$, the player $v$ will guess the correct hat color, since the alternative would change the sum by $v$, making it $0$. All other players will remain silent, since their possible sums are $S$ and $S+w$ for $w\neq v$, which cannot be $0$. So, the players win.
If $S=0$, everyone guesses the wrong color. (As is common in hat guessing problems, you want the "wrong" case to be as wrong as possible to balance out the expectation.)
A win probability of $15/16$ is optimal. For any player who guesses, they have an equal probability of getting their hat color right of wrong. So, by linearity of expectation, the expected number of right guesses minus wrong guesses is $0$. Since a win requires at least $1$ right guess and no wrong guesses (difference $+1$), and a loss has at worst a wrong for each player difference $-15$), we must have at least $1$ loss per $15$ wins, so at most $15/16$ win probability.
This all generalizes when the number of players $N$ is of the form $2^k-1$. If it's not, the players can pretend it is by ignoring some number of the players, which gives win probability $1-\frac{1}{2^k}$ where $2^k$ is the largest power of $2$ with $2^k-1\leq N$. I don't know if this is optimal though.
No comments:
Post a Comment