100 prisoners enter a room one at a time in an order chosen adversarially, each entering infinitely often. The room holds one switch, which each visitor may toggle or leave. Any prisoner may declare that all 100 have visited, freeing them if true and killing them if not. The starting switch position is unknown. Give a strategy that always works.

100 prisoners enter a room one at a time in an order chosen adversarially, each entering infinitely often. The room holds one switch, which each visitor may toggle or leave. Any prisoner may declare that all 100 have visited, freeing them if true and killing them if not. The starting switch position is unknown. Give a strategy that always works.

Approach: Appoint one prisoner to keep the tally and let everyone else send at most a fixed number of signals, with the budget chosen so that an unknown starting position cannot corrupt the count.

Appoint one counter, let every other prisoner turn the switch on exactly twice in his life and only when he finds it off, and let the counter turn it off and add one each time he finds it on, declaring at a tally of 198. Each of the 99 others contributes at most 2, so a tally of 198 forces all 99 to have contributed at least once, which with the counter covers everyone. The doubling handles the unknown initial state: if the switch started on, one count is spurious, and since the 99 others can supply 198 genuine flips the tally still reaches the target. With a known off start, one flip each and a target of 99 works. The counting argument uses no timing, so any visiting order is fine.

Follow-up: What is the expected time to freedom under this strategy if visitors are chosen uniformly at random each day?

Key concepts: counter strategy, unknown initial state, counting argument.