100 prisoners are sentenced to life in prison in solitary confinement. Upon arrival at the prison, the warden proposes a deal to keep them entertained, certain that the prisoners are too dim-witted and impatient to accomplish it.
The warden has a large bowl containing the cell numbers of all the prisoners. Each day he randomly chooses one cell from the bowl, the corresponding prisoner is taken to the interrogation room, and the cell number is returned to the bowl.
While in the interrogation room, the prisoner will not be allowed to touch anything except the light switch, which the prisoner may choose to turn on or off.
The prisoner may make the assertion that all 100 prisoners have been in the room. If the prisoner’s assertion is correct, all prisoners will be released. If the prisoner is incorrect, the game is over and their chance to be freed is gone.
The prisoners are given one meeting to discuss a strategy before their communication is completely severed. The initial state of the light is OFF when the first prisoner enters the room.
What strategy should they adopt in order to ensure, with 100% certainty, that one of them will guess correctly and all be freed?
How many days did it take for the prisoners to be sure they have all visited the interrogation room?