Solution
Prisoners and the Lightbulb
Show the problem again
100 prisoners will be taken, one at a time in an arbitrary (possibly repeating) order, into a room containing a single light switch, initially off. At any visit, a prisoner may declare "all 100 of us have visited the room." A correct declaration frees everyone; a wrong one is fatal. The prisoners may strategize once beforehand. In the standard guaranteed strategy, one prisoner is designated the counter and everyone else signals with the switch. How many times must the counter find the light switched on before safely declaring?
Worked solution
The answer is 99. Every non-counter prisoner turns the light on only if it is off and they have never turned it on before; otherwise they do nothing. The counter, whenever finding the light on, turns it off and increments a tally. Each on-signal is a distinct prisoner, so when the tally reaches 99, all 99 others have visited and the counter declares with certainty. Success is guaranteed, though the expected wait is on the order of 10,000 days.
Source: Classic distributed-protocol puzzle in wide circulation; no traceable original source. Statement written for AxiomIQ.