Feb 08, 2020
RAY: I got this from my pal, Stan Zdonik, who teaches at Brown University. It was given to him by a colleague who failed to provide him with the answer -- maybe because he didn't know it?
Here it is.
This puzzle has been making the rounds of Hungarian mathematicians' parties.
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 A and B, each of which can be in either the on or the off 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.'
"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."
Here's the question:
What is the strategy the prisoners devise?
And here are the hints I'll give:
Hint number 1: A sixth grader could figure this puzzler out.
Hint B: Take a long-term perspective.
And Hint III: Solve the puzzler for three prisoners.
RAY: So, here's the answer.
The prisoners all meet, and the leader of the prisoners says, "Okay, guys, here's our strategy. First, there's only one guy who can count past two, so we're naming him 'The Counter.' He's going to be responsible for telling the warden we've all been in the switch room when the time comes."
He then proceeds to give instructions to the other inmates. He says, "We're going to designate Switch A -- the switch on the left - as the "real switch." That's the only switch that matters to The Counter. The other switch, Switch B, is a dummy. It won't tell us anything, and you just use it when you have to move a switch, but don't want to move Switch A. You got it? So Switch A is the meaningful switch and Switch B is a placeholder."
So, each of the 22 prisoners is told, "When you go into the switch room, we want you to move Switch A to the "On" position. If Switch A is already in the "On" position, then leave it there, flick switch B and walk out." All the prisoners nod.
"Now I want each of you to flick Switch A to the "On" position twice, and only twice. So if you go in there and Switch A is already on, that doesn't count. I want each of you to actually flick it "On" two times. You got that?"
All the prisoners nod. One of them raises his hand, tentatively.
"Yes, Berman?"
"Who's going to be flicking Switch A off," he asks.
"Good question," says the leader. "The Counter is the only one with the authority to turn off Switch A."
So, each time The Counter is taken into the switch room finds the switch in the "On" position, he knows that at least one prisoner has been in there.
It could be one prisoner who came in and turned it on, or it could be six prisoners -- the first one turning it on and the next five leaving it on. But when The Counter walks in and finds Switch A in the "On" position, he knows at least one prisoner has been in the room since the last time The Counter turned the switch off.
And when you work it all out, The Counter has to turn off Switch A 44 times in order to know that all 23 prisoners have been in the switch room. And the reason he has to count that high is that he doesn't know what the original position of the switch is, and therefore he has to wait for everyone to go in twice.
In other words, if the warden started with Switch A in the "On" position, and The Counter was brought in first, he could be fooled into thinking that another prisoner had been in there. And that's why it's 44 instead of 22.
If you have trouble understanding the strategy, try it for two prisoners. Let's say Prisoner 2 is The Counter. Prisoner 1 is brought in first. He sees Switch A is in the "Off" position, so he flicks it on. Let's say Prisoner 1 is brought in again. Remember -- the warden picks prisoners randomly. So Prisoner 1 leaves Switch A on and flicks Switch B, which doesn't matter. At some point, The Counter comes in, finds Switch A on and flips it off. That's once, he says. Eventually, Prisoner 1 is brought back in, and he turns Switch A on again. When Prisoner 2 comes back, he sees Switch A on, and now he knows that the other prisoner has been there. Last time he was there, he personally turned off Switch A, and now it's back on, so he knows the other prisoner did it, and he says, "Warden, our work here is done."
And interestingly, the number of times The Counter has to turn Switch A off is exactly twice the number of the other prisoners -- not counting him -- in the group. So, for two prisoners, it's two times. For 23 prisoners, it's 44 times.
Pretty cute, huh?
