0
$\begingroup$

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?

$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Where does the 3/4 come from? Is it 3 * P(loss), where P(loss) = 1/4? Why does it equal 1/4? $\endgroup$
    – James Flanagin
    Sep 11, 2020 at 17:36
  • $\begingroup$ @JamesFlanagin I have edited my answer to clarify the last step. $\endgroup$
    – Ravi Fernando
    Sep 11, 2020 at 19:21
2
$\begingroup$

To win in $7$ or $8$ of the $8$ scenario's (at least) one of the people (person $X$) must guess white, if they see two white hats, or one of the people must guess black if they see two black hats. Without loss of generality assume the former.

Then if person $X$ has a black hat and the other two have white hats, they will lose, which means that they must win in every other scenario.

But then there must also be a person, person $Y$ ($Y$ may or may not equal $X$) who guesses black, if they see two black hats. If $Y$ has a white hat and the other two have black hats, then they will lose.

Thus there will always be at least two distinct scenarios where they lose.

$\endgroup$
2
  • $\begingroup$ Hmm, I'm looking for a more state space-sort of proof, where we can prove that there exists no other strategy such that this would work. Thank you though! $\endgroup$
    – James Flanagin
    Sep 11, 2020 at 0:02
  • 1
    $\begingroup$ @JamesFlanagin The above shows that given any strategy, there exist at least two states where they do not win, so probability of success is always less than or equal to $6/8$. $\endgroup$
    – tkf
    Sep 11, 2020 at 0:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .