There are 10 prisoners are in 10 different cells of a prison. There is no way in which they can communicate with each other.
Each night, the warden picks one of the 10 prisoners and that prisoner is supposed to spend the entire night in the central living room. There is one bulb in the living room which can be switched on or off.
Warden puts a condition, “If any of the prisoner can tell with certainty, that all the other prisoners have spent night in the central living room, then he will free all of them. But, If the prisoner says that all the other have spent night in the living room, but that is not true, then all the prisoners will be killed”. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.
Before the random picking begins, the prisoners are allowed to get together and make some strategy. But, once the strategy is made, then a prisoner cannot communicate with any other prisoner.
What plan should they agree on, so that eventually, someone will make a correct assertion?
From the problem it is clear that there is no limit on the number of times that a prisoner can go into the living room (because warden picks randomly), the problem is that they will not be able to communicate with each other that they have spent the night in the cell.
Therefore one person is chosen as the counter.
Every time any prisoner is selected other than counter person , he will follow these steps.
- If the bulb is already switched on then he will do nothing.
- If he has never switched on the bulb, and the bulb is off then he will switch on the bulb
- If he has switched on the bulb earlier, then he will do nothing (one prisoner will switch on the bulb only once).
If person who is made ‘counter’, goes to the living room, then,:
- If the bulb is on then he will increment the counter by one, and switch it off.
- If the bulb is already off then he will do nothing.
When the counter switch off the bulb 9 times, it will indicate that each of the other prisoner has already been to the living room at least once, because one prisoner is switching on the bulb only once. Hence at this time, the counter can declare that all the prisoners have spent the night in the cell.