Solution
The Switch of Unknown State
Show the problem again
One hundred prisoners are taken, one per day in an arbitrary order in which every prisoner is chosen infinitely often, into a room containing a light bulb with a switch. The bulb's initial state (on or off) is unknown to everyone and cannot be assumed. Nobody else sees the bulb, and the room offers no other communication. Prisoners agree in advance on this protocol. - Prisoner A is the counter. On a visit, if the bulb is on, A turns it off and adds 1 to a tally. Otherwise A does nothing. - Every other prisoner keeps their own count of how many times they have switched the bulb on. On a visit, if the bulb is off and that count is below 2, they turn it on and add 1 to their count. Otherwise they do nothing. A declares "everyone has visited" as soon as the tally reaches T. What is the smallest T for which the declaration is guaranteed to be correct, no matter the initial state and the visiting order?
Worked solution
The answer is 198. Each of the 99 other prisoners can switch the bulb on at most twice, and only after having visited, so at most 99 × 2 = 198 genuine signals exist. The tally can also be inflated by one extra count if the bulb began on, since A will then count a signal that nobody sent. Suppose one prisoner has not visited. The other 98 can contribute at most 196 signals, plus one phantom count from an initially lit bulb: a maximum of 197. A tally of 197 can occur with someone missing, so T ≥ 198. A tally of 198 cannot, so T = 198 is safe. It is also reached eventually: every prisoner keeps returning, so each eventually sends both of their signals (the bulb is turned off by A at each visit following a signal), giving at least 198 counts in total. A search over all reachable configurations for smaller crowds (3 to 6 prisoners) confirmed that the largest tally reachable with someone missing is 2(n − 1) − 1 for n prisoners, so the safe threshold is 2n − 2, which is 198 for n = 100.
Source: Variant of the classic prisoners-and-light-switch puzzle (initial state unknown) in wide circulation; no traceable original source. Statement written for AxiomIQ.