Interesting Stuff

Also courtesy of Steamboat Steven. That guy has all kinds of neat puzzles!

There are n prisoners on a train being taken to a prison. Once they arrive there, they will each be put in separate sensory deprivation chambers. They will have no conception of how long they have been in there. However, sometimes a guard will take one of them into a room with two switches on the wall, make the prisoner flip one of the switches, and send him back to his sensory deprivation chamber. If you wait long enough, every prisoner will go to the switch room an arbitrarily large number of times (i.e., none of them will be “starved” of visits to the switch room). At any time, any prisoner may make the claim that all prisoners have been in the switch room at least once. If he is right when making this claim, they will all be set free. If he is wrong, they will all be killed.

The prisoners can discuss and agree on a strategy for the switches right now, but once they reach the prison they won’t see each other again. They don’t know the initial configuration of the switches. No prisoner will know how many other prisoners have visited the switch room before him; the person who goes to the switch room first won’t know he’s the first. They won’t know how often the guards take people to the switch room, and even if they did they wouldn’t know how much time has passed between their own visits.

How can they be guaranteed to eventually go free?