One Switch, A Hundred Prisoners

  • Hard
  • Logical puzzles
  • Tests: Building a counter out of one bit of shared state

The puzzle

A hundred prisoners will be taken, one at a time in any order and as often as the warden likes, into a room containing a single light switch. Each may flip it or leave it. Every prisoner will visit infinitely often, but nobody knows the order or the switch's starting position.

At any point any prisoner may declare that all 100 have now visited the room. If right, everyone is freed; if wrong, everyone is executed. They may agree a strategy beforehand and never communicate again. What should they agree?

Stuck?

One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.

Hint 1

One of them should have a different job from the other 99.

Hint 2

The switch can carry a signal: an ordinary prisoner turns it on once in their life, and one designated counter turns it off and keeps a tally.

Show the answer Hide the answer

Appoint one counter. Each of the other 99 turns the light on exactly once in their life, and only if it is off. The counter turns it off each time it is on, counting as they go, and declares when the count reaches 99.

How to get there

The 99 ordinary prisoners follow one rule: if the light is off and you have never turned it on, turn it on; otherwise do nothing. So each of them contributes at most one "on" in their lifetime, and exactly one eventually, since they visit infinitely often and the counter keeps resetting the switch.

The counter follows another: if the light is on, turn it off and add one to your tally; otherwise do nothing. Every increment therefore corresponds to a distinct ordinary prisoner having visited - nobody can contribute twice.

When the tally reaches 99, all 99 others have visited, and the counter has obviously visited too, so all 100 have been in the room and the declaration is safe. The unknown starting position is the one trap: if the light might start on, the counter should ignore the first "on" they see, or equivalently wait for a count of 100 - otherwise a switch that began on could be miscounted as a prisoner.

The technique worth keeping

When a channel carries one bit, use it as a token rather than a message. Asymmetry is what makes it work: a single designated counter turns an ambiguous shared bit into an unambiguous tally, and the protocol must also account for the channel's unknown initial state.