An amusing puzzle
The following is taken from the puzzles column of the Fall, 2002 issue of the magazine Emissary.
A warden meets with 23 prisoners as they arrive. He explains the prison rules, and then allows them to meet with each other, talk, and have a strategy session. The prisoners are then taken to their solitary cells, and no further communication between the prisoners is possible.
In the prison there is a "switch room" containing two electrical switches (not connected to anything), each with two positions. From time to time the warden chooses a prisoner and takes him to the switch room; after observing the switches the prisoner is required to choose one switch and reverse its state. (The prisoners know nothing about the initial state of the switches.) The prisoner is then returned to solitary confinement. The only constraint on the warden's behavior is that each prisoner must be taken to the switch room infinitely often, i.e., any individual prisoner knows that he will sooner or later be taken to the switch room, and after that sooner or later be taken to the switch room again, etc.
At any time, a prisoner can announce to the warden that "By now, all of us have visited the switch room." If this is a true statement, the prisoners are all freed. If it is false, the prisoners are all executed. Clearly, no prisoner will make this statement unless they are absolutely sure that it is true.
Devise a strategy for the prisoners which will guarantee their release.
Source: This problem has apparently been circulating for a while, and appeared on IBM's puzzle web site "Ponder This" at www.research.com/ponder/. Each month, a puzzle is posted on that site, and a solution (together with a list of people who solved it) is posted at the end of the month. The prisoners problem was the July, 2002 challenge.