# Cooperative guessing game: no incorrect guesses

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?

• I heard this one a while back. I do not know the origin. – Julian Rosen Jun 4 '15 at 3:13
• 100% winning strategy: stare at the eyes of a person wearing a white hat. – Ian MacDonald Jun 4 '15 at 12:28
• 100% winning strategy #2: Take off your hat and guess it's colour, or take off someone else's hat and let them see it so that they can guess it's colour. – Mark N Jun 4 '15 at 16:46
• I was wondering what would happen if the players could communicate after they get their hats but before they guessed. But then it dawned on me that they only need to signal to one payer what his or her hat is, which is trivial and uninteresting. – Kevin - Reinstate Monica Jun 5 '15 at 21:18

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.

• I'm disappointed, you used a XOR instead of a XNOR! ;-) – leoll2 Jun 4 '15 at 16:08
• I wrote a quick program, and out of 32768 possibilities, 8257 resulted in $S=0$, slightly more than $1/4$. – Trenin Jun 4 '15 at 16:35
• @Trenin Could you please check again? I tried it with code and got that S=0 on 2048 of the 32768 possibilities. – xnor Jun 4 '15 at 21:33
• @xnor I was mistaken - I had a bug in my code. Still, other than brute force, how did you know it is 15/16? – Trenin Jun 5 '15 at 13:42
• Half of all combinations for each of the four elements gives zero for that element (and half give one). Given that the values for each element are uncorrelated, we may multiply probabilities to get $P(S=0) = (\frac{1}{2})^{4}$ – frodoskywalker Jun 5 '15 at 15:03

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$.

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).

• Welcome to Puzzling! There's already a well-known strategy for 75% with 3 players, and Joe Z posted a strategy for about 60% with 15 players. (The trick is to "concentrate" all the wrong guesses into specific scenarios, since we're not trying to maximize the expected value of guesses, just the probability of not guessing wrong.) Please read other answers before posting your own. Thanks! – Deusovi Mar 9 '17 at 21:48

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.

• While this would work great, I think that this would count as communication, which is prohibited. – Trenin Jun 4 '15 at 16:41

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.

• Nice idea, but 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. – frodoskywalker Jun 4 '15 at 19:30