# prisoner problem

posted 9 years ago

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?

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

posted 9 years ago
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

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.

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.

Ryan McGuire

Ranch Hand

Posts: 1073

4

posted 9 years ago

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.

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.

posted 9 years ago
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

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.

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.

posted 9 years ago

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.

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

Sheriff

Posts: 18671

posted 9 years ago

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

Posts: 132

posted 9 years ago

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

Sheriff

Posts: 18671