prisoner problem

[fred rosenberger]

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?

[Steve Fahlbusch]

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]

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]

Or that we're both wrong

[fred rosenberger]

I prefer my explanation.

:-)

[Ryan McGuire]

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]

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]

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]

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.

[Nathan Leniz]

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]

[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]

I liked this puzzle.

Are prisoners that smart?