100 prisoners and a light bulb
100 prisoners are put in separate cells and taken one at a time, in an order chosen by the warden, to a room with a light switch that is initially off. Every prisoner will be brought to the room again and again, but no one learns anything except the state of the switch. On each visit a prisoner may toggle the switch, leave it, or declare that every prisoner has now visited the room at least once. A correct declaration frees everyone and a wrong one is fatal. Find a protocol, agreed on before the prisoners are isolated, that guarantees a correct declaration.
History and references
Solved by folklore.
The puzzle circulated widely around 2001 and 2002, reportedly having made the rounds of Hungarian mathematicians' parties, and it was analyzed by Dehaye, Ford and Segerman in 2003. The standard solution gives one prisoner the role of counter. Every other prisoner turns the light on the first time they find it off and never touches it again. The counter turns the light off each time he finds it on, and the 99th time he finds it on he knows that all 99 others have visited and declares. If there is one visit per day in random order, this simple protocol takes just under 30 years on average, and much work has gone into faster protocols, with the best known reported to need fewer than 3400 visits on average.
References
Solutions 0
Sign in or create an account to publish a solution