100 Prisoners and a Lightbulb
While working on the second homework for this class I was suddenly reminded of an old riddle, simple in setup but fiendishly difficult to solve. Here’s how it goes:
There are 100 prisoners in solitary cells. There’s a central living room with one light bulb; this bulb is initially off. No prisoner can see the light bulb from his or her own cell. Everyday, the warden picks a prisoner equally at random, and that prisoner visits the living room. While there, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting that all 100 prisoners have been to the living room by now. If this assertion is false, all 100 prisoners are shot. However, if it is indeed true, all prisoners are set free and inducted into MENSA, since the world could 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 one night in the courtyard, to discuss a plan. What plan should they agree on, so that eventually, someone will make a correct assertion?
At this point, I’d highly recommend sitting down and thinking about the problem. There are a few simple, easy solutions that would only succeed in a length of time far exceeding the lifespan of our prisoners. For example, the prisoners could number themselves 0 to 99 and turn/leave the light on if randomly called in the correct order, starting with prisoner 0 on day 0, and conversely turn the light off if any aberration to the order is found. If prisoner 99 enters the room and the light is on, he calls the warden. This means that on average prisoners can expect to wait approximately 2.7 * 10199 years before they get out of jail. That’s a long time. So long, that it is difficult to describe how long that is. It is about 2 * 10189 times longer than the age of the universe. OK – clearly that won’t be good enough.
There are, it turns out, many solutions to this problem that get increasingly efficient and increasingly complex. Try and take a few minutes to find a faster solution than the one described above! There are nearly infinite ways to solve the riddle.
OK, so you’ve got a solution? Time to take a trip down this rabbit hole:
http://anttila.ca/michael/100prisoners/
Here michael antilla goes deep into finding the best possible solution, which is incredibly interesting to compute and model. It turns out that a system that takes under 10 years is possible.
Drawing things back to the class, I think this riddle does a wonderful job of showing the complexity that can be contained within even a ‘simple’ game theory question – to flip, or not to flip, the lightswitch. The network of people – the prisoners – and their strategy of working together and signaling to each other even through the most limiting of medium allows (with enough intelligence) a solution that is far better than initially seems possible.