The governor of a prison is bored. He decides to amuse himself by playing
a game with the prisoners. He sets up a room with two switches in it. Each
switch has 2 positions (on and off ). He tells the prisoners that he is going to
send them to the room one at a time and that they have to move exactly one
of the switches each time they visit. He is free to send them in whatever order
he likes and can send them as often as he likes (perhaps sending one prisoner
100 times before sending some other prisoner, then sending the first one again...
anything!). The only promise that he makes is that if any prisoner picks a
number n and waits long enough, they can be sure to visit the room n times.
The prisoners are kept in solitary and are unable to communicate once the
game has started. They will never know how many other prisoners have visited
the room since they were last there. They are also not told what the initial
position of the switches was.
The governor tells them that if at any stage a prisoner comes to him and
states correctly that all prisoners have now visited the room at least once, all of
the prisoners will be freed. But if a false claim is made, they will all be shot.
The night before the game begins the prisoners meet in a large room to
discuss their tactics. Do they have a strategy that ensures they will win their
freedom?
