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?  

Solution

This is not some trick question! The prisoners can actually figure out a way that uses a light bulb (which has only 2 states: on or off) as the only method of communication.

Key is that not every prisoner needs to do the same thing. What the prisoners should agree upon is that one of them is assigned the role of ‘The Counter’. That guy keeps a count in his head, starting at 1.

• A regular prisoner enters the room: he should do nothing when the light is already on. But when the light is off, and only if he has never turned on the light before, he should do so.
• The Counter enters the room: when the light is off, he should do nothing. When the light is on, he should turn it off, and increase the count in his head with 1. Since he started at 1, once he hits 100, he can safely announce that all prisoners have been in the room.

So the idea is that every prisoner announces his presence in the room by turning the light on. Until the counter receives this ‘signal’ and turns the light off, none of the other prisoners can announce their presence so they have to wait for the next opportunity. This way all prisoners will eventually be counted by The Counter. (Note that this assumes that the light is initially off; if not, the prisoners can simply agree to first switch it off when one enters the room on the first day.)

Hmm... this sounds like it will take a long time? Yeah it does — calculations show that this will on average take almost 29 years. That's a long time to wait for your freedom! There are actually complex methods of doing it faster... around 10 years even. But those require a page full of instructions and some advanced mathematics. Here's a paper if this doesn't scare you off!