Green and Yellow hats

[bonanova]

Here's a toughie. A room full of prisoners is given hats, whose color only the others can see. And just to be different, let's say they are yellow or green. No communication is permitted. At a signal, given by the warden, the prisoners must simultaneously shout out the color of their own hat. Those who guess wrong are subsequently executed.

Beforehand, the prisoners meet to determine a strategy -- a set of rules, not necessarily the same for each prisoner -- that will guarantee the greatest number of survivors. As an added wrinkle, the warden may attend the meeting and then use his knowledge of their strategy when he chooses the colors of their hats.

If there are 100 prisoners, how many can be assured of surviving?

 

[Izzy]

  Reveal hidden contents

So, the above answer can be generalized a bit. Let everyone pick a partner, and number the partners 0 and 1.  Everyone agrees to say "green", unless they count the exact number of greens hats as their number, The possible colorings are:

green, green (guy on left lives)

green, yellow (guy on right lives)

yellow, green (guy on right lives)

yellow, yellow (guy on left lives)

Since we can have 50 such groups, 50 people are guaranteed to live (and die!).

 

[Izzy]

@Molly Mae, here is a demonstration that the answer can bestrictly greater than zero. 

  Reveal hidden contents

I only have like ten minutes to type it out right now, so here's a smaller example. Suppose there are three people, number them 0 to 2. Let everyone say "green", unless they see exactly the same number of hats as their number. 

The eight possible hat colors, people numbered left to right are:

g, g, g (at least 0th person lives)

g, g, y (at least 0th person lives)

g, y, g (at least 0th person lives)

y, g, g (at least 2nd person lives)

g, y, y (at least 1st person lives)

y, g, y (at least 1st person lives)

y, y, g (at least 1st person lives)

y, y, y (at least 0th person lives)

Generalize this to 100 people. 

 

 

[CaptainEd]

As always, we hope for some communication. The prisoners can see each other. It’s not clear they can hear each other (after all, if they shout simultaneously, they can’t benefit from hearing the others). Are they allowed to turn their bodies to face in a variety of directions, or some such thing? You said “no communication”, and I fear you mean it, but just askin’...

[bonanova]

Nope. They act on what they see. Sorry.

[Izzy]

Are they allowed to move at all, like to sort themselves without communication? Or do they start off in their positions in the room with hats placed on them, only allowed to say one word? 

[bonanova]

  On 1/23/2018 at 6:13 AM, Izzy said:

Are they allowed to move at all, like to sort themselves without communication? Or do they start off in their positions in the room with hats placed on them, only allowed to say one word? 

Expand  

Hmmm. OP does not rule out movement. But it does rule out communicating. So let's say that if the prisoners want to be at some preferred location in the room, that's permissible. But their chosen location can't be in any way influenced by hat color -- i.e., all movement must occur before the hats are placed.

[Molly Mae]

  Reveal hidden contents

An absolute worst case, I can get 49. That's where the hats happen to split 50-50. Any other distribution increases the number. 

If a prisoner sees 49/50, he shouts the colour of the 49. For any other distribution, he shouts the colour of the larger group.

It's a starting point, but the lack of gained information over time means I likely can't do better.

Never mind. This fails for the case of 49-51 the same way the larger group fails for 50-50.

This will always have a case that fails completely, which the warden can use against us. 

Edited January 23, 2018 by Molly Mae

[Izzy]

  Reveal hidden contents

I wonder if the prisoners have to effectively trick the warden into giving them a favorable scenario. For example, the prisoners say that they're all going to pair up with a predetermined partner, and say the opposite color of the hat that their partner has. The warden, thinking that he's clever, gives all pairs the same color hats. The prisoners all know this and say the same color hat as their partner. Or, the warden just doesn't let people partner up. This relies on the warden being way too stupid lol. 

[Molly Mae]

  On 1/23/2018 at 4:05 PM, Izzy said:

 

  Reveal hidden contents

