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]

Spoiler

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. 

Spoiler

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]

1 hour ago, 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? 

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]

 

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]

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]

1 hour ago, Izzy said:

 

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

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.

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]

6 minutes ago, 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.

 

 

Spoiler

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]

12 minutes ago, Izzy said:

 

  Hide 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? 

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]

1 hour ago, Izzy said:

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

Yes and yes.

[Molly Mae]

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]

Spoiler

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]

48 minutes ago, Izzy said:

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

 

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)

Spoiler

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

 

[Molly Mae]

46 minutes ago, Izzy said:

  Hide 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!).

 

 

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]

23 hours ago, Izzy said:

  Hide 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!).

 

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

[bonanova]

23 minutes ago, 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?

Spoiler

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

 

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]

9 hours ago, 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.

Ah!

[arpsabbir]

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