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?
Easy. One prisoner is designated as the "caller." He and only he will make the determination of when everyone's been in the room. Whenever he sees that the left-hand switch is "down," he will move it "up" and add 1 to his count; otherwise, he will flip the right-hand switch and not think anything of it. When the other prisoners enter the room, they have a different strategy. If the left-hand switch is "up," they will switch it "down," but they will only do this the first two times they encounter the left-hand switch "up." If they've moved the left switch twice already, or if the left-hand switch is "down," they will flip the right-hand switch.
When the caller's count is twice the number of prisoners plus one, each prisoner must have been in the room at least once, regardless of the initial configuration of the switches.
