Thursday, April 19, 2007

Prisoner puzzle win win situation

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."

Now what you got to do is plan for them and find a win win situation

Click here for answer
Show/Hide

We may use 1 switch for a tag and the other just for changing state as it is given the prisoner have to change the state of 1 switch.

Chose a leader who will count (count what?? is explained below).
So lets say we chose switch A in the on conditions as a tag that a new prisoner has visited the room.
Only the leader can turn off the switch A and adds 1 to his count every time he turns it off. But he himslef doesnot turns it on (so as not to confuse himself with the count). If leader finds it in the off state(he visited consecutively) already he should change the state of switch B

Everytime a new prisoner comes if he finds the switch A in off condition(that means the count has been taken in account) he can switch it on. If he finds it in on condition or he had earlier changed the state of switch A to on then change the state of B.

This way the leader will count the number of on states of switch A and then change it to off state. Taking in account ,if the starting state of switch A is on. He may count it as a visited prisoner. So counting this case and 22 changed on states(he himself is the 23rd person) = 23 is the count which the leader got to reach to ensure that all of them has visited.
And then he can tell the warden that everyone has visited the room