You may recall the prison experiment done along the following lines:
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 at random, and place him in a central interrogation room made of concrete walls 7ft on all sides and containing only a light bulb affixed to the ceiling with a toggle switch on one wall. The prisoner will be left alone for 1 minute in this room. 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.
The solution to this puzzle (I surprisingly cannot find it on PSE, is found here)
Since that experiment's success, a new, crueler warden has taken over. He does not want the prisoners to succeed in obtaining their freedom. He is bound by law to offer the prisoner's the same opportunity, but he is allowed to change the rules to make it harder for them. To that end, he comes up with a plan that he thinks makes it impossible to succeed.
He removed the lightswitch that controls the bulb from the room. In addition, after each prisoner's time in the central room, he will peer in the room himself and see if anything has been altered or left behind; if he sees any difference, all prisoners will be executed.
Under these new rules, what plan can the prisoners devise to guarantee their freedom?
CLARIFICATION: To help keep the possibilities from being too broad, I want to specify that the answer I have in mind does not involve anything besides the room itself (nothing like 'prisoners banging on their doors if they've visited the room', etc) and can yield a strategy that can guarantee with 100% certainty when all prisoners have visited the room (nothing like 'wait x years and they've probably all been').
Answer
Using the same logic in the original answer (of switching the light bulb on and off), you can still use that algorithm by
slightly loosening/tightening the bulb in it's socket. (about a quarter turn or so). The light bulb would still be lit/unlit, but the next prisoner can easily tell the "on/off" state from the "tightness" of the light bulb. And the warden sees no visible difference in the room.
Link to answer by Yisong Song https://www.math.washington.edu/~morrow/336_11/papers/yisong.pdf
No comments:
Post a Comment