Puzzle: How do you get out of the prison (Part II)
The previous puzzle was solved correctly in the comments. So I thought to present with another prison-style puzzle:
A 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."
Comments
- Anonymous
June 25, 2005
The comment has been removed - Anonymous
June 25, 2005
The comment has been removed - Anonymous
June 25, 2005
The comment has been removed - Anonymous
June 25, 2005
The comment has been removed - Anonymous
June 25, 2005
Sorry for the repeat post. - Anonymous
June 25, 2005
Entropy questions are fun! OK, the prisoners agree to organize into 22 signalers and one captain. When a signaler goes to the room, the first two times that he finds the left switch off, he turns it on, thereby signalling; otherwise, he flips the right switch. Each time the captain goes to the room, if he observes the left switch on, he adds one to his tally and turns it off, accepting the signal; otherwise, he flips the right switch. Once the captain has collected 44 signals, he knows that everyone else has signaled exactly twice, with the possible exception of one who has only signaled once if the left switch was initially on, therefore everyone has been to the room, so he calls the warden and everyone goes free. - Anonymous
June 25, 2005
Yes, I forgot that the initial state isn't known <blush>.
Also, where I said 'haven't been to the room before' I (obviously?) meant 'haven't flipped switch A before'...