“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?”
Recently, my friend shared with me this puzzle that’s apparently been floating around the web/universities.
Method 1:
Assign different protocols:
1) For the first 99 persons, on their first time in, they have to turn on the light bulb. Subsequent times they enter the room, they leave it off. (Fulfills uniqueness condition of each entry)
2) Only one person, the 100th person, will be turning off the switches and counting how many times the switches have been toggled off. (Make sure to choose someone who is responsible and have a good memory here!)
3) Once the last person has counted 99 times that the light has been turned on, He/She can feel safe to call that everyone has entered the room already.
Method 2:
In blocks of 100 days, assign everyone the same protocol:
1) If it’s the first time you enter, leave the light switch off.
2) If it’s the second or more time you enter, turn on the light switch or leave it on.
3) If you enter on a day which is a multiple of 100 and see the lights on, turn it off and reset the counter. However, if you see that on the multiple of 100th day, the light is still off, call that everyone has entered the room.
Here’s a link to the paper about calculating the O(n) time complexity for the solutions by Berkeley’s department of CS: https://www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBulb.pdf
Thanks to my friend Arthur Lee for sharing this puzzle and the solutions!
