Difficulty: Hard · Puzzle 6 of 6 · Topic: Classic Brain Teasers
100 prisoners are isolated. A guard picks one random prisoner daily to visit a room with one light switch (initially OFF). Prisoners may agree on a strategy once beforehand. They can declare when everyone has visited the room at least once. How?
Use one designated counter and one-time signals from others.
1) Designate prisoner P0 as counter.
2) Every non-counter signals exactly once in their lifetime: the first time they enter and find the switch OFF, they turn it ON. If they enter and find it ON they must leave it alone and wait for a later visit.
3) P0 rule: whenever P0 enters and sees ON, set it to OFF and increment count.
4) Each increment corresponds to one unique non-counter prisoner having signaled.
5) When P0 reaches count = 99, P0 can safely declare all 100 have visited (P0 itself has obviously visited).
6) Correctness: no non-counter contributes more than once; every non-counter eventually visits and finds the switch OFF under random fair selection.
7) Expected duration: a simulation of 3,000 runs gave a mean of about 10,400 days (about 28 years); the range was roughly 7,300 to 15,000 days. This is why interviewers ask for the strategy, not the schedule.Answer: Use one counter prisoner counting 99 unique ON signals from the other prisoners.
Checked by running a model of the rule in a Python model. A computational check with a fixed seed: 300 simulated runs with the one-signal counter strategy all declare correctly, the mean is in the stated range, and the two-signal 2(n-1) rule never declares early even when the switch starts ON.
Letting a non-counter turn the switch ON more than once (or turning it ON when it is already ON) makes the counter overcount and declare too early; the one-time rule is the whole proof.
How would strategy change if initial switch state were unknown? Model answer: every non-counter signals twice (turns ON the first two times they find it OFF) and the counter declares at 2(n-1) = 198 ON observations. The initial state may contribute one spurious ON, so with 198 counted, even in the worst case every non-counter has signaled at least once (if one had not, at most 2*98 = 196 genuine + 1 spurious = 197 could be seen).
Nobody can see the others, so I pick one prisoner as the counter and give everyone else a one-time signal. A non-counter who finds the switch off turns it on, once in their life, and otherwise leaves it alone. The counter turns the switch off each time it is on and adds one to the count. When the count reaches 99, every other prisoner has signalled exactly once, so the counter declares that all 100 have visited. The trap is letting a non-counter signal twice, which makes the counter overcount and declare too early.