The 100 Prisoners And The Light Bulb

One hundred prisoners have been newly ushered into prison. The warden tells them that starting tomorrow, each of them will be placed in an isolated cell, unable to communicate with each other. Each day, the warden will choose one of the prisoners at random, and place him in a central interrogation room for an hour. A prisoner can be chosen any number of times; thus it could happen a prisoner is chosen multiple times while another is yet to be picked. The interrogation room contains nothing but a light bulb and a light switch. The prisoner can see whether the light is on or off, and – if he wishes – can toggle the light switch. He also has the option of announcing that he believes all prisoners have visited the interrogation room at some point in time.

If this announcement is true, then all prisoners are set free, but if it is false, all prisoners are executed. So obviously the announcement should only be made if the prisoner is 100% certain that it is true!

The warden leaves, and the prisoners huddle together to discuss their fate. This is the last time they can speak with each other! Can they devise a system that will guarantee their freedom?