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
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.
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'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".
Joined: Jan 30, 2000
[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".