11
$\begingroup$

Two wizards, Alice and Bob, each have two hats on their heads. Each hat is independently black or white with probability one-half. When the game starts each wizard will see the hats on the other wizard's head. At the same time and without letting the other see, they each write down their own name and the position of one of the hats on their own head. Then both entries are checked, and they win if they have both identified a black hat on their own head.
They are allowed to communicate only before the game starts.

Can you devise a strategy to give them more than 25% odds of winning?

$\endgroup$
  • 4
    $\begingroup$ They only win if they each have a black hat on their own head? Well, that sucks for the times when there's only white hats or when one person has only white hats :( $\endgroup$ – dcfyj Nov 4 '16 at 14:31
  • 2
    $\begingroup$ Hi, I think the original formulation is with infinitely many hats on each wizard's head. It is a nice puzzle. $\endgroup$ – Puzzle Prime Nov 4 '16 at 14:32
  • $\begingroup$ Isn't this similar to link $\endgroup$ – Techidiot Nov 4 '16 at 14:35
  • 1
    $\begingroup$ "At the same time and without letting the other see, they each write down their own name and the position of one of the hats on their own head." That technically doesn't say they can't communicate verbally (just that they can't "let the other see".) Can we assume a complete lack of communication once the game starts? $\endgroup$ – mr23ceec Nov 4 '16 at 14:49
  • 1
    $\begingroup$ @mr23ceec Yes that is right. $\endgroup$ – Lembik Nov 4 '16 at 14:50
11
$\begingroup$

One possibility is

for each wizard to guess "TOP" if the other wizard's top hat is black, and to guess "BOTTOM" otherwise. They will win if each wizard's top hat is black, which happens $25\%$ of the time. They will also win if each wizard's top hat is white and bottom hat is black, which happens an additional $6.25\%$ of the time. In total, the wizards will win $31.25\%$ of the time with this strategy.

It is not possible for the wizards to do better. There are $16$ possible combinations of hat colors. Of these, $7$ of them have at least one wizard with no black hat, so cannot be won. Of the remaining $9$ possibilities, in $6$ of them Alice will have one black hat and one white hat, and no matter what Alice's guessing strategy, she will guess correctly in $3$ of the situations and incorrectly in the other $3$. Of the remaining $3$ situations, $2$ of them have the property that Bob has one white hat and one black hat, and no matter what Bob's guessing strategy, he will guess correctly in one situation and incorrectly in the other. So in total Alice and Bob must lose in at least $7+3+1=11$ of the $16$ situations, so they can win at most $5/16=31.25\%$ of the time.

$\endgroup$
  • 1
    $\begingroup$ Interestingly enough, this works -- with identical odds -- if each chooses the OPPOSITE hats: pick "top" if the other wizard's bottom hat is black, and pick "bottom" otherwise. $\endgroup$ – Rubio Nov 4 '16 at 21:57
  • 1
    $\begingroup$ My brain's not working... can you explain (in answer) the counterintuitive result why they're able to beat random strategy (25%), since all hat colors are independent and seeing each others' hats doesn't convey any useful information? What am I missing? $\endgroup$ – smci Nov 5 '16 at 9:17
  • 1
    $\begingroup$ @smci - in simple terms, there's a correlation introduced by the strategy. For more detail, see my answer. $\endgroup$ – Glen O Nov 5 '16 at 12:34
8
$\begingroup$

Each hat is independently black or white with probability one-half

So I take this to mean that a wizard could have both hats be white, or both be black. Not that 1 will be white and 1 will be black (and the position is random).

So...

There are 4 possibilities for each wizard (WW, WB, BW, BB), 16 total combinations between the 2.
In 7 out of 16 cases, at least one wizard will have 2 white hats and they can't possibly win.
In 1 out of 16 both wizards will have 2 black hats and they win no matter what.
In the remaining 8 cases (50% of total) are when they each have at least one black hat and we can try to win.

WB-WB / WB-BW / WB-BB / BW-WB / BW-BW / BW-BB / BB-WB / BB-BW
So there are 4 positions where each wizard sees only 1 black hat. Of these, if they guess the same position they will be correct in 2.
Of the 4 positions where 1 wizard sees 2 black hats, if they guess "top" they will be correct another 2 times.
That means they can be right 4 out of these 8 scenarios.

Which brings us to...

If each wizard writes the same position for the black hat that they see, and guess top when they see 2 black hats, they'll win 5 out of 16 times which is 31.25%

$\endgroup$
  • 1
    $\begingroup$ @JulianRosen - bleh you are right! I was mistakenly counting 7 as a win. That does give us the same answer. I updated $\endgroup$ – Ryan Smith Nov 4 '16 at 15:28
2
$\begingroup$

The other answers focus on the combinatoric way of understanding what is going on. However, it can also be seen from a more statistical perspective.

From the information given in the question, there is no obvious correlation between any of the factors. In the absence of a correlation - that is, with all events being independent - the chance of winning is 25%, as each wizard has a 50% chance of their nominated hat being black, and there is no correlation between those two chances.

But in spite of appearances, it is actually possible to set up some correlations that alter the probability of winning. Let's start by defining a few events:

Let $A_n$ mean that wizard A's $n$th hat is black.

Let $B_n$ mean that wizard B's $n$th hat is black.

Let $a$ and $b$ mean that wizards A and B, respectively, chooses hat 1.

Now, as the hat colours are random, we have $P(A_n)=P(B_n)=\frac12$ for each $n$.

This is where the correlation comes in...

If Wizard A chooses hat 1 if and only if Wizard B's first hat is black, then $P(a|B_1) = 1$.
If the reverse is also true (B chooses based on A's first hat colour), then $P(b|A_1)=1$.

Now, there are four ways to win, each of which is mutually exclusive. There's:

  1. $C_1=a\cap A_1\cap b\cap B_1=(a\cap B_1)\cap(b\cap A_1)$
  2. $C_2=a\cap A_1\cap \bar b\cap B_2=(a\cap B_2)\cap(\bar b\cap A_1)$
  3. $C_3=\bar a\cap A_2\cap b\cap B_1=(\bar a\cap B_1)\cap(b\cap A_2)$
  4. $C_4=\bar a\cap A_2\cap \bar b\cap B_2=(\bar a\cap B_2)\cap(\bar b\cap A_2)$

As they are mutually exclusive, we can simply add the probabilities, and so we need only look at the probability of each case. Note that the pairs of bracketed terms on the right side of the equalities are independent of each other. And this is where the correlation becomes useful.

Case 1:

We have $P(a\cap B_1)=P(a|B_1)P(B_1)=1\cdot\frac12 = \frac12$,
and similarly, $P(b\cap A_1)=\frac12$.
So for case 1, the probability is $\frac12\cdot\frac12=\frac14$.

Case 2:

We have $P(\bar b\cap A_1) = P(\bar b|A_1)P(A_1)=0\cdot\frac12 = 0$,
and so, for case 2, the probability is zero - it cannot happen.

Case 3:

We have $P(\bar a\cap B_1) = P(\bar a|B_1)P(B_1)=0\cdot\frac12 = 0$,
and so, for case 3 as with case 2, the probability is zero - it cannot happen.

Case 4:

We have $P(\bar a\cap B_2)$ and $P(\bar b\cap A_2)$. However, neither of these are in any way correlated - wizard A doesn't look at wizard B's second hat when deciding which hat to choose, and vice versa. As such, $P(\bar a\cap B_2) = P(\bar a)P(B_2) = \frac12\cdot \frac12 = \frac14$, and similarly for the second pair.

Therefore, we conclude that

$P(Win) = P(C_1)+P(C_2)+P(C_3)+P(C_4) = \frac14 + \frac1{16} = \frac5{16}$

All of this happens because we introduced the correlations. If the wizards choose randomly, then obviously $P(a|A_1)=P(a)=\frac12$, and the chance of winning is just $\frac14$, as expected.

The really interesting part is that it only works if they both do it, but it doesn't matter which hat each one looks at, nor does it matter whether black means hat 1 or hat 2 for each of them.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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