100 prisoners are lined up by an executioner, who places a red or blue hat upon each of their heads.
The prisoners can see the hats of the people lined up in from of them, but they cannot look at the hats behind them, or at their own.
Starting at the back of the line, the executioner asks the last prisoner to state the colour of his hat.
In order to live, the prisoner must answer correctly. If he doesn’t, he is killed ‘instantly and silently.’
This means that the other prisoners will hear the answer, but will not know whether or not it was correct.
The night before the line-up, the prisoners can discuss a strategy to help them survive. What should they do?
All Prisoners need to agree on this idea,through which 99 of the prisoners can be saved with 100 percent certainty, while the remaining prisoner will have a 50/50 chance of survival.
The 1st prisoner to speak will say ‘blue,’ if the number of blue hats he sees in front of him is even, or ‘red’ if he sees otherwise.
Thus ,the rest of the prisoners can figure out what their own hat colours will be based on the hats they see in front of them, and the responses they’ve heard behind.