The warden meets with 23 new prisoners when they arrive. He tells them, "You may meet today and plan a strategy. But after today, you will be in isolated cells and will have no communication with one another.
"In the prison is a switch room, which contains two light switches labeled 1 and 2, each of which can be in either up or the down position. I am not telling you their present positions. The switches are not connected to anything.
"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. This prisoner will select one of the two switches and reverse its position. He must move one, but only one of the switches. He can't move both but he can't move none either. Then he'll be led back to his cell.
"No one else will enter the switch room until I lead the next prisoner there, and he'll be instructed to do the same thing. I'm going to choose prisoners at random. I may choose the same guy three times in a row, or I may jump around and come back.
"But, given enough time, everyone will eventually visit the switch room as many times as everyone else. At any time anyone of you may declare to me, 'We have all visited the switch room.' and be 100% sure.
"If it is true, then you will all be set free. If it is false, and somebody has not yet visited the switch room, you will be fed to the alligators. You will be carefully monitored, and any attempt to break any of these rules will result in instant death to all of you"
What is the strategy they come up with so that they can be free?
Show Hint Show Solution
Hint: Take a long-term perspective. Solve the puzzler for three prisoners, then do it for 23 prisoners.
This was a long one....
ReplyDeleteThe team nominates a leader. The group agrees upon the following rules:
The leader is the only person who will announce that everyone has visited the switch room. All the prisoners except for the leader will flip the first switch up when possible, but only for their first two visits to the room. If the first switch is already up, or they have already flipped the first switch twice, they will then on flip the second switch. Only the leader may flip the first switch down, and if the first switch is already down, then the leader will flip the second switch. The leader remembers how many times he has flipped the first switch down. Once the leader has flipped the first switch down 44 times, he announces that all have visited the room. It does not matter how many times a prisoner has visited the room, in which order the prisoners were sent or even if the switch was flipped up by the warden. In the example of three prisoners, the leader must flip the first switch down four times to be sure all prisoners have visited the room.