Wednesday, November 18, 2009
For the next test, each of 20 prisoners will be placed in solitary confinement. Every once in a while, a prisoner's name will get drawn from a hat and he will get to visit the Rec Room. The Rec Room is no different from any of the barren concrete confinement cells except it has a light switch on the wall that isn't wired to anything. The prisoner is allowed to flip that switch to his heart's content for a minute, then has to go back to solitary. Then after another random length of time - maybe 5 minutes, maybe 5 days or more, another random prisoner will get selected to go to the Rec Room. Note that the same prisoner might be selected multiple times in a row. This will continue until a prisoner can tell a guard that everyone has been to the Rec Room at least once. At that point, all of the prisoners will be set free. If he's wrong, though, everyone will get executed.
So before the test happens, the 20 prisoners get to have one last party/meeting to coordinate how they are going to have someone know when everyone has been to the Rec Room. After this meeting, however, there will be no communication between them. What should they do?
Addendum: This riddle can be separated into two parts, with two similar solutions. First, come up with a strategy assuming that the switch starts in the 'off' position and that everyone knows it. Then for an additional challenge, assume that the initial position of the switch is unknown. (Thanks to Adam Sigelman for reminding me).
First we will assume 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 Rec 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 Rec 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 up once, the Counter will flip the switch down once for every prisoner in the prison. Once he has flipped the switch down 19 times (once for every prisoner other than himself), he can confidently say that everyone has been to the Rec Room at least once.
But what if the initial position of the light switch is unknown? Would this strategy still work? If the Counter happens to be the first one in the room and the switch was up, he will switch it down 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 up twice. The Counter will know everyone has been in the room once he flips the switch down 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 up twice and 1 prisoner flipped the switch up once. This process may take an awfully long time, but every prisoner is guaranteed to have been to the Rec Room at least once.
Posted by Charlie Guthrie at 2:34 PM