“Tomorrow, at the execution, I will give you a chance to go free. I will queue you up randomly and put a hat on your head. The hat is either red or blue. You cannot see the color of your own hat, only those of the prisoners in front of you. You will not be allowed to look behind you, nor are you allowed to touch, or talk to the other prisoners in any way. To be clear, the last prisoner will only see the 19 prisoners in front of him. The second-to-last prisoner will only see the 18 prisoners in front of him, and so on.”
The warden grins. “Starting with the last person in the row, I will ask a simple question: What is the color of your hat?”
“If he answers correctly, I will set him free. But you can guess what happens when the answer is wrong. He will be put to death immediately. Regardless of the outcome, I will then move to the prisoner in front of him, and ask the same question. From the last one in the row to the first one, you will all be asked.”
The warden lowers his voice. “And another thing. I will tolerate no cheating. If anyone answers anything besides ‘red’ or ‘blue’, I will execute you all right then and there!”
As he leaves, the warden sarcastically shouts: “Good luck tomorrow!”
The twenty prisoners can still talk freely during the night, so they are having heated discussions about how to free as many prisoners as possible. This turns out to be a difficult task. What is the most prisoners that can definitely be saved, and how?
Solution
It's all up to the first guy that is asked; in other words the prisoner at the end of the row. And if that isn't enough, this is the unluckiest position in the queue to be in. His chance equals that of the toss of a coin.This last prisoner can see 19 prisoners in front of him. Some of them have blue hats and he is to count how many. He says ‘blue’ if that number is odd, or ‘red’ if it's even. All the other prisoners are to pay close attention to what's been said, not only by the last prisoner but everyone behind them. Let's assume he says ‘blue’.
Prisoner #20 has now either been released, or executed, and prisoner #19 is up next. He too should count the number of blue hats. Consider the information now available to him. If he sees an odd number then he still sees the same number of blue hats as the prisoner behind him did — his own hat must be red! If he sees an even number, it must be because his own hat is blue and is not counted this time where it was before. So the prisoner can always give the correct answer. To continue the example I'll go for ‘blue’.
It's prisoner #18's turn. He has now heard ‘blue’ two times. That means the number of blue hats was odd, then went to even. In the same way he can deduce his own hat color, by counting the number of blue hats in front of him. Still even? Red. Odd? Blue. This time, assume the answer is ‘red’.
Since prisoner #18 said ‘red’, nothing has really changed for prisoner #17, and there are still an even number of blue hats. Prisoner #17 does the same as the prisoners behind him and counts the blue hats. Once again, still even? Red. Odd? Blue.
This can continue all the way down the line! With this method, 19 prisoners can be saved for sure. Only the unfortunate 20th prisoner has to accept a fifty/fifty chance. Wish him luck!
Is there a answer?
ReplyDeleteThis is ridiculous. Nowhere does it say in the puzzle that there are an equal number of red and blue hats. There could be 18 red and 2 blue. Where does that leave your stupid puzzle??
ReplyDeleteHe is not stupid, and yes no where it is mentioned that equal number of red and blue caps, it can be random.
ReplyDeleteTake pen and paper and do some mathematics you'll find how the calculations done.
Let's take your example, 18 R & 2 Blue
20th prisoner having 50-50 chances of survival, but he passes correct information to other.
Case 1: 20th Prisoner said Blue => in front of him he can see max 19 caps. So
there could be 17 Red and 2 Blue OR 18 Red and 1 Blue, so for simplicity assume all presioners decided to say Blue if count is odd, Red if blue count is even.
So in this case, take example of 18 Red and 1 Blue => He can see odd number of blue caps in front of him which means Blue count is Odd and Red count is Even for other. Definitely they don't know the exact number of caps.
Now Turn of 19th prisoner=> If he sees Blue count is still odd [so the case would be 18,1] => he can see max 18 caps in front of him.
which means either 17,1 or 18, 0], if still blue count is odd he simply say Red or if blue count is even then say blue. Because he knew what was old answer by 20th prisoner. Let's say he said Red.[Blue count still hold old count, so he says Red]
Now 17th prisoner know last statement was Red and prior to that it was Blue which means still Blue have the odd count and he count another 16 caps
either (16, 0 or 15, 1). If this prisoner sees even no of caps of blue which are 0 now which means he doesn't see any blue cap(as per example) then he is wearing blue cap and rest are red. Let's say he said Blue.
16th prisoner knows that 20th prisoner said Blue, 19th prisoner said Red, 18th said Blue, 17th said Blue, now 16th Prisoner know there are 2 Blue in a row which means Blue count went even on 17th prisoner chance. So now Blue count is even, he counts next 15 caps in front of him and he counts Blue is still even (0 in our case) and Red is odd which means he is wearing Red cap.
Now I hope you would have understood the intuition behind this question.
:) ^_^ Thanks