6. The Warden
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 flip one switch when he visits the switch room, and may only flip one of the switches. Then he'll be led back to his cell.
"No one else will be allowed to alter the switches until I lead the next prisoner into the switch room. 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. I will not touch the switches, if I wanted you dead you would already be dead.
"Given enough time, everyone will eventually visit the switch room the same number of times as everyone else. At any time, anyone may declare to me, 'We have all visited the switch room.'
"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 all die horribly. 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?
Added 1 January 2007
Hint: Take a long-term perspective. Solve the puzzler for three prisoners.
Solution:
The 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 at their very first opportunity, and again on the second opportunity. If the first switch is already up, or they have already flipped the first switch up two times, they will then flip the second switch. Only the leader may flip the first switch down, 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 first switch was initially up. Once the leader has flipped the switch down 44 times then the leader knows everyone has visited the room. If the switch was initially down, then all 22 prisoners will flip the switch up twice. If the switch was initially up, then there will be one prisoner who only flips the switch up once and the rest will flip it up twice.
The prisoners can not be certain that all have visited the room after the leader flips the switch down 23 times, as the first 12 prisoners plus the leader might be taken to the room 24 times before anyone else is allowed into the room. Because the initial state of the switch might be up, the prisoners must flip the first switch up twice. If they decide to flip it up only once, the leader will not know if he should count to 22 or 23.
In the example of three prisoners, the leader must flip the first switch down three times to be sure all prisoners have visited the room, twice for the two other prisoners and once more in case the switch was initially up.
Comments (34)
What is the answer to the Warden question? I'm going mad to find out!
This puzzle has been making the rounds recently.
The question of the 23 prisoners has interested me quite a bit. You have one of the better explanations of the solution that I've seen, but the solution to the test case of 3 prisoners is wrong and misleading.
I would like to propose adding a sentence to the Warden puzzle stating: 'I intend to keep this game going, till infinity,' as it is unclear whether the warden intends to stop or not.
In the Warden puzzle, with 3 prisoners, the leader would need to count 4 switches to ensure that both other prisoners have visited the room.
I believe (in #6, the warden) that the leader does not have to wait for everyone to flip #1 twice. if they just tell everyone to only flip #1 up on their first visit and the leader only counts to 22, they will be fine. there is no need to have them flip switch #1 up more than once each. when the leader enacts his 22nd #1 down, that proves that all the other inmates have been in the room. since the leader will be in the room to realize this, that makes 23/23 and he is safe to call the warden. as far as the initial switch position, whoever goes first just makes sure #1 is up when they leave. that will start the leaders counting (if its the leader he can make sure #1 is down, and then count to 23) But I may be missing something. please let me know if you have time.
The leader does not have to wait for everyone to flip switch #1 twice; they can just tell everyone to flip switch #1 up on their first visit and count to 22.
I believe in 'The Warden' puzzle that the leader does not have to wait for everyone to flip switch #1 twice. They can just tell everyone to flip it up on their first visit, and the leader counts to 22. This way, they will be fine.
Can you provide the solution for 'The Warden' puzzle?
I have a small quibble with the Warden question. The solution assumes that no prisoner will ever have had more than one visit more than any other prisoner.
In The Warden, the answer regarding the number of flips needed is incorrect. The leader would need to flip the switch 4 times, not 3, due to the potential states of the switches.
What happens if the leader is chosen 30 times in a row? Then the solution doesn't hold true.
The explanation regarding the Warden and prisoners seems to overlook the fact that the counter can only count the switches that are pulled down, which complicates the counting process.
I'm thoroughly stuck on the Warden puzzle. Could you provide any other hints? Does it have anything to do with 23 being a prime?
I'm thoroughly stuck on the Warden puzzle. I can solve for 3 easily, but not more than that. Does it have anything to do with 23 being a prime? Is there a set number of times each prisoner will go to the switch room? Is the fact that they will all eventually have been to the switch room the same amount of times a key piece in the puzzle?
The last sentence in the solution is incorrect: it should be 4, not 3. If the switch was up, and then the leader and one prisoner alternated visits, he would declare they had all visited before the second prisoner had ever visited.
Are the prisoners called in a cycle? Will a prisoner be called more than once before completing a cycle?
The order of prisoners being called in a cycle raises a question. Can a prisoner be called more than once before completing a full cycle? For example, with 6 prisoners, is the sequence 'aaa b cc b cc b cc d ee aa fff' possible?
Why would you want the leader to have to flip the counting switch 44 times? The solution's ending is much better than that, though it wrongly states it won't work.
Wouldn't it be faster to assign a leader and only one person to flip the switch up twice? That way, the leader only has to flip the switch down 24 times to be sure everyone has been in the room.
If everyone is being monitored at all times, wouldn't everyone have to physically visit the room to flip a switch?
In the case of three prisoners, the leader needs to flip the switch down four times to ensure all have visited the room.
In 'The Warden', the leader needs to flip the switch down four times to ensure all prisoners have visited the room, not three times.
I had a rough time with the Warden Puzzle because I misunderstood the puzzle.
I misunderstood the Warden Puzzle. The declaration should be made when everyone has visited the room at least once, not when they have visited the same number of times.
The condition for the prisoners is that they must all visit the switch room the same number of times. If one prisoner visits more times than the others, the condition is not met, and they cannot declare they have all visited.
I spent three days trying to create a system under which prisoners will be 100% sure. I failed to do so and was very excited to read the solution.
The condition clearly states he can jump around, which creates a possibility that one of them will never be called up.
Shouldn't the leader be required to flip down the first lever four times in the example of the three prisoners?
The phrasing for The Warden led me to a frustrating dead end. The sentence makes it sound like there are a finite number of visits to the switch room.
I want to share with you an alternate solution for The Warden.
The leader must see the switch up four times, not three. The non-leaders will still be required to flip the switch up twice to handle the 'it started up' case.
If the switch has been flicked up 43 times then the leader can announce it then; so he does not need to flip the switch down the 44th time.
In the Warden puzzle, with 3 prisoners, the leader would need to flip the switch 4 times, not 3, to account for the possibility that a prisoner could have flipped the switch up multiple times.
Add a Comment or Suggest an Answer