I have to admit that I was unaware of this interesting problem and only discovered it due to a recent review paper. It deserves to be better known as it is a fascinating algorithmic puzzle.

The first question is what is the problem? As Vladan Majerech, the author of the survey paper poses it:

"100 prisoners are imprisoned in solitary cells. Each cell is windowless and soundproof. There’s a central living room with one light bulb; the bulb is initially off. No prisoner can see the light bulb from his or her own cell. Each day, the warden picks a prisoner equally at random, and that prisoner visits the central living room; at the end of the day the prisoner is returned to his cell. While in the living room, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting the claim that all 100 prisoners have been to the living room. If this assertion is false (that is, some prisoners still haven’t been to the living room), all 100 prisoners will be shot for their stupidity. However, if it is indeed true, all prisoners are set free and inducted into MENSA, since the world can always use more smart people. Thus, the assertion should only be made if the prisoner is 100% certain of its validity."

The prisoners are allowed to get together and talk about finding a plan that sets them all free. The "game" continues until one of the prisoners claims all 100 have visited and they all go free or are shot.

At first sight it seems impossible - silly even, but it isn't. First off we have to discount "cheating" solutions that involve making marks on the wall of the room or smashing the light bulb. We also need to reject probabilistic solutions even if they promise release with a probability approaching one in the long run. We need a deterministic algorithm.

The key is noticing that the fixed frequency of visits means that it is possible to keep a count. However this isn't directly useful as you can't stop when the count reaches100 because some of the prisoners my have visited the room more than once - this is random sampling with replacement. Of course, each prisoner knows how many times they have visited the room even if this is not global knowledge.

The best way to see that there might be a solution is to try the problem with a smaller number of prisoners, but one possible solution is fairly easy to understand. See if you can make any progress before reading on:

1. The first prisoner has to turn the light on whenever it is off and they have to keep a count of the number of times they have turned the light on.
2. All of the other prisioners turn the light off the first time time they find it on - otherwise they leave it alone.
3. Once the first prisioner's count reaches 100 they can be sure that every prisoner has visited the room and they can safely claim to be let go.

Can you see why this works? The first prisoner is the reset - turning the light on when it is off. The other prisoners turn the light off just once, no matter how many times they visit - hence when the first prisioner has turned it on 100 times they have all visited the light bulb.

This is the "standard" solution, but how long do you think it takes  for the prisioners to be released? An amazing 28 to 29 years with one prisoner per day - which is still a long sentence.

Are there better algorithms that reduce the time in jail - this is the real interest in the puzzle.

If you want to know more read the survey paper - but I don't think I'm spoiling any fun by saying that there are better algorithms. There is also a set of similar problems with n prisioners and a k-state signalling device, nAk and nBk, where the initial state of the signal is known and nCk where it is unknown. The problem we looked at is 100A2.

More Information

100 prisoners and a lightbulb -- looking back Vladan Majerech

Related Articles

Eight Queens Solved!

Too Good To Miss: The Robot Panda Problem - Fun CS Theory

New Game Dots And Polygons Is NP Hard

The Grasshopper Problem

LZ Compression And The One-Bit Catastrophe

Best Laid Plans of Lions and Men

Irrational Guards

Cannibal Animal Games     

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info