19
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ I heard this one a while back. I do not know the origin. $\endgroup$ Jun 4, 2015 at 3:13
  • 6
    $\begingroup$ 100% winning strategy: stare at the eyes of a person wearing a white hat. $\endgroup$ Jun 4, 2015 at 12:28
  • $\begingroup$ 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. $\endgroup$
    – Mark N
    Jun 4, 2015 at 16:46
  • $\begingroup$ 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. $\endgroup$
    – Kevin
    Jun 5, 2015 at 21:18

6 Answers 6

23
$\begingroup$

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.

$\endgroup$
12
  • 6
    $\begingroup$ I'm disappointed, you used a XOR instead of a XNOR! ;-) $\endgroup$
    – leoll2
    Jun 4, 2015 at 16:08
  • $\begingroup$ I wrote a quick program, and out of 32768 possibilities, 8257 resulted in $S=0$, slightly more than $1/4$. $\endgroup$
    – Trenin
    Jun 4, 2015 at 16:35
  • $\begingroup$ @Trenin Could you please check again? I tried it with code and got that S=0 on 2048 of the 32768 possibilities. $\endgroup$
    – xnor
    Jun 4, 2015 at 21:33
  • 2
    $\begingroup$ This answer would be way more useful if it had a paragraph of English in it. What on earth does "Associate the 15 players with nonzero vectors in Z42 like (0,1,1,1). Let S be the sum (entry-wise XOR, or Nim sum) of the players with black hats" even mean? How about one example featuring just a subset of the people? Alternatively, if someone wants to add another answer using this logic but not this notation, I will bounty it. $\endgroup$ Mar 10, 2017 at 20:21
  • 1
    $\begingroup$ @KateGregory , the following link gives an answer which is a little easier to understand math.stackexchange.com/questions/1978141/… $\endgroup$ Dec 2, 2020 at 1:08
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
  • 3
    $\begingroup$ 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! $\endgroup$
    – Deusovi
    Mar 9, 2017 at 21:48
1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ For $N$ integer such that $2^{k}-1 \leq N \leq 2^{k+1}-2$, where $k=\lfloor log_2 N +1 \rfloor$. One can simply disregard $N-2^{k}+1$ players and achieve: $ \frac {2^{k}-1} {2^{k}}$ $\endgroup$
    – heartwork
    Nov 17, 2023 at 15:34
  • $\begingroup$ Welcome to Puzzling! Please check the existing answers before answering :) this particular answer has been given at the end of xnor's answer, for example. $\endgroup$
    – justhalf
    Nov 17, 2023 at 16:06
  • 1
    $\begingroup$ Not really! For general case this is still an open problem! $\endgroup$
    – heartwork
    Nov 18, 2023 at 19:42
  • $\begingroup$ See puzzling.stackexchange.com/questions/100023/… (or oeis.org/A000983). It is possible to do better, but I don't think there is an known easy way to determine the answer. $\endgroup$
    – tehtmi
    Nov 18, 2023 at 22:01
0
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$ Jun 4, 2015 at 19:30
-1
$\begingroup$

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.

$\endgroup$
1
  • 4
    $\begingroup$ While this would work great, I think that this would count as communication, which is prohibited. $\endgroup$
    – Trenin
    Jun 4, 2015 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.