Death Trap !
One thousand prisoners are lined up, one behind the other, all facing forward. On each prisoner's head is a hat, either red or black. Each prisoner can see the hats of all the people in front of him, but he cannot see his own hat and he cannot see the hats of the people behind him. Starting with the prisoner in the back of the line (the one that can see all 999 other prisoners), the prison warden asks the prisoner what color hat he is wearing. Each prisoner can hear the guesses of all of the prisoners behind him. If a prisoner correctly guesses his hat color, he is set free. If he guesses wrong, he is executed.
The prisoners are allowed to agree in advance on an algorithm to use, and you can assume that they all agree to follow the agreed-upon algorithm. The prisoners are NOT allowed to provide each other with any additional clues once the hats are placed on their heads. (For example, tapping shoulders or modulating their voices are not allowed.) The only information each prisoner has is the guesses for the prisoners behind them, and the hats on the prisoners in front of them. Design an algorithm for the prisoners to follow that saves the most prisoners from execution. What is the maximum number of prisoners you can guarantee to save?
The answer is 999.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
There must be a sacrifice: the first one. To make things easier, let's make an analogy and visualize 10 prisoners.
The Very important assumptions is that "Each prisoner can hear the guesses of all of the prisoners behind him".
The First prisoner to be interrogated can see 9 hats. 9 is an odd number hence it's the addition of an even number and an odd number.
The solution is for the first prisoner to say the colour of the number of even number hats he sees (for example if there are 4 red and 5 blue, he will say Red). Hence the 2nd prisoner who can see the 8th remaining hats, can count the number of Red and Blue hats.
example of mechanism: He sees 4 Red and 4Blue. He knows he's blue, and will say blue. There are now two even numbers of hat and the information that there was and even number of red hats. Hence the one after will say the colour that is an odd number in the hats. Hence all have the information of which colour is "oddly" or "evenly" represented, can count and answer etc.