The Prisoners and the Light Switch

Unlike the hundred-prisoners puzzle, which is about maximising a probability, this one asks for a strategy that succeeds with certainty — no luck involved, just a guaranteed eventual announcement. That changes what kind of solution you should be looking for.

The puzzle

100 prisoners are in solitary cells. There is a room with a single light bulb and switch, currently off. Every day, the warden picks one prisoner at random (with repeats allowed, and no guarantee everyone gets picked equally often) to visit the room alone; that prisoner may toggle the switch or leave it, then leaves. At any point, any prisoner may declare "we have all visited the room at least once." If they're right, everyone goes free; if wrong, everyone is executed. Before the process starts, the prisoners may agree on a strategy. Devise one that guarantees a correct declaration eventually.

Why "just toggle it on your first visit" fails. If every prisoner turns the light on the first time they see it off, nobody can distinguish "the light is on because I turned it on" from "the light is on because someone else did" — there's no way to count how many distinct people have visited.

The fix: designate a counter. Before the process starts, the prisoners name one person — say, prisoner A — as the sole "counter." Every prisoner except A follows this rule: the first time (and only the first time) they enter the room and find the light off, they turn it on. On every other visit, they leave the switch alone, whatever its state.

Prisoner A follows a different rule: every time A enters and finds the light on, A turns it off and increments a private mental count. A never turns the light on. Once A's count reaches 99, A declares that all 100 prisoners (the 99 others plus A, who obviously knows they themselves exist) have visited.

Why the count is exact. Each of the 99 non-counters turns the light on exactly once, ever, no matter how many times they revisit the room. A only turns the light off, never on, so every "on-to-off" event A performs corresponds to exactly one distinct non-counter's first visit. When A's tally hits 99, all 99 have visited — and A's own presence in the room to observe this makes 100.

The same asymmetric-role trick generalises: if a system needs to know "has every one of $n$ agents acted at least once," designating one dedicated observer with a one-way signal (increment-only, never decrement) turns a communication-starved counting problem into an exact one.