24 Mar '06 01:14>5 edits
N prisoners gather to decide on a cooperative strategy after hearing the rules to the following game:
Each prisoner is to be taken to his own isolated cell.
A prison guard goes to a random cell and takes its prisoner to a room where there is a switch.
The initial state of the switch can either be up or down, unknown to all prisoners.
The prisoner is allowed to inspect the state of the switch and then has the option of flicking the switch.
The prisoner is then taken back to his cell.
The prison guard repeats this process infinitely often until the game ends, each time choosing randomly among the prisoners. That is, the prison guard will choose each prisoner infinitely often, and none is ever more likely than another to be chosen. The state of the switch persists between visits
At any time, any prisoner can exclaim "Now, every prisoner has been in the room with the switch". This ends the game. If, at that time, the statement is correct, all prisoners are set free; if the statement is not correct, all prisoners are immediately executed.
Is there a strategy that the prisoners can agree on prior to their isolation to ensure their eventual freedom?
What strategy could they use if there were two labled switches rather than only one?
Each prisoner is to be taken to his own isolated cell.
A prison guard goes to a random cell and takes its prisoner to a room where there is a switch.
The initial state of the switch can either be up or down, unknown to all prisoners.
The prisoner is allowed to inspect the state of the switch and then has the option of flicking the switch.
The prisoner is then taken back to his cell.
The prison guard repeats this process infinitely often until the game ends, each time choosing randomly among the prisoners. That is, the prison guard will choose each prisoner infinitely often, and none is ever more likely than another to be chosen. The state of the switch persists between visits
At any time, any prisoner can exclaim "Now, every prisoner has been in the room with the switch". This ends the game. If, at that time, the statement is correct, all prisoners are set free; if the statement is not correct, all prisoners are immediately executed.
Is there a strategy that the prisoners can agree on prior to their isolation to ensure their eventual freedom?
What strategy could they use if there were two labled switches rather than only one?