Ages ago, a king named Prasenajit Singh used to rule over Magadh Empire. He had hundreds of prisoners. Once, ahead of Diwali celebrations, the king decided to reward some of the intelligent prisoners with good conduct. Hence he lined up exactly 100 prisoners with best behavior. He ordered to play a game with them. All the winning prisoners would be set free on the auspicious occasion of Dhanteras.
Financial solution every stock broker should read
The rules of the game go like this:
- All prisoners (100 of the selected ones) were lined up in a single row and made to wear hats of either red or green color.
- The king has infinite hats of both the colors. So we don’t know number of red hats or the green hats.
- All prisoners are standing in such a way that, anyone can see color of hats for all prisoners standing ahead of him. But no one can see color of his hat or of those prisoners standing behind him.
- Those prisoners who will be able to predict color of their hat correctly would be freed.
- First, the last prisoner in the row would be questioned (The prisoner who knows color of hats for all prisoners except his/her own). Each prisoner can hear answers of all other prisoners, but would never know whether those answers were correct or not.
- Before start of the same, prisoners can talk to each other and make any strategy. But once they wear the hats, they wouldn’t be allowed to communicate with anyone.
- When asked, prisoners would only be allowed to speak color of their hat, “Red” or “Green”.
If anyone breaks any rule, all the prisoners would be killed by throwing into boiling oil. To communicate anything more than their guess of red or green by coughing or shuffling would be considered breaking the rules.
What is the maximum number of prisoners that can be freed for sure?
Assume that all the prisoners, the king and the referee of the game are extremely intelligent people. They all have ample amount of time to decide on the best suited strategy.
The strategy prisoners should devise should as follows:
The last prisoner (first to answer) would count all the red hats he can see (Q) and then answer
– “Green” if the number is odd or
– “Red” if the number is even.
Each subsequent prisoner keeps track of the number of red hats known to have been saved from behind (X), and counts the number of red hats in front (Y).
If Q was even, and if X&Y are either both even or are both odd, then the prisoner would answer green. Otherwise the prisoner would answer red.
If Q was odd, and if X&Y are either both even or are both odd, then the prisoner would answer red. Otherwise the prisoner would answer green.