| Issue 4: | 1.8 Exercise 4. | |
| 1 person starred this issue and may be notified of changes. | Back to list |
|
Exercise 4. You are one of P recently arrested prisoners. The warden, a deranged computer scientist, makes the following announcement: -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.” This prisoner may throw the switch (from on to off, or vice-versa), or may leave the switch unchanged. Nobody else will ever enter this 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 all of you to the crocodiles. Choose wisely! Devise a winning strategy when you know that the initial state of the switch is off. Devise a winning strategy when you do not know whether the initial state of the switch is on or off. Hint: not all prisoners need to do the same thing.
Aug 26, 2014
Solution of task (know that the initial state/do not know whether the initial state) in attach 1.4.docx
Sep 4, 2014
I have not fond solution for the case with unknown initial state. please describe.
Sep 4, 2014
cell(1,1) has changing state "Off to On / On to On (1)", for Off state prisoner turn on it, for On state prisoner does nothing
Sep 16, 2014
(No comment was entered for this change.)
Status:
Done
|
||||||||||
16.7 KB Download