The 23 prisoners problem
Adam next posed this problem:
The warden meets with the 23 prisoners when they arrive. He tells them:
You may meet together today and plan a strategy, but after today you will be in isolated cells and have no communication with one another.
There is in this prison a "switch room" which contains two light switches, labelled "A" and "B", each of which can be in the "on" or "off" position. I am not telling you their present positions. The switches are not connected to any appliance. After today, from time to time, whenever I feel so inclined, I will select one prisoner at random and escort him to the "switch room", and this prisoner will select one of the two switches and reverse its position (e.g. if it was "on", he will turn it "off"); the prisoner will then be led back to his cell. Nobody else will ever enter the "switch room".
Each prisoner will visit the switch room arbitrarily often. That is, for any N it is true that eventually each of you will visit the switch room at least N times.
At any time, any of you may declare to me: "We have all visited the switch room." If it is true (each of the 23 prisoners has visited the switch room at least once), then you will all be set free. If it is false (someone has not yet visited the switch room), you will all be executed.
Devise for the prisoners a strategy which will guarantee their release.
(My solution follows.)
"Doing nothing" is defined as follows: if you intend to toggle switch A, do so. Otherwise, since you're forced to toggle something, toggle switch B. Nobody pays attention to the state of switch B.
In conference, the prisoners appoint a manager. The manager tells the remaining 22 prisoners that they are all currently in "unknown" mode.
Unknown mode: a prisoner in this mode wants to progress to "ready" mode. He does so once he has visited at least twice and seen switch A in different positions.
Ready mode: a prisoner in this mode wants to progress to "idle" mode. He may do so once he has visited and finds switch A in the off position. If he switches A on, which he should do at this point, he has progressed to idle mode.
Idle mode: the prisoner does nothing but wait.
The manager's job is to count how many times prisoners switch from ready to idle, knowing a prisoner will do so only once. He must reset switch A to off each time he increments the count. He must also provide signals to allow prisoners to switch from unknown to ready. He begins in "sync" mode:
Sync mode: If A is on, switch it off and enter count mode. If A is off, switch it on and remain in sync mode.
Count mode: increment prisoner count each time you visit and find switch A on. Always leave the room with switch A off. If the count indicates all prisoners have visited the room, yell for the warden.
There is a case where a prisoner remains in unknown mode, either by bad luck (he always enters the room when switch A happens to be in the same state), or through the warden's evil (he leaves one prisoner out for the first N iterations). Eventually the manager will count 22 prisoners (including himself) and notice that nobody else switches anymore. He can solve this by periodically dropping back into a modified form of sync mode, where he increases the prisoner count if switch A is on, and moves to count mode if switch A is off. In either case he toggles switch A. Eventually the straggler will note the state change andswitch into ready mode.
