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?
|
SelectClick for Answer |
If the prisoners knew that both switches were off at the start, then the solution would be fairly straightforward. One switch (say, the left one) will be used for counting, and the other is a meaningless dummy. One prisoner is chosen as the Counter. Each other prisoner is instructed to flip the left switch from off to on one time, at the first opportunity, but otherwise to flip the dummy switch on each visit. When the Counter enters the room and finds the left switch on, he turns it off; otherwise he too flips the dummy switch. When the Counter has found the left switch turned on 22 times, he knows that all prisoners have visited the room and can safely tell the warden so.
Because the prisoners don’t know the initial states of the switches, this plan must be enhanced (otherwise, if the left switch starts in the on position, then the Counter will make his announcement prematurely). The solution is to ask each prisoner to flip the left switch from off to on twice in total, rather than once. The Counter will wait until he’s seen the left switch turned on 44 times altogether, and then tell the warden that all prisoners have visited the room.
(At first I wondered why they couldn’t just stick with the first scenario but add 1 to the expected count to allow for the possibility that the left switch had started in the on position. But this won’t work: If the Counter is waiting until he’s found the left switch turned on 23 times, and if it started in the off position, then he’ll wait forever, because each of the 22 other prisoners will turn it on only once.)
|
