100 Prisoners with Red/Black Hats | Puzzles for Interview - Interview Preparation PDF Download

Introduction 

There are 100 prisoners standing in a queue facing in one direction, each wearing a hat of either black or red. The prisoners can see the hats of those in front of them, but not their own hat or the hats of those behind them. The jailer will ask each prisoner the color of their hat starting from the last prisoner in the queue. If a prisoner answers correctly, they will be saved, otherwise, they will be executed. The prisoners are allowed to discuss a strategy before the questioning begins.

Solution 1: Counting Red Hats

The prisoners can save at most 99 prisoners with this strategy. The 100th prisoner will have a 50-50 chance of being executed. The strategy involves each prisoner counting the number of red hats in front of them. The 100th prisoner will say "red" if the number of red hats in front of them is even. This conveys enough information for the 99th prisoner to determine the color of their hat.
If the 100th prisoner says "red," then there must be an even number of red hats in front of them. The 99th prisoner can then determine the color of their hat based on whether they see an even or odd number of red hats in front of them. If the 100th prisoner says "black," then there must be an odd number of red hats in front of them. The 99th prisoner can use the same logic to determine the color of their hat. This process continues with each prisoner using the previous prisoner's answer to determine their own hat color.

Solution 2: Sorting by Hat Color

Another strategy involves two random prisoners standing at the front of the queue. If they have the same hat color, the third prisoner will stand behind them. If their hat colors are different, the fourth prisoner will stand in between them. This process continues until all prisoners are sorted into two groups, with 50 wearing black hats and 50 wearing red hats. The last prisoner in the queue will then tell the color of the hat of the prisoner in front of them. The 51st prisoner will then change the color of their hat, indicating to the jailer that they have a different color hat than the previous prisoner.

Conclusion

Both strategies allow the prisoners to discuss a plan and increase their chances of survival. The counting strategy saves 99 prisoners, while the sorting strategy ensures that at least 50 prisoners are saved.