Problem of the Week 975

A New Prisoners' Dilemma

Three prisoners are in separate cells. Every once in a while the warden takes one of the prisoners into a special "switch room", which contains a single switch (connected to nothing) with two settings, UP and DOWN. The prisoner can reverse the state of the switch or leave it alone. The warden is committed to taking the prisoners to the room infinitely often: in other words, whenever they leave the room, they know they will eventually be taken back.

At any time, a prisoner can announce "all three of us have visited the switch room", in which case they will all be released if the statement is true, or executed if the statement is false.

The prisoners may consult with each other before the room visits begin in order to formulate a strategy, but after that they will never see each other in the prison. And the warden can put the switch in any position he or she likes at the start (though after that the warden may not touch the switch).

Formulate a strategy that will guarantee that the prisoners will eventually be released.

Note: No probability is involved...the warden can arrange the visits any way he or she wants, subject to his or her commitments.

Source: A puzzle from ibm.com (reprinted in latest MSRI newsletter "Emissary").