you are one of P recently arrested prisoners. The warden a deranged computer sci
ID: 3875846 • Letter: Y
Question
you are one of P recently arrested prisoners. The warden a deranged computer scientist, makes the following annoucncemnt
You may meet together today and plan a strategy, but after today you will be in isolated cells and have no communication with one another.
I have set up a “switch room” which contains a light switch, which is either on or off. The switch is not connected to anything.
Every now and then, I will select one prisoner at random to enter the “switch room.” The prisoner may throw the switch (from on to off, or vice versa), or may leave the switch unchanged. Nobody else will visit the room at that time. No one other than the selected prisoner will know that I took him to the switch room.
Each prisoner will visit the switch room arbitrarily often. More precisely, for any N, eventually, each of you will visit the switch room at least N times.
At any time, any of you may declare: “We have all visited the switch room at least once.” If the claim is correct, I will set you free. If the claim is incorrect, I will feed you to the crocodiles. Choose wisely!
None of the prisoners know the initial position of the switch. Write a correct winning algorithm, one that results in one of the prisoners declare “We have all visited the switch room at least once” correctly, without all of them being fed to the crocodiles. Explain clearly why your algorithm is correct.
Explanation / Answer
1. All the prisoners plan together and select one of them to declare that all the prisoners had visited the room.
2. Let us assume that the nominated prisoner maintains the count of all the prisoners that entered the room. Let the count be 1 initially.
case-1 : when the switch is initially off -
a. when the nominated prisoner enters the switch room:
1.If the switch is on, he turns it off and increases the count. If the count becomes P-1 then he declares that
every prisoner have visited the room.
2.If the switch is off, he does nothing.
b.If any other prisoner except the nominated prisoner enters the room,
1. If he sees that the first time switch is off, he will turn it on.
2.else he does nothing.
case-2:when we dont know whether the switch is on/off-
a.when the nominated prisoner enters the room:
1.If the switch is on, he turns it off and he increases the count. If the count becomes 2P-2 he will declare that all the prisoners have visited the switch room.
2.else he does nothing.
b.If any other prisoner except the nominated prisoner enters the room,
1. If he sees first two times that the switch is off, he will turn it on.
2.else he does nothing.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.