Jump to content
BrainDen.com - Brain Teasers
  • 4

Green and Yellow hats


Go to solution Solved by Izzy,

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?

 

Link to post
Share on other sites

24 answers to this question

Recommended Posts

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

 

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. 

 

 

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

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.

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

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.

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? 

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.

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. 

 

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

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!


 

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.

Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...