[Tom Ball told me (a close variation of) this problem. The problem has been featured as a Car Talk Puzzler under the name Prison Switcharoo.]

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 is 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?

(Just in case there’s any confusion: The initial state of the switch is unknown to the prisoners. The state of the switch is changed only by the prisoners.)

As a warm-up, you may consider the same problem but with a known initial state of the switch.