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