3 heroes with hats vs a villain

[jestingrabbit]

Simple solution?

Spoiler:

Say the heroes have a strategy such that their probability of success is > 50%. The villain can then give each hero a random hat with 50:50 probability, hence anyone who guesses can only have a 50% chance of success (as the hats are independent of one another.) This contradicts our assumption that there exists a solution with greater than 50% odds. Therefore (as a 50% strategy does exist), that is the best we can do.

That argument must be wrong. Your villain uses no knowledge of the strategy, so if there is a strategy that delivers better than 50% when the villain is uninformed, that contradicts you.

Spoiler:

Now consider what happens if every hero uses the strategy "if the other two are wearing hats that are the same colour, I guess the other colour, otherwise I abstain", then in RRB, RBR, BRR, RBB, BRB and BBR the heroes win, and they only lose on RRR and BBB where every hero guesses wrong.

The question is whether there can be a similar strategy when the the villain knows what the heroes will do. Smart money says no.

[taggedjc]

Spoiler:

We have three people to consider: A, B and C. Let's call the probability that A guesses correctly A1, and the probability that he guesses incorrectly A2. Similarly, we can define B1, B2, C1 and C2. Then the constraint E(wrong guesses) ≥ E(correct guesses) becomes A2 + B2 + C2 ≥ A1 + B1 + C1. We are interested in how large we can make p(correct guess an no wrong guess), which I'll call p. In the notation above, p = (1 - A2)(1-B2)(1 - C2) - (1 - A1 - A2)(1 - B1 - B2)(1 - C1 - C2).

Of course, each of the As, Bs and Cs should lie between 0 and 1, and we must have that each of A1 + A2, B1 + B2 and C1 + C2 is at most 1. I'll call these the bounding conditions.

We want to show that p ≤ 1/2, which we can now do by the circuitous method of supposing that we can choose A1, A2, B1, B2, C1 and C2 meeting the constraint above but with p > 1/2, and showing that that leads to an absurd conclusion. So suppose we have such values for the As, Bs and Cs.

Lets first of all think about what happens if we change A1 and A2 a bit. We don't want to break the constraint, so whatever we add on to A1, we should also add on to A2.

Spoiler:

This is where I stop following. If you add to A1, you may actually have to remove something from A2, since if you have a 60% chance of guessing correctly and a 40% chance of guessing incorrectly, and you change the chance of guessing correctly to 65%, the other chance necessarily goes down to 35%. How did you come up with the constraint E? The puzzle is that you can't have any wrong guesses, not that you have to have more correct guesses than wrong ones - I guess I just don't see how the given constraint gives that meaning. If you were doing this puzzle without a malevolent villain who knows the strategy, would you apply the same argument? Because it is easily shown that in this case there is an optimal strategy that results in success > 50%. What would the math look like on that one, I am curious?

[mfb]

Looking for a simple proof of <=50%, I found a 75%-strategy for the heroes if they get access to a common source of random information after the villain placed their hats:

Spoiler:

Let's look at the solution without villain first:
We have 8 possible hat arrangements, which can be shown in a cube like this one from Wikipedia.
The strategy now defines two positions at opposite corners which are "bad", meaning that the heroes lose there and win at the other 6 corners. This is usually done with (000) and (111), but it is possible to use all other combinations of opposide corners.

Here as an example with (100) and (011), where (ABC) are the heroes A, B and C:
For A: "if you see (x00) guess 0, if you see (x11) guess 1, otherwise abstain"
For B: "if you see (1x0), guess 1, if you see (0x1) guess 0, otherwise abstain"
For C: "if you see (10x), guess 1, if you see (01x) guess 0, otherwise abstain"
In the case of (100) and (011), all are wrong, otherwise one hero will guess right and the others abstain.

In total, there are four different ways to use this strategy class, for each hat placement three win and one loses.

Now, assume that they can see two coin-flips from any source: The results determine which of these 4 strategies they use (with some pre-defined algorithm, e.g. "2 heads: use the {(100),(011)}-strategy shown above, head tail: use [...]"). With 75% probability, they choose a winning strategy.

Instead of coin flips, they could use anything which cannot be manipulated (or known) by the villain and is observable by all.

