aspose file tools*
The moose likes Programming Diversions and the fly likes prisoner problem Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "prisoner problem" Watch "prisoner problem" New topic
Author

prisoner problem

fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11406
    
  16

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?


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Steve Fahlbusch
Bartender

Joined: Sep 18, 2000
Posts: 570
    
    7

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
Bartender

Joined: Oct 02, 2003
Posts: 11406
    
  16

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

Joined: Sep 18, 2000
Posts: 570
    
    7

Or that we're both wrong
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11406
    
  16

I prefer my explanation.

:-)
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1010
    
    3
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
Bartender

Joined: Oct 02, 2003
Posts: 11406
    
  16

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

Joined: Sep 18, 2000
Posts: 570
    
    7

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.
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
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.


"I'm not back." - Bill Harding, Twister
Nathan Leniz
Ranch Hand

Joined: Nov 26, 2006
Posts: 132
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.


The very existence of flamethrowers proves that at some time, some where, some place, someone once said to themselves "I'd really like to set those people on fire over there, but I just can't get close enough".
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
[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".
Vikas Kapoor
Ranch Hand

Joined: Aug 16, 2007
Posts: 1374
I liked this puzzle.

Are prisoners that smart?
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: prisoner problem