The Prisoners and The Switch

Source

I got this problem from Rustan Leino, whom Tom Ball told (a close variation of) this problem.

The problem has been featured as a Car Talk Puzzler under the name "Prison Switcharoo". But, if you can find that page, beware: the Car Talk problem page also contains an answer.

I solved it and wrote up my solution.

Problem    

$N$ prisoners get together to decide on a strategy. Then, each prisoner is taken to his own isolated cell. A prison guard goes to a cell and takes its prisoner to a room where there's a switch. The switch can either be up or down. 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, each time choosing fairly among the prisoners. That is, the prison guard will choose each prisoner infinitely often.

At any time, any prisoner can exclaim "Now, every prisoner has been in the room with the switch." If, at that time, the statement is correct, all prisoners are set free; if the statement is not correct, all prisoners are immediately executed. What strategy should the prisoners use to ensure their eventual freedom?

Clarifications:

  • The initial state of the switch is unknown to the prisoners.
  • The state of the switch is changed only by the prisoners.
  • The prisoners' only means of communication with each other, once they've finished strategizing, is via the switch's position.
  • The switch cannot be in any state other than up or down.

Hints    
Solution     Reveal