100 Prisoners And a Light Bulb


100prisoners_bulb“One hundred prisoners have been newly ushered into prison. The warden tells them that starting tomorrow, each of them will be placed in an isolated cell, unable to communicate amongst each other. Each day, the warden will choose one of the prisoners uniformly at random with replacement, and place him in a central interrogation room containing only a light bulb with a toggle switch. The prisoner will be able to observe the current state of the light bulb. If he wishes, he can toggle the light bulb. He also has the option of announcing that he believes all prisoners have visited the interrogation room at some point in time. If this announcement is true, then all prisoners are set free, but if it is false, all prisoners are executed. The warden leaves, and the prisoners huddle together to discuss their fate. Can they agree on a protocol that will guarantee their freedom?”

Working with the combined efforts of many members of [wu:forums] since 2002, we have embarked on a never-ending journey to find new more efficient algorithms and protocols for solving the 100 prisoners and a light bulb riddle, most of which are not well-known. In an investigation with collaborators Hans van Ditmarsch and Jan van Eijck, we show how the riddle can be studied using dynamic epistemic logic.

  • van Ditmarsch, Hans; van Eijck, Jan; Wu, William100 Prisoners and a Light Bulb: Logic and Computation. KR 2010 (Principles of Knowledge, Representation, and Reasoning). For a preprint that has more details (but does not fit the page limits of KR), check this out.
  • Wu, William100 Prisoners and a Light Bulb. Online document uploaded in 2002; since then, it has been referenced in several places. A never-ending work in progress with no submission plans, but if you have suggestions, feel free.
    • Programmed simulation of 100 Prisoners: click here