[douglasm]

Looking for a simple proof of <=50%, I found a 75%-strategy for the heroes if they get access to a common source of random information after the villain placed their hats:

Spoiler:

Let's look at the solution without villain first:
We have 8 possible hat arrangements, which can be shown in a cube like this one from Wikipedia.
The strategy now defines two positions at opposite corners which are "bad", meaning that the heroes lose there and win at the other 6 corners. This is usually done with (000) and (111), but it is possible to use all other combinations of opposide corners.

Here as an example with (100) and (011), where (ABC) are the heroes A, B and C:
For A: "if you see (x00) guess 0, if you see (x11) guess 1, otherwise abstain"
For B: "if you see (1x0), guess 1, if you see (0x1) guess 0, otherwise abstain"
For C: "if you see (10x), guess 1, if you see (01x) guess 0, otherwise abstain"
In the case of (100) and (011), all are wrong, otherwise one hero will guess right and the others abstain.

In total, there are four different ways to use this strategy class, for each hat placement three win and one loses.

Now, assume that they can see two coin-flips from any source: The results determine which of these 4 strategies they use (with some pre-defined algorithm, e.g. "2 heads: use the {(100),(011)}-strategy shown above, head tail: use [...]"). With 75% probability, they choose a winning strategy.

Instead of coin flips, they could use anything which cannot be manipulated (or known) by the villain and is observable by all.

I think this addition of a post-villain common random information source is functionally equivalent to removing the villain from the problem. Come up with a strategy that works well for uniform random hat placement, and then use your post-villain source of randomness to produce a uniform random transformation of the villain's hat placement - for each hero, flip a coin to decide whether to treat that hero's hat as being what's actually there or the opposite. This allows the heroes to treat the hat placement as uniform random no matter what the villain actually does, so the villain might as well not exist.

Make sure to keep track of the coin flip results and use the same results to convert each guess back from the imaginary distribution to the real one.

[mfb]

You are right. Although the number of required coin flips is smaller than the number of heroes.

[sfwc]

If you add to A1, you may actually have to remove something from A2, since if you have a 60% chance of guessing correctly and a 40% chance of guessing incorrectly, and you change the chance of guessing correctly to 65%, the other chance necessarily goes down to 35%.

You are right that we can't always increase both A1 and A2, since maybe A1 + A2 = 1 already. Similarly, we might be unable to decrease both if one of them takes the value 0. I'll call these situations boundary cases. The point of my argument about attempting to make these modifications is that we can always assume we are in one of these boundary cases, since if we aren't, we can make such a modification and move to a boundary case without making the strategy any worse. That's why I said this:

In fact, we can keep on changing the values of A1 and A2 in the appropriate direction until we can go no further because of the bounding conditions. This happens when either at least one of A1 and A2 is 0 or else A1 + A2 = 1. So, we may as well suppose that one of these things happen: if not, we can make it happen without breaking the constraint or reducing the value of p.

I'm sorry if I laid out the argument in a way that made this unclear.

How did you come up with the constraint E? The puzzle is that you can't have any wrong guesses, not that you have to have more correct guesses than wrong ones - I guess I just don't see how the given constraint gives that meaning.

Yes, there is an extra step here, which you might have missed since it is in the stuff I quoted in that post, rather than in the main text. I'll give the key quotations again here:

I'm pretty sure it's impossible for any strategy to do better than 50%. My reasoning:

Spoiler:

If hero X has probability p of making a correct guess in a certain hat setup, then in the setup where X's hat has changed and the other two stay the same, X has probability p of making a wrong guess. So the sum, over all hat setups, of the expected numbers of correct guesses is equal to the sum of the expected numbers of wrong guesses. For this to be true there must exist at least one setup where E[wrong guesses] >= E[correct guesses].

Since given a particular hat setup, the heroes' choices are independent of each other, there's no way to get the wrong guesses correlated together like there is in the non-adversarial case.

Spoiler:

Even given your last line, the probability of a correct guess could still be greater than the probability of an incorrect guess, e.g. in a situation where A guesses correct, and B/C each guess incorrectly 2/3 of the time, and otherwise don't guess. The expected number of incorrect guesses is 4/3>1, but the chance of an incorrect guess is 8/9<1.

