Death Trap !Computer Science Level 2
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?