Jump to content
BrainDen.com - Brain Teasers
  • 4
Sign in to follow this  
bonanova

Green and Yellow hats

Question

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?

 

Share this post


Link to post
Share on other sites

24 answers to this question

  • 1
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!).

 

Share this post


Link to post
Share on other sites
  • 1

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

 

 

Share this post


Link to post
Share on other sites
  • 0

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

Share this post


Link to post
Share on other sites
  • 0

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? 

Share this post


Link to post
Share on other sites
  • 0
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.

Share this post


Link to post
Share on other sites
  • 0
 

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 by Molly Mae

Share this post


Link to post
Share on other sites
  • 0

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. 

Share this post


Link to post
Share on other sites
  • 0
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.

Share this post


Link to post
Share on other sites
  • 0
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? 

Share this post


Link to post
Share on other sites
  • 0
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.

Share this post


Link to post
Share on other sites
  • 0

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.

Share this post


Link to post
Share on other sites
  • 0
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. 

 

Share this post


Link to post
Share on other sites
  • 0
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 by Molly Mae

Share this post


Link to post
Share on other sites
  • 0

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.

 

Share this post


Link to post
Share on other sites
  • 0
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 by Molly Mae

Share this post


Link to post
Share on other sites
  • 0

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.

Share this post


Link to post
Share on other sites
  • 0

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

Thanks. :D 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 by Izzy

Share this post


Link to post
Share on other sites
  • 0
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.

Share this post


Link to post
Share on other sites
  • 0
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. :D 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!


 

Share this post


Link to post
Share on other sites
  • 0

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

Share this post


Link to post
Share on other sites
  • 0
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!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.

×