Can you show that if E(wrong guesses) ≥ E(correct guesses), and guesses are independent, then p(correct guess and no wrong guess)≤1/2?

If you are still confused after reading both of those spoilers then let me know and I'll try to give a bit more explanation.

If you were doing this puzzle without a malevolent villain who knows the strategy, would you apply the same argument?

No, the argument wouldn't work in that case. The reason is that the argument in the quote from Goplat assumes that the villain chooses a worst-case scenario for the heroes. But if the hat colours are chosen randomly then even if the worst-case scenario is very bad, it can be made improbable enough that that doesn't matter.

Let me know if you have any more questions.

[rileyrulesu]

Spoiler:

Correct me if i'm wrong, but couldn't the problem be done easily by having each person guess the same color as the hat to their right? Since there will be at least 2 of one color hat, and there are only 3, that means those 2 are automatically next to each other, making an easy victory.

[jestingrabbit]

Correct me if i'm wrong, but couldn't the problem be done easily by having each person guess the same color as the hat to their right? Since there will be at least 2 of one color hat, and there are only 3, that means those 2 are automatically next to each other, making an easy victory.

Someone needs to get it right, with no one getting it wrong. Your strategy would have 2 out of 3 guessing wrong in 3 fourths of all cases. The villain is left with a clear winning strategy.

[douglasm]

Having someone guess right is not sufficient. There must also be no wrong guesses at all. Everyone who submits a guess has to be right.

[Alopex lagopus]

If the heroes have no secret, the probability is 50%.
The heroes have strategy. The villain knows the strategy.
Heroes having n "random". Villain does not know the random n (0-1). The probability 54.54% (6/11)

Does the villain have to be informed honestly of the strategy?

Can the heroes have a secret random number?
This gives the probability 54.54% (6/11)

[mfb]

What? How?
Could you explain what you mean?

With any number (random or not, but with at least 4 possible values) not known by the villain at the time of the hat-placement but known to the heroes at the time of their guesses, the best strategy converts this problem to to a problem without villain (as shown in a previous post from me), and the heroes have a probability of 75% to win.

[Alopex lagopus]

What? How?
Could you explain what you mean?

You have the right and has a beautiful solution. I do not always see the spoiler, unfortunately.
I came to another method, which is worse.

[blakpete]

Assuming that the heroes will definitely be in a circle...
And assuming the hats can only be red or blue...
This strategy should work no matter what.

Spoiler:

If the person left of you has a blue hat, keep your left eye closed; keep your left eye open if the hat is red. If the person right of you has a blue hat, keep your right eye closed; keep your right eye open if the hat is red. If both hats are blue, close for eyes for 3-5 seconds, open them briefly only to check the other two hero's eyes, then repeat. If both hats are red, keep both of your eyes open, and blink very quickly only when needed.

In about seven seconds or so, all three should be 100% sure who has what colored hat. If the right eye of the person to your left and the left eye of the person to your right are both closed, then you have a blue hat. If those two eyes are both open, you have a red hat.

[jestingrabbit]

Assuming that the heroes will definitely be in a circle...
And assuming the hats can only be red or blue...
This strategy should work no matter what.

Spoiler:

If the person left of you has a blue hat, keep your left eye closed; keep your left eye open if the hat is red. If the person right of you has a blue hat, keep your right eye closed; keep your right eye open if the hat is red. If both hats are blue, close for eyes for 3-5 seconds, open them briefly only to check the other two hero's eyes, then repeat. If both hats are red, keep both of your eyes open, and blink very quickly only when needed.

In about seven seconds or so, all three should be 100% sure who has what colored hat. If the right eye of the person to your left and the left eye of the person to your right are both closed, then you have a blue hat. If those two eyes are both open, you have a red hat.

In much the same way, if they turn to each other and tell each what colour hat they're wearing, they will also be able to make the right "guess". The puzzle is all about getting stuff right without all the information. Finding a way to communicate the required information doesn't solve the puzzle, it evades it.

[blakpete]

Whoops, good point. Never mind that then. Uh... chicken scratch, whites of their eyes, and eh... I got nothing.