100 Prisoners

Problem

• 100 prisoners in jail are standing in a queue facing in one direction.
• Each prisoner is wearing a hat of color either black or red.
• A prisoner can see the hats of all the prisoners in front of him in the queue, but cannot see his hat and hats of prisoners standing behind him.
• The jailer is going to ask the color of each prisoner’s hat starting from the last prisoner in queue.
• If a prisoner tells the correct color, then he is saved, otherwise executed.
• How many prisoners can be saved at most if they are allowed to discuss a strategy before the jailer starts asking colors of their hats.

Solution

At-most 99 prisoners can be saved and the 100th prisoner has 50-50 chances of being executed.

• The idea is that every prisoner counts the number of red hats in front of him.
• The 100th prisoner says red if the number of red hats is even. He may or may not be saved, but he conveys enough information to save 99th prisoner.