The Prisoners and the Light Bulb Coordination Puzzle

A single counter and a fixed toggle rule let one prisoner certify with certainty that all 100 have visited the room, after about 10,400 expected days.

100 prisoners are told that, starting on some day, exactly one prisoner will be brought to a room containing a single light bulb and its switch, chosen uniformly at random each day and possibly repeated many times before everyone has visited. A strategy exists that lets one designated prisoner declare, with total certainty rather than high probability, that every prisoner has visited the room at least once, and under the standard version of that strategy the expected number of days before that declaration can be made correctly is about 10,400, close to 28 years of daily visits.

Before the process starts, the prisoners meet and agree on a strategy, but from then on the only information any prisoner receives on a given day is whether the bulb is currently on or off, and each prisoner may choose to toggle the switch or leave it alone before leaving the room. No other communication between prisoners is possible once the process begins.

A single prisoner must eventually be able to announce that every one of the 100 has visited at least once, and the announcement has to be correct with certainty, not merely likely to be correct, which rules out any strategy that only produces a high probability guess.

One prisoner is designated the counter in advance. Every non-counter follows one rule for the entire process, applied only the first time that specific prisoner ever finds the bulb off, on that single occasion turn it on, and never touch the switch again after that, regardless of what the bulb shows on any later visit. The counter follows a different rule, on every visit, if the bulb is on, turn it off and add one to a private tally kept in her head.

The tally the counter keeps only increases when a non-counter has turned the bulb on, and each non-counter can only turn the bulb on once in the entire process. Once the counter's tally reaches 99, one for every prisoner other than herself, she can declare with certainty that all 100 prisoners have visited the room, since the tally is an exact count of distinct non-counters who have visited, not an estimate.