Prisoners

[Sidoh]

I think this was on Car Talk or something like that, so if you've heard it, please don't answer.  Feel free to comment, but don't ruin it for everyone else!  If you're really considerate, you could post the answer in rot13.



A prison guard is in a dilemma.  His prison is full and he has a new shipment of prisoners due to arrive within a few days.  To clear out the prison, he picks 10 random inmates.  He can't decide whether he should let them go or to kill them, so he decides to put their fate into their own hands.  He invents a game.  Each prisoner is placed in a chair that's in a straight row.  Then, a hat of either green or red is placed on each prisoner's head.  He then tells them: each one of you is to guess which color your hat is.  If you're right, then you're free to go; if not or you say anything other than your hat color, I shoot you on the spot.



The rules of the game are given to the prisoners the night before the game takes place.  The guard gives them the chance to converse before the event as to maximize the number of prisoners allowed free.

Goal: Maximize the number of prisoners that live by inventing a strategy that can be used.

Rules:
    * The prisoners can only say "red" or "green."  If anyone does anything else, the guard shoots all of them.
    * The prisoners can't look at their own hat colors or turn around to see other prisoners' hats.  If this happens, the guard kills all of them.
    * Each prisoner only has one chance to speak a color.  He can say "red" or "green" once and then their turn is over.
    * The prisoners are asked their hat colors sequentially, starting with prisoner 0.
    * Each prisoner must answer immediately after his turn begins or they're shot.

Here are a few pseudo-hints:
    * The diagram is a mere representation of a possible configuration of hats.  The order and number of each color is purely random.
    * The prisoner in the first seat can see all hat colors but his own.  Prisoner 1 can see prisoners 2-9, etc.

[trust]

What is the question?

[Sidoh]

The guard gives them the chance to converse before the event as to maximize the number of prisoners allowed free.

[deadly7]

Why couldn't the person in the very back just say every color hat he sees?  He'd be the only one with a 50% chance, then... or am I thinking about it all wrong?

[Sidoh]

Why couldn't the person in the very back just say every color hat he sees?  He'd be the only one with a 50% chance, then... or am I thinking about it all wrong?

I'm not being clear enough; you have my apologies.  I'll edit my post.  Re-read the rules section and I'll have added a few things.

[dark_drake]

Hrmmm.... here goes the answer I thought up after thinking for a few seconds; it's nothing too elaborate. Prisoner 0 would say prisoner 1's color.  Prisoner 1 would say his color.  Prisoner 2 says prisoner 3's color, and so on.  5 are guaranteed to live.  But really, why does the guard want them to leave?  Just waste them all.  ;D

[Sidoh]

Hrmmm.... here goes the answer I thought up after thinking for a few seconds; it's nothing too elaborate. Prisoner 0 would say prisoner 1's color.  Prisoner 1 would say his color.  Prisoner 2 says prisoner 3's color, and so on.  5 are guaranteed to live.  But really, why does the guard want them to leave?  Just waste them all.  ;D

Yes, that's one way, but it's not the best way.

[rabbit]

Since they are allowed to converse before hand, they can set up a system.  0 will tap 1's chair once for red, twice for green (or something) before saying his own color, and each can do the same for the one in front of them.  That way 9 are guaranteed to live, while 0 has a 50% chance.

Also, do they have the hats on when they are allowed to converse?  Cause if so they could all just get told their color...

[dark_drake]

[size=0pt]I have a way, but only 9 would be guaranteed to survive.

Hrmm.... Prisoner 0 would wait 10 seconds if prisoner 1's hat were green and 20 seconds if his hat were red.  Prisoner 1 would do the same for prisoner 2, and so on. 
[/size]
Quote it for my answer.  :-\

[Sidoh]

Since they are allowed to converse before hand, they can set up a system.  0 will tap 1's chair once for red, twice for green (or something) before saying his own color, and each can do the same for the one in front of them.  That way 9 are guaranteed to live, while 0 has a 50% chance.

Also, do they have the hats on when they are allowed to converse?  Cause if so they could all just get told their color...

That's not outside of the rules I specified, but I'd hope your intuition at least indicated that it is out of the rules of the riddle.  The only form of communication they're allowed is saying "red" or "green."

So, in conclusion: no on both accounts. ;p

drake, sorry, I missed your post.  That's a clever answer, but it's not the one I'm thinking of.  I'll add that as another rule.

[Joe]

Va lbhe qvntenz, gurer ner svir erq ungf naq svir terra ungf. V'z abg fher vs gurl jrer vagragvbanyyl rira, ohg V'yy nffhzr gurl jrer, orpnhfr gung znxrf vg rnfvre. :)

Gur ynfg cevfbare pbhagf hc ubj znal terra ungf naq ubj znal erq ungf gurve ner. Gurer jvyy or svir bs bar naq sbhe bs gur bgure, fb gur bar gurerf sbhe bs vf ba uvf urnq.

Gur frpbaq cevfbare yvfgraf gb jung ur fnlf naq jvyy nffhzr gurerf bayl sbhe bs gung bar yrsg, lrg svir bs gur bgure. Juvpurire unf gur jebat ahzore vf ba uvf urnq.

Pbagvahvat yvxr guvf, gur guveq cevfbare fhogenpgf obgu gur svefg ung naq gur frpbaq ung, naq lrg ntnva juvpu vf vapbeerpg vf ba uvf urnq.

Gurl pbagvahr yvxr guvf hagvy gurl ernpu gur svany cevfbare, jub fubhyq unir abj pbhagrq rvgure 4 be 5 erq ungf, naq gur bccbfvgr ahzore bs terra ungf. Juvpu rire unf bayl sbhe yrsg, ur'f jrnevat.

Ol guvf zrgubq, hayrff nalbar unf n fubeg nggragvba fcna, abobql fubhyq cbffvoyl qvr. Ohg V'q cebonoyl qvr, orpnhfr V unir n fubeg nggragvba fcna. Nsx, fpubby.

[Joe]

[size=0pt]I have a way, but only 9 would be guaranteed to survive.

Hrmm.... Prisoner 0 would wait 10 seconds if prisoner 1's hat were green and 20 seconds if his hat were red.  Prisoner 1 would do the same for prisoner 2, and so on. 
[/size]
Quote it for my answer.  :-\

Each prisoner must answer immediately as his turn begins or he will be shot.

Unless Sidoh added that later, in which case, good job. :)

[Sidoh]

x86] link=topic=8505.msg107615#msg107615 date=1170261080]
Each prisoner must answer immediately as his turn begins or he will be shot.

Unless Sidoh added that later, in which case, good job. :)

drake, sorry, I missed your post.  That's a clever answer, but it's not the one I'm thinking of.  I'll add that as another rule.

Joe, your answer is reasonably close, but you missed this:

    * The diagram is a mere representation of a possible configuration of hats.  The order and number of each color is purely random.