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, ON and OFF. The switch starts in the OFF position. 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. The warden may not touch the switch.
Question 1: Formulate a strategy that will guarantee that the prisoners will eventually be released.
Question 2: Formulate a strategy that will work for 10 prisoners.
Question 3: Formulate a strategy that will work if the prisoners do not know the initial start position of the switch. i.e. the warden can decide to initially have the switch ON or OFF, without the prisoners knowing the start position.
Click here to reveal answer
Question 1: First we know the light switch starts in the OFF position and everyone knows it. The prisoners will select one among them to be the designated Counter. When a prisoner enters the Room, he will check to see if the light switch is in the ‘OFF’ position. If he has never flipped the switch before, he will turn the switch ON. He will only do this once. If he has flipped the switch before, he won’t do anything. The only person that will not flip the switch up to ‘ON’ is the Counter. When he comes to the Room, if he sees that the switch is ON, he will turn it OFF and add one to his mental prisoner count. As long as each prisoner only flips the switch ON once, the Counter will flip the switch OFF once for every prisoner in the prison. Once he has flipped the switch OFF 2 times (once for every prisoner other than himself), he can confidently say that everyone has been to the Room at least once.
Question 2: Follow the same strategy for question one, but instead of counting to 2, the Counter counts to 19.
Question 3: Let’s assume 20 prisoners. What if the initial position of the light switch is unknown? Think about it – If the Counter happens to be the first one in the room and the switch was ON, he will switch it OFF and think that someone has been in the room before him. He might then end his count of 19 before the last prisoner has been to the room. What will have to happen then, is that every prisoner (except the Counter) will have to flip the switch ON twice. The Counter will know everyone has been in the room once he flips the switch OFF 38 times. This way, even if the Counter was the first in the room and counted a prisoner when there was none, this will mean that 18 prisoners flipped the switch ON twice and 1 prisoner flipped the switch ON once. This process may take an awfully long time, but every prisoner is guaranteed to have been to the Room at least once.