Green and Yellow hats again, but harder

[bonanova]

As promised, a harder hat problem.

Prisoners are seated in a circle so they can see all the others. This time the warden flips a fair coin for each prisoner and gives him a yellow or green hat, accordingly. Once all the hats have been placed, and have been seen by the others, prisoners are taken aside singly and given the opportunity to guess the color of his hat. And if instead he chooses not to guess, he is permitted to pass.

Now comes the bad part. Unless at least one prisoner guesses, and all the prisoners who do guess are correct, all the prisoners will be executed. That's right, survival requires perfection from every prisoner who guesses his color.

Prisoners decide on a strategy beforehand, and after the first hat is placed there is no further communication. Clearly, there can be a single "designated guesser" who ... just ... guesses a color. Half the time they all survive. But what kind of a puzzle would that be? Yes, incredibly, the prisoners can do much better. How? Maybe thinking about a three-prisoner case will answer that question.

Once you're convinced they can do better than a coin toss, find their best strategy.

[Izzy]

  Reveal hidden contents

First, we convince ourselves of the case with three people. When three hats are colored, the most common combination is that two hats are one color and the third hat is of the other. So, if one person sees two hats of the same color, he should guess the opposite color of those hats. 

Let's see what happens in each of the cases. 

green green green (everyone dies)

green green yellow (everyone lives)

green yellow green (everyone lives)

yellow green green (everyone lives)

yellow green green (everyone lives)

green yellow green (everyone lives)

green green yellow (everyone lives)

yellow yellow yellow (everyone dies)

Great, so people are saved 6/8 times. 

Generalizing this is not too hard. For four people, there are 16 possible ways to color the hats. Let (AcB) denote "A choose B", and let this also be the ways we choose the green hats. So, all of our possible combinations are:

(4c0) + (4c1) + (4c2) + (4c3) + (4c4) = 1 + 4 + 6 + 4 + 1. So, in 8/16 cases, there will be three hats of one color and one hat of the other. Okay, this only gives us 50/50. 

Let's see what happens for five people. We get

(5c0) + (5c1) + (5c2) + (5c3) + (5c4) + (5c5) = 1 + 5 + 10 + 10 + 5 + 1. Now, in 20/32 cases, the coloring will have three hats of one color and two of the other. 

With six, the strategy is worse again, the corresponding numbers being 1+6+15+20+15+6+1 = 64. 

Anyways, if you keep doing this, you see that with an odd number of prisoners, 2k+1, you get that the middle two entries (of Pascal's triangle) are both (2k+1 c k), so you have people 2(2k+1 c k)/2^(2k+1) of the time, which... has a limit that goes to 0 sadly. So, this doesn't work work well for lots of people, but does for small amounts of people. 

 

[Molly Mae]

For 3 prisoners:

  Reveal hidden contents

If any prisoner observes 2 hats of the same colour, he should guess the other colour.  

GGG - they die
YGG - they live
GYG - they live
GGY - they live
GYY - they live
YGY - they live
YYG - they live
YYY - they die

That also succeeds with 75%.

 

EDIT: Ninja'd by Izzy.

Edited January 27, 2018 by Molly Mae
Ninja'd

[Izzy]

  Reveal hidden contents

I did another case to convince myself. There let be six people. Say "green" if you see exactly 5, 4, or 3 people before you with green hats, and no one in front of you could also see 5, 4, or 3 green hats in front of them. Say "yellow" if you see exactly 5, 4, or 3 people before you with yellow hats, and no one in front of you could also see 5, 4, or 3 yellow hats in front of them.

The possible colorings again break up into 1 + 6 + 15 + 20 + 15 + 6 + 1 (corresponding to ways to have all green hats, 1 green hat, 2 green hats, etc. respectively). We show we can save all except the middle 20 scenarios. 

If all of the hats are green, the fourth person sees three green hats in front of him, and says "green". Then, no one else says anything. 

If five of the hats are green, the person with the fourth green hat says "green", and no one else says anything. 

The same thing happens for the all yellow and five yellow cases. So, we've already saved 14/64 cases. 

Now, consider when four hats are green and two hats are yellow. None of the yellow people speak. The person with the fourth green hat says "green", and they all live. The same thing happens for the cases when all the hats are yellow. Thus, this saves an additional 15*2 = 30 cases. So, overall, we save 44/64 = 11/16 cases. 

So, for an even number of people, I think we can always save (2^n-(n C n/2))^(2^n) people, by saying "green" if you see n-1, n-2, ..., or n/2+1 green hats in front of you, and no one else does, or same thing for yellow hats. (For six, this turns out to be (2^6 - (20))/2^6 = 11/16. For 100, this turns out to be about 90%, and in general the expression has limit 1.  

If n is odd, we have to be a little bit careful in small cases. For example, for n=5, we get the color breakdown of 1 + 5 + 10 + 10 + 5 + 1, and 10 + 10 > 1 + 5 + 5 + 1, so this strategy is not optimal. However, for n large enough (starting at n=9, actually), this problem disappears. The n=5 and n=7 cases can be examined separately for an optimal strategy. 

 

Edited January 27, 2018 by Izzy

[plainglazed]

Not a generalized formula but better than strategy for three?

  Reveal hidden contents

Label prisoners A-G.  Label Yellow hats 0 and Green hats 1. 

Each prisoner must memorize these eight strings and their inverses as well as their relative position within the group:

        A B C D E F G
S1 - 0 0 0 0 0 0 0
S2 - 0 0 0 1 1 1 1
S3 - 0 0 1 0 1 1 0
S4 - 0 0 1 1 0 0 1
S5 - 0 1 0 0 1 0 1
S6 - 0 1 0 1 0 1 0
S7 - 0 1 1 0 0 1 1
S8 - 0 1 1 1 1 0 0

These sixteen strings and all strings created by changing just one bit of each of the sixteen comprise all 128 possible two

color hat combinations with seven prisoners.

So now the strategy:  Each prisoner sees six bits (hats) and can create two seven bit strings by inserting a 0 and a 1 at

their respective position.  If neither of those two strings match any of the sixteen memorized strings, abstain.  If one of

those two strings matches one of the memorized strings, choose the other bit (hat color) that did not create a match.

This effectively packs seven wrong answers in each of the sixteen memorized strings and gives one correct response in each

of the other 112 cases.  So with 7 prisoners (or more) freedom is possible 7/8ths of the time.

 

[plainglazed]

I think I see the pattern here and am encouraged by the beauty of binary symmetry so here goes:

  Reveal hidden contents

For integers i and the number of prisoners n equal to 2^i-1, the probability of success p is (2^n-m)/2^n or n/2^i where m is the number of strings needed to memorize and is 2^(n-i).

i          n=2^i-1          m=2^(n-i)               p=(2^n-m)/2^n or n/2^i
1             1                      1                                         1/2
2             3                      2                                         3/4
3             7                     16                                        7/8
4           15                   2,048                                   15/16
5           31              67,108,864                              31/32
.
.
.

 

[Molly Mae]

  Reveal hidden contents

I'lI can do better than a standard coin toss, but the worst case scenario still comes down to a coin toss.

For two prisoners, let the first prisoner pass is he sees that his partner has a green hat.  His partner is informed to always guess green.  If his partner has a yellow hat, the first person guesses any colour.

50% of the time, they are guaranteed to live.  25% of the time, they live based on a correct guess from the first person.  25% of the time, they die.

75% success rate is better than a coin toss, but I'm convinced there's better.

[bonanova]

In games of this type every guess, on average, is wrong 50% of the time.

For the 3-prisoner strategy, if we count the number of guesses made in all 8 cases, we find six of them are correct and six are incorrect. We "rescue" the other cases, (when both colors are seen, and no guidance is available,) with the "Pass" option. The same is true in the previous G-Y puzzle.

The difference is that in the first puzzle every wrong guess produced a fatality, so survival also was only 50%. In the 3-prisoner case here, death uses up three wrong guesses (while survival still requires only a single correct guess.) We "packed" the incorrect guesses into the fewest possible of the eight cases and thus raised survival to 75%.

But since 2x3 = 6x1 randomness still got its due.

The 3-prisoner solution is trimmed-down version of the n-prisoner strategy. Have fun...

[bonanova]

In this puzzle, they're not in a line.

[Izzy]

  On 1/28/2018 at 7:58 AM, bonanova said:

In this puzzle, they're not in a line.

Expand  

So, same solution as above (the upvoted post if you can't see it chronologically), but the "people in front of them" are the people that get taken aside before them?

[bonanova]

I'm missing

  On 1/27/2018 at 5:13 PM, Izzy said:

Now, consider when four hats are green and two hats are yellow.
None of the yellow people speak.
The person with the fourth green hat says "green", and they all live.

Expand  

I think I understand your analysis, but wonder how you would implement this.
Given they sit in a circle and guess (or pass) privately,

  Reveal hidden contents

• How do the prisoners become aware that the color distribution is GGGG YY
• How do the yellow prisoners become aware (of their hat color, and therefore) that they should pass.
• How does the prisoner with the fourth green hat become aware that (1) his hat is green and (2) that it's the fourth one.

 

 

[Molly Mae]

  On 1/31/2018 at 11:17 AM, plainglazed said:

Not a generalized formula but better than strategy for three?

  Reveal hidden contents

Label prisoners A-G.  Label Yellow hats 0 and Green hats 1. 

Each prisoner must memorize these eight strings and their inverses as well as their relative position within the group:

        A B C D E F G
S1 - 0 0 0 0 0 0 0
S2 - 0 0 0 1 1 1 1
S3 - 0 0 1 0 1 1 0
S4 - 0 0 1 1 0 0 1
S5 - 0 1 0 0 1 0 1
S6 - 0 1 0 1 0 1 0
S7 - 0 1 1 0 0 1 1
S8 - 0 1 1 1 1 0 0

These sixteen strings and all strings created by changing just one bit of each of the sixteen comprise all 128 possible two

color hat combinations with seven prisoners.

So now the strategy:  Each prisoner sees six bits (hats) and can create two seven bit strings by inserting a 0 and a 1 at

their respective position.  If neither of those two strings match any of the sixteen memorized strings, abstain.  If one of

those two strings matches one of the memorized strings, choose the other bit (hat color) that did not create a match.

This effectively packs seven wrong answers in each of the sixteen memorized strings and gives one correct response in each

of the other 112 cases.  So with 7 prisoners (or more) freedom is possible 7/8ths of the time.

 

Expand  

  Reveal hidden contents

These are the kinds of things I feel like I'm normally good at, but I stared at it for a long time and I eventually unpacked it.  Since each string is different from the other 15 by at least three bits, you can guarantee that two people won't choose a colour.  That's sneaky-clever.

[bonanova]

  On 2/23/2018 at 9:52 PM, plainglazed said:

I think I see the pattern here and am encouraged by the beauty of binary symmetry so here goes:

  Reveal hidden contents

For integers i and the number of prisoners n equal to 2^i-1, the probability of success p is (2^n-m)/2^n or n/2^i where m is the number of strings needed to memorize and is 2^(n-i).

i          n=2^i-1          m=2^(n-i)               p=(2^n-m)/2^n or n/2^i
1             1                      1                                         1/2
2             3                      2                                         3/4
3             7                     16                                        7/8
4           15                   2,048                                   15/16
5           31              67,108,864                              31/32
.
.
.

 

Expand  

That is amazing. And you've shown that 1 fewer than a power of 2 is the optimal value for n.

Can you reduce it to only q memorized strings, and the success rate to (q-1)/q, where q is the highest power of 2 less than or equal to n?

(Purposely leaving this un-spoilered, cuz this is a tough problem.)