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 prisoner toggles OFF->ON exactly once in their lifetime, only when they first enter and see OFF.
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.
6) Correctness: no non-counter contributes more than once; every non-counter eventually visits and can contribute under random fair selection.Answer: Use one counter prisoner counting 99 unique ON signals from the other prisoners.
Allowing non-counters to toggle multiple times causes overcount and false declaration.
How would strategy change if initial switch state were unknown?