100 prisoners and a light bulb
I have to admit that I was unaware of this interesting issue and only found out about it due to a recent review article. It deserves to be better known because it is a fascinating algorithmic puzzle.
The first question is what is the problem? As Vladan Majerech, the author of the investigative document puts it:
“100 prisoners are imprisoned in solitary cells. Each cell is windowless and soundproofed. There is a central living room with a light bulb; the bulb is initially off. No inmate can see the bulb from their own cell. the guard chooses a prisoner at random, and this prisoner visits the central hall; at the end of the day, the prisoner is sent back to his cell. While in the living room, the prisoner can turn on the light bulb if they wish. , the prisoner has the possibility to assert that the 100 prisoners went to the living room. If this claim is false (i.e. some prisoners still haven’t been to the parlor), all 100 prisoners will be shot for their stupidity. However, if true, all prisoners are released and inducted into MENSA, since the world can always use smarter people. Thus, the assertion should only be made if the prisoner is 100% sure of its validity. “
The prisoners are allowed to gather and discuss finding a plan that frees them all. The “game” continues until one of the prisoners claims that all 100 people have visited and they are all released or shot.
At first glance, it seems impossible – silly even, but it’s not. First of all, we must rule out “cheating” solutions which consist of making marks on the wall of the room or breaking the light bulb. We must also reject probabilistic solutions even if they promise release with probability close to one in the long term. We need a deterministic algorithm.
The key is to notice that the fixed frequency of visits means that it is possible to keep an account. However, this is not directly useful as you cannot stop when the count reaches 100 because some of the prisoners have visited the room more than once – this is random sampling with replacement. Of course, each inmate knows how many times he visited the room even if it is not a 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 a possible solution is quite easy to figure out. See if you can make progress before reading on:
- The first inmate must turn on the light each time it is turned off and he must count the number of times he has turned on the light.
- All other prisoners turn off the light the first time they find it on – otherwise they leave it alone.
- Once the first prisoner’s count reaches 100, they can be sure that every prisoner has visited the room and they can safely ask to be released.
Can you see why this works? The first prisoner is the reset – turning the light on when it’s off. The other prisoners only turn off the light once, regardless of the number of visits – so when the first prisoner has turned it on 100 times, they have all visited the bulb.
This is the “standard” solution, but how long do you think it takes for the prisoners to be released? An incredible 28 to 29 years with one prisoner a day – which is still a long sentence.
Are there better algorithms that reduce time spent in jail – that’s the real point of the puzzle.
If you want to know more, read the survey paper – but I don’t think I’m spoiling the fun by saying there are better algorithms. There is also a similar set of problems with n prisoners and a k-state signaling 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.
100 prisoners and a light bulb — looking back Vladan Majerech
Eight queens resolved!
Too Good to Miss: The Panda Robot Problem – Fun CS Theory
New Dots And Polygons Game Is NP Hard
The grasshopper problem
LZ Compression and the One-Bit Catastrophe
The best plans of lions and men
Cannibal animal games
To be notified of new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.
or send your comment to: [email protected]