I wonder if the prisoners have to effectively trick the warden into giving them a favorable scenario. For example, the prisoners say that they're all going to pair up with a predetermined partner, and say the opposite color of the hat that their partner has. The warden, thinking that he's clever, gives all pairs the same color hats. The prisoners all know this and say the same color hat as their partner. Or, the warden just doesn't let people partner up. This relies on the warden being way too stupid lol. 

Expand  

This is basically my stumbling block.  Any strategy you could come up with could be countered by the warden.  If you could anticipate that the warden would do all in his power to flummox your strategy, you could (as a logical individual) decide to go completely against the strategy.  That, however, doesn't guarantee any successes either.

  Reveal hidden contents

It wouldn't be a hat puzzle without a clever answer, though, so I'm going to say the highest number I can guarantee is 0.

[Izzy]

  On 1/23/2018 at 5:24 PM, Molly Mae said:

 

  Reveal hidden contents

It wouldn't be a hat puzzle without a clever answer, though, so I'm going to say the highest number I can guarantee is 0.

 

Expand  

 

  Reveal hidden contents

Pretty sure it wouldn't be a "toughie" if we can't save anyone. We definitely need to manipulate the warden. 

@bonanova, is the warden perfectly logical? Are the prisoners perfectly logical? 

[Molly Mae]

  On 1/23/2018 at 5:34 PM, Izzy said:

 

  Reveal hidden contents

Pretty sure it wouldn't be a "toughie" if we can't save anyone. We definitely need to manipulate the warden. 

@bonanova, is the warden perfectly logical? Are the prisoners perfectly logical? 

Expand  

I figured it would be a "toughie" because hat puzzles tend to have counterintuitive answers.  Now that we've become accustomed to that, we may be looking for an answer that isn't there given the new constraints.

[bonanova]

  On 1/23/2018 at 5:34 PM, Izzy said:

@bonanova, is the warden perfectly logical? Are the prisoners perfectly logical? 

Expand  

Yes and yes.

[Molly Mae]

  Reveal hidden contents

I can save many for all cases other than the 50-50 and 49-51 (likewise 51-49, obviously).  In either of these cases, I believe the warden has a direct riposte to the any strategy that is discussed.

[Izzy]

  Reveal hidden contents

Okay, what about this. (Long shot. Does the warden assume the prisoners to be truthful? Probably not.) 

The prisoners decide aloud, as MM mentioned, to each say the hat color that they see most frequently. (So, if they see 49-50, they say the color of the 50.)

"Drats!" thinks the warden. "A majority of them will survive, which reflects poorly on my wardening ability. Unless! Hah. I will make the hats 50-50 and then they will all die and I'll get a raise." The warden of course believes the prisoners, because why would they lie to each other during their only opportunity to plan?

Of course, the perfectly logical prisoners knew the warden would think of this solution. The hats are distributed 50-50, and everyone lives by saying the opposite color of the majority that they see. 

 

[Molly Mae]

  On 1/24/2018 at 3:28 AM, Izzy said:

  Reveal hidden contents

Okay, what about this. (Long shot. Does the warden assume the prisoners to be truthful? Probably not.) 

The prisoners decide aloud, as MM mentioned, to each say the hat color that they see most frequently. (So, if they see 49-50, they say the color of the 50.)

"Drats!" thinks the warden. "A majority of them will survive, which reflects poorly on my wardening ability. Unless! Hah. I will make the hats 50-50 and then they will all die and I'll get a raise." The warden of course believes the prisoners, because why would they lie to each other during their only opportunity to plan?

Of course, the perfectly logical prisoners knew the warden would think of this solution. The hats are distributed 50-50, and everyone lives by saying the opposite color of the majority that they see. 

 

Expand  

The only problem is that it doesn't guarantee that anybody lives.

Too much WiFoM

Edited January 24, 2018 by Molly Mae

[bonanova]

