100 Prisoners & the Light Bulb
No talking — just one light bulb. Prove everyone has visited the room.
by MindYourPuzzle
A famous "coordination without communication" puzzle — the solution turns a light switch into a counting device.
100 prisoners are told: from now on, the warden will take them one at a time, in any order he likes, into a room containing a single light bulb with a switch. A prisoner may toggle the bulb or leave it, then is taken back to their cell. The order is arbitrary and endless — a prisoner may be brought in many times before another goes even once.
At any point, any prisoner may declare: "Every one of us has now visited the room at least once." If they're right, everyone goes free. If wrong, everyone is executed.
The bulb starts OFF. They get one meeting beforehand to agree on a strategy, then can never communicate again except through the bulb.
Is there a strategy guaranteed to eventually free them — and how many DISTINCT prisoners must turn the bulb ON for the plan to work?
(Answer with that number.)