A prison warden greets 23 new prisoners with this challenge. They can meet now to plan a strategy, but then they’ll be placed in separate cells, with no means of communicating. Then the warden will take the prisoners one at a time to a room that contains two switches. Each switch has two positions, on and off, but they’re not connected to anything. The prisoners don’t know the initial positions of the switches. When a prisoner is led into the room, he must reverse the position of exactly one switch. Then he will be led back to his cell, and the switches will remain undisturbed until the warden brings the next prisoner. The warden chooses prisoners at his whim, and he may even choose one prisoner several times in a row, but at any time, each prisoner is guaranteed another visit to the switch room.
The warden continues doing this until a prisoner tells him, “We have all visited the switch room.” If this prisoner is right, then all the prisoner will be set free. But if he’s wrong then they’ll all remain prisoners for life.
What strategy can the prisoners use to ensure their freedom?