Puzzle 13: 100 Prisoner + One Light Bulb

Puzzle 13: There is a prison with 100 prisoners, each in separate cells, which are sealed off, soundproof and windowless. There is a lobby in the prison with a lightbulb in it. Each day, the warden will pick one of the prisoners at random (even if they have been picked before) and take them out to the lobby. The prisoner will have the choice to flip the lightbulb switch if they want. The lightbulb starts in the "off" position.

When a prisoner is brought out to the lobby, he also has the option of saying "Every other prisoner has been brought out to the lobby." If a prisoner chooses to say this and it is true, all the prisoners will go free. However, if a prisoner chooses to say this and it's wrong, all the prisoners will be executed. So a prisoner should only say this if he knows it is true for sure.

Before the first day of this process begins, all the prisoners are allowed to get together to discuss a strategy to eventually save themselves.

What strategy could they use to ensure their eventual salvation?
Show Solution

Solution:
Make one of the prisoners the "lead" prisoner. This prisoner is the ONLY one who is allowed to turn the light off.

Each time any of the other prisoners goes into the lobby, if the light is off, they will turn the light on, but only if they've never turned it on before. This means that each prisoner will only ever turn the light on once.

Meanwhile, every time the lead prisoner goes into the lobby, he will turn the light off if it's on. He will keep track of the number of times he has turned the light off.

Once the lead prisoner turns off the light for the 99th time, he knows that every other prisoner has turned the light on once (and thus has been in the lobby). At this point, he may say that all the prisoners have been to the lobby, and they will all go free.