Cooperative guessing game: no incorrect guesses

Question

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 1

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.

Answer 2

I know the strategy for 3 players - If you see two or more of a colour, call out the opposite colour; remain silent if both are in equal proportion.

This doesn't work if all three players are wearing the same colour, but does work in all other cases, which is a probability of 3/4.

---

For 15 players (and in general any odd number of players), a similar solution might work in terms of the higher number of hats of a single colour being odd or even:

If you see an even number of hats of a single colour, call out colour that has fewer hats. Otherwise, remain silent.

Supposing that there are $n$ black hats and $15 - n$ white hats, this gives us the following scenarios:

• If we have 15 white hats and 0 black hats, everyone calls out black and dies.
• If we have 14 white hats and 1 black hat, the person wearing the black hat calls out "black", and everyone else remains silent.
• If we have 13 white hats and 2 black hats, everyone wearing a white hat calls out black and they die.
• If we have 12 white hats and 13 black hats, the three people wearing black hats call out "black", and everyone else remains silent.

And so on. This gives us a probability of $\binom{15}{1} + \binom{15}{3} + \binom{15}{5} + \binom{15}{7} + \binom{15}{8} + \binom{15}{10} + \binom{15}{12} + \binom{15}{14}$ $= 19186/32768$ $\doteq 0.6047$.

Answer 3

Since the hat colour is determined randomly by a coin flip, the best probability of winning the game is 50%.

Strategy: Only one player guesses, and it does not matter what colour he or she guesses.

Reasoning: A coin flip does not have memory (much like roulette) so the probability of you wearing a white hat is not dependant on what colour hats the other people are wearing.

Further points: Number of players does not matter, and more people guessing will lower your chances of winning the game (e.g. if two people guess your chances of winning become 0.5*0.5 = 0.25).

Answer 4

This generalize for any $N$ not necessarily of the form$2^k-1$.
Let $N$ be an integer such that $2^{k-1} \leq N \leq 2^k-1$, where $k=\lfloor log_2 N \rfloor+1$.
By this strategy one can guarantee that $N$ players can achieve:
$\frac{N}{2^{\lfloor log_2 N \rfloor+1}}$
win probability, but is this optimal for all $N$?

Answer 5

Update This answer is for a slightly different question. Oops.

Assume everyone can count seconds accurately and consistently. Everyone agrees to speak only on-the-dot on the seconds. At t = 0, everyone opens their eyes.

Act as if a seer at that moment announced "I see at least one person with a black hat." Using the same logic as for the island of blue/brown-eyed people, then at second n (where n is the number of black hats), all the people wearing black hats will correctly guess that they are wearing black hats.

Only fails if everyone is wearing white hats, which has probability $2^{-15}$.

Details, in case you are not familiar with the other riddle.

If there is exactly one person wearing a black hat, he will see only white hats and know the seer must refer to him. At t = 1, he will speak. If there are two people with black hats, they will each see another person with a black hat. When that person doesn't speak at t = 1, they will each realize they must also have a black hat, and so both will speak at t = 2. Etc.

This works for any number of hats, and fails only if all the hats are white.

Answer 6

Since you only need one person to answer, and one person to answer correctly, elect one person as the guesser. When the hats are placed, have everyone at the table, with the exception of the guesser, look a certain direction based on hat color of the guesser (left for black, right for white). This tells the guesser what color their hat is without anyone else having to speak.

The great thing is, this is expandable for number of players. As long as you have 2+ players, you can follow this strategy.