• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

prisoner problem

 
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Four prisoners are due to be sentenced. The Judge, being a nice guy, says "I'm going to line you all up, one behind the other, all facing front. So prisoner A can only see a wall. B can see A only. C can see both A and B. D can see all three of the others.

Each of you will get either a black hat, or a white hat, but you cannot see the hat on your head - only the hats in front of you.

I will start with D, and ask you what color. You can say "black" or "white" - those are your only options. If you are correct, you go free. if you are wrong, you spend life in prison. You have until tomorrow morning."

The prisoners get together, talk about it, and one of them says "I know a way we can garantee 3 of us go free".

What was his plan?
 
Bartender
Posts: 612
7
Mac OS X Python
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
D says one color (say white) if he sees an even number of white hats.
D says other color (black) if he sees an odd number of white hats.

sucks to be D
 
fred rosenberger
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Good!!! somebody posed this to me last night, and i didn't come up with the answer before i left.

I thought i had it this morning, so i posted it here to see what answers ranchers would come up with.

We agree, so i take that as a good sign i was right.
 
Steve Fahlbusch
Bartender
Posts: 612
7
Mac OS X Python
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Or that we're both wrong
 
fred rosenberger
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I prefer my explanation.

:-)
 
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Ok, let's say that the prisoner that gets picked to be D decides that if he's going down he's going to take someone with him.

As Prisoner C, do you have any way to know if D told the truth? Does that change your strategy?

Same questions for Prisoner B.

Same questions for Prisoner A.
 
fred rosenberger
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
hmmm... assuming that all four agree to the plan, they pick D, and then D decides without telling anyone else he's going to screw the other guys, I don't believe C can know.

assume A-C are all wearning black hats. so the plan would have D say "white" (0 white hats), so he lies and says "black".

C now thinks that there must be an odd number of white hats. he sees two whites, so he has to think his is white, and says so. he is given his life sentence.

But now B knows that D lied, assuming he hears what happens to C. knowing D lied, he knows D should have said white, and there should be an even number of white hats. he knows C had a black hat, and knows A has a black hat. therefore, he has to have a black hat, says black, and goes free.

A can do a similar thing.

and i think the logic would hold for other cases.

I think the problem comes if D randomly chooses. i'm not sure, and don't have time right now to work through it, but i think that there could be a case where the right positioning of the hats and the right random statement, C could go free, and B could get screwed. but i'm not sure.
 
Steve Fahlbusch
Bartender
Posts: 612
7
Mac OS X Python
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If D lies, anyway you look at it, poor old C is in trouble - has no way of knowing until sentenced for life. And D still has a 50/50 chance, but if he lies C is old news.

Now if the Judge waits until all are done, then it's pretty much the same for B and A.

But if he lets all know if C was right or wrong before B and A answer, then at least those 2 would walk.
 
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If we're going to consider the possibility of D lying, why not also consider the possibility that the other prisoners might know D well enough to anticipate this and maybe correct for it? Then things get really hairy. C could be, say, 90% sure that D will lie out of spite. So maybe C corrects for that, and does the opposite of what D's answer would have indicated. And he survives. But now B has to decide - should he assume that D lied and C corrected for it? Or that D did not lie, and C did not correct for it? Similarly, A must consider whether he thinks D lied and whether B and/or C corrected for it. And what if D anticipates that the others will correct for his lie, and instead tells the truth, just to spite them? And what if the others anticipate this move? There's really a never-ending cascade of feedback here, once we assume that the prisoners might not act altruistically.
 
Ranch Hand
Posts: 132
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I've heard this very same riddle, but told in a MUCH different way, and with different results.

The one I know of is how can one of them go free for sure, if the warden passes out two black hats and two white hats.

I'd agree with the even/odd response and faith that the riddle won't allow the 4th prisoner to lie.
 
Jim Yingst
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
[Nathan]: I've heard this very same riddle, but told in a MUCH different way, and with different results.

Well, I guess I would have to question what the heck you mean by "very same riddle".
 
Ranch Hand
Posts: 1374
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I liked this puzzle.

Are prisoners that smart?
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic