100 Prisoners And A Lightbulb 
Written by Mike James  
Wednesday, 10 August 2022  
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:
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 kstate 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 Information100 prisoners and a lightbulb  looking back Vladan Majerech Related ArticlesToo Good To Miss: The Robot Panda Problem  Fun CS Theory New Game Dots And Polygons Is NP Hard LZ Compression And The OneBit Catastrophe Best Laid Plans of Lions and Men 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
or email your comment to: comments@iprogrammer.info


Last Updated ( Wednesday, 10 August 2022 ) 