Red herring (which I think you've figured out)

  Reveal hidden contents

The warden is a red herring.
To guarantee some number of survivors the strategy must handle the worst case.

 

[Molly Mae]

  On 1/24/2018 at 11:08 PM, Izzy said:

  Reveal hidden contents

So, the above answer can be generalized a bit. Let everyone pick a partner, and number the partners 0 and 1.  Everyone agrees to say "green", unless they count the exact number of greens hats as their number, The possible colorings are:

green, green (guy on left lives)

green, yellow (guy on right lives)

yellow, green (guy on right lives)

yellow, yellow (guy on left lives)

Since we can have 50 such groups, 50 people are guaranteed to live (and die!).

 

Expand  

  Reveal hidden contents

Wouldn't green, green result in both saying yellow? [/spoier]

Edit nvm. I misread. 

Edited January 24, 2018 by Molly Mae

[bonanova]

OK so I see MM quoting an Izzy post, but I don't see that original post.

Can I invite Izzy to repost it, with complete description? Because ... it's the solution.

Nice solve.

[Izzy]

@bonanova, it should be the second post in the thread. Someone upvoted it, so it's no longer in chronological order.

Thanks.  Honestly, I was going to keep trying to come up with a better one, so thanks for putting me out of my misery. Is there a way to prove that there isn't a *better* solution?

Edited January 25, 2018 by Izzy

[bonanova]

  On 1/24/2018 at 11:08 PM, Izzy said:

  Reveal hidden contents

So, the above answer can be generalized a bit. Let everyone pick a partner, and number the partners 0 and 1.  Everyone agrees to say "green", unless they count the exact number of greens hats as their number, The possible colorings are:

green, green (guy on left lives)

green, yellow (guy on right lives)

yellow, green (guy on right lives)

yellow, yellow (guy on left lives)

Since we can have 50 such groups, 50 people are guaranteed to live (and die!).

 

Expand  

This approach saves |n/2| prisoners, and that is optimal.

[bonanova]

  On 1/25/2018 at 10:16 PM, Izzy said:

@bonanova, it should be the second post in the thread. Someone upvoted it, so it's no longer in chronological order.

Thanks.  Honestly, I was going to keep trying to come up with a better one, so thanks for putting me out of my misery. Is there a way to prove that there isn't a *better* solution?

Expand  

  Reveal hidden contents

What the method does is to group cases where if one is wrong the other must be right. You have to "give" something to the disorder in order to "get" something back. I think 1 for 1 is the best bargain you can strike in a case like this where "everything" starts out unknowable on a case by case basis. When you group by threes, could you trade one sure error for two sure saves? That would be something to look at. But it may turn out that in half the cases the answer is yes while in the other half the answer is no.

This really a fun type of problem. There's another puzzle, like this, where the solution is to group a lot of unfavorable outcomes into one or two cases. And by doing so create disproportionately many favorable-outcome choices. I'll try to find it and post it.

By the way, the way the solution is usually described, although your version is logically identical, is to assign half the group to be "husbands" (and the other half to be "wives") so that after the hats are received they can form "couples." The husband then guesses his wife's hat color and the wife guesses the opposite of her husband's color. Unfortunately none of the "marriages" survives the warden's executions!

 

[Izzy]

@bonanova

  Reveal hidden contents

 

Let everyone pick a partner, and number one of the partners 0 and the other 1.  Everyone agrees to say "green", unless they count the exact number of greens hats as their number. The possible colorings are:

green, green (guy on left (0) lives)

green, yellow (guy on right (1) lives)

yellow, green (guy on right (1) lives)

yellow, yellow (guy on left (0) lives)

Since we can have 50 such groups, 50 people are guaranteed to live (and die!).

Just calculated the groups of three case, and half the time two people are saved, and the other half one person is saved. So, you get the same expected value, but can't guarantee as many.

[bonanova]

  On 1/26/2018 at 2:42 AM, Izzy said:

@bonanova

Just calculated the groups of three case, and half the time two people are saved, and the other half one person is saved. So, you get the same expected value, but can't guarantee as many.

Expand  

Ah!

[arpsabbir]

Hello I am new on this forum. I would like to contribute please help me.