100 prisoners and the light bulb

Question

100 prisoners are in solitary cells. Each day the warden picks one prisoner at random (uniformly, with repetition) to visit a room containing a single light bulb with an on/off switch. The prisoner may toggle the switch or leave it, then returns to their cell. No other communication is possible. At any point, any prisoner may declare "Every prisoner has now visited this room at least once." If true, all go free; if false, all are executed. The bulb starts off (assume they know this). They strategize beforehand. Devise a strategy that is guaranteed to eventually free them.

Accepted Answer

Appoint one prisoner as the "counter." The other 99 are "ordinary." The rules for each role: Ordinary prisoner: The first time you enter the room and find the bulb off, turn it on. On every subsequent visit, and any visit where the bulb is already on, do nothing. Thus each ordinary prisoner turns the bulb on exactly once, ever. The counter: Whenever you enter and find the bulb on, turn it off and add 1 to your private count. If you find it off, do nothing. When your count reaches 99, declare that everyone has visited. Why it's correct. The bulb being on can only have been caused by an ordinar…

100 prisoners and the light bulb

Your answer

More Brainteasers questions