Skip to Content

100 prisoners and a lamp

A prison holds 100 inmates, each in a sealed cell with no way to meet or communicate. They follow a regular daily routine (meals and sleep). Each evening after dinner, the warden randomly selects one inmate for ten minutes of exercise alone in the yard. Each inmate has a 1% chance of being chosen that day, independent of past selections.

The yard has a lamp and a switch that controls it. Only inmates may flip the switch; the lamp is reliable and never fails or runs out of power. Nothing that happens in the yard (including the lamp) can be observed from the cells.

One day the warden gathers all 100 inmates and announces: if someday an inmate reports that every inmate has exercised at least once (counting from the day after this meeting), and that is true, everyone goes free; if the report is wrong, everyone is executed immediately.

The inmates may agree on a strategy now, then return to isolation with no further contact.

Assume every inmate wants freedom but will not take even the slightest risk of execution (so anyone who reports that all have exercised must be able to prove it by rigorous logic, not probability). Assume inmates (and the warden) live forever, which explains the zero tolerance for risk. The only yard state they can change is whether the lamp is on or off (no other marks allowed).

Question: Is there a strategy that guarantees release after sufficiently long time?