Can u help prisoners to get free ?

[ujjagrawal]

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 1 and 2, each of which can be in either up or the down 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 flip one switch when he visits the switch room, and may only flip one of the switches. Then he'll be led back to his cell.

"No one else will be allowed to alter the switches until I lead the next prisoner into the switch room. 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. I will not touch the switches, if I wanted you dead you would already be dead.

"Given enough time, everyone will eventually visit the switch room the same number of times as everyone else. At any time, anyone 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 all die horribly. You will be carefully monitored, and any attempt to break any of these rules will result in instant death to all of you"

What is the strategy they come up with so that they can be free?

[bonanova]

Choose a Reporter. He will tell the warden when he is certain every prisoner has visited the room.

The others, let's call them the Counters, must signal to the Reporter that they have visited. They do this by flipping S1 to the UP position. The Reporter's job is to reset S1 to the DOWN position and keep track of how many times he has done so. When he resets S1 22 times he knows all the others have visited, and he reports this to the warden.

That's the basic idea, but it doesn't quite work.

If S1 is initially up, a Counter can't signal his visit, or the Reporter resets it, thinking a Counter has visited.

What does work is if the process is done twice. That is, the Counters flip S1 up [only] at their first TWO opportunities, and the Reporter resets S1 44 times.

[psykomakia]

Choose a Reporter. He will tell the warden when he is certain every prisoner has visited the room.

The others, let's call them the Counters, must signal to the Reporter that they have visited. They do this by flipping S1 to the UP position. The Reporter's job is to reset S1 to the DOWN position and keep track of how many times he has done so. When he resets S1 22 times he knows all the others have visited, and he reports this to the warden.

That's the basic idea, but it doesn't quite work.

If S1 is initially up, a Counter can't signal his visit, or the Reporter resets it, thinking a Counter has visited.

What does work is if the process is done twice. That is, the Counters flip S1 up [only] at their first TWO opportunities, and the Reporter resets S1 44 times.

Actually, I was thinking the same thing, but that doesn't work either. It just kicks the can down the road a bit. If the first guy has to flip S1 up so that the Reporter doesn't count him the first time, he'll only count to 43 and won't know that he doesn't need to count to 44.

[TripleOption]

Actually, I was thinking the same thing, but that doesn't work either. It just kicks the can down the road a bit. If the first guy has to flip S1 up so that the Reporter doesn't count him the first time, he'll only count to 43 and won't know that he doesn't need to count to 44.

if the count makes it to 43, then that means everyone has hit the switch at least once. just one guy only hit it once not twice. but everyone has been in the room

[psykomakia]

Yes of course. You're both right.

[phil1882]

a prisoner will put a switch into the up position if both switches aren't already up, and he hasn't flipped it before.

then a reporter will put both switches down, and count 2 (assuming both switches are up, which is likely).

let's label the two switches A and B.

each prisoner on thier first visit will toggle switch A, and on subsequent visits toggle switch B.

each prisoner will keep a count of the number of changed states he sees. when he reaches 23 they can stop.

there are four possible states: up, up; up, down; down, down; down, up each prisioner will go to the next state, and keep track of the distance between states. for example, if prisoner 1 enters in with up,up changes the state to up,down and upon entering the next time sees down, down, he can count 1. if he saw up,up he could count 3, the most count. this stategy gives the lowest chances of success, but the highest chances of finishing before the end of the year.

[psykomakia]

a prisoner will put a switch into the up position if both switches aren't already up, and he hasn't flipped it before.

then a reporter will put both switches down, and count 2 (assuming both switches are up, which is likely).

But he can't switch both switches at once.

let's label the two switches A and B.

each prisoner on thier first visit will toggle switch A, and on subsequent visits toggle switch B.

each prisoner will keep a count of the number of changed states he sees. when he reaches 23 they can stop.

But all 23 "changed states" could be due to the same single prisoner!

there are four possible states: up, up; up, down; down, down; down, up each prisioner will go to the next state, and keep track of the distance between states. for example, if prisoner 1 enters in with up,up changes the state to up,down and upon entering the next time sees down, down, he can count 1. if he saw up,up he could count 3, the most count. this stategy gives the lowest chances of success, but the highest chances of finishing before the end of the year.

But all of the "changed states" could be due to the same single prisoner!

[phil1882]

agreed on 2 and 3, its extreamely unlikely, but possible. i didnt realize that about my garenteed solution.

[psykomakia]

agreed on 2 and 3, its extreamely unlikely, but possible. i didnt realize that about my garenteed solution.

My point wasn't that the 23 state changes might possibly be the same single prisoner, but that it is LIKELY that some of the 23 state changes would be from the same prisoner, and so is not a viable solution.

[EventHorizon]

If the s1 lever is initially up:

1 + 21*2 + 1 resets are needed = 44, but once all 22 counters set the lever twice the reset count will be 45.

If the s1 lever is initially down:

0 + 21*2 + 1 resets are needed = 43, but once all 22 counters set the lever twice the reset count will be 44.

If you declare everyone has visited at 43 resets in the case that the s1 lever was initially up, it is possible one person hasn't visited. If you wait until 44, it's guaranteed everyone's been there regardless of the initial state of s1.

[ujjagrawal]

So the it is there... you all had got the answer... but below I will put my version of answer in bit detail

The team nominates a leader. The group agrees upon the following rules:

The leader is the only person who will announce that everyone has visited the switch room. All the prisoners (except for the leader) will flip the first switch up at their very first opportunity, and again on the second opportunity. If the first switch is already up, or they have already flipped the first switch up two times, they will then flip the second switch. Only the leader may flip the first switch down, if the first switch is already down, then the leader will flip the second switch. The leader remembers how many times he has flipped the first switch down. Once the leader has flipped the first switch down 44 times, he announces that all have visited the room.

It does not matter how many times a prisoner has visited the room, in which order the prisoners were sent or even if the first switch was initially up. Once the leader has flipped the switch down 44 times then the leader knows everyone has visited the room. If the switch was initially down, then all 22 prisoners will flip the switch up twice. If the switch was initially up, then there will be one prisoner who only flips the switch up once and the rest will flip it up twice.

The prisoners can not be certain that all have visited the room after the leader flips the switch down 23 times, as the first 12 prisoners plus the leader might be taken to the room 24 times before anyone else is allowed into the room. Because the initial state of the switch might be up, the prisoners must flip the first switch up twice. If they decide to flip it up only once, the leader will not know if he should count to 22 or 23.

In the example of three prisoners, the leader must flip the first switch down three times to be sure all prisoners have visited the room, twice for the two other prisoners and once more in case the switch was initially up.

[phil1882]

so i just wanted to make a note, i ran a simulation of my third method and found that 1558 out of 100,000 cases ended in failure.

that's a 98% chance of success. unless the warden is evil, which given the puzzle may very well be the case, assuming he honestly picked prisoners at random, if you want to get out in a reasonable amount of time, I'd use my third method.

[bonanova]

So the it is there... you all had got the answer... but below I will put my version of answer in bit detail

The team nominates a leader. The group agrees upon the following rules:

The leader is the only person who will announce that everyone has visited the switch room. All the prisoners (except for the leader) will flip the first switch up at their very first opportunity, and again on the second opportunity. If the first switch is already up, or they have already flipped the first switch up two times, they will then flip the second switch. Only the leader may flip the first switch down, if the first switch is already down, then the leader will flip the second switch. The leader remembers how many times he has flipped the first switch down. Once the leader has flipped the first switch down 44 times, he announces that all have visited the room.

It does not matter how many times a prisoner has visited the room, in which order the prisoners were sent or even if the first switch was initially up. Once the leader has flipped the switch down 44 times then the leader knows everyone has visited the room. If the switch was initially down, then all 22 prisoners will flip the switch up twice. If the switch was initially up, then there will be one prisoner who only flips the switch up once and the rest will flip it up twice.

The prisoners can not be certain that all have visited the room after the leader flips the switch down 23 times, as the first 12 prisoners plus the leader might be taken to the room 24 times before anyone else is allowed into the room. Because the initial state of the switch might be up, the prisoners must flip the first switch up twice. If they decide to flip it up only once, the leader will not know if he should count to 22 or 23.

In the example of three prisoners, the leader must flip the first switch down three times to be sure all prisoners have visited the room, twice for the two other prisoners and once more in case the switch was initially up.

Nice.

I missed the part about three prisoners. What was that?

[bonanova]

so i just wanted to make a note, i ran a simulation of my third method and found that 1558 out of 100,000 cases ended in failure.

that's a 98% chance of success. unless the warden is evil, which given the puzzle may very well be the case, assuming he honestly picked prisoners at random, if you want to get out in a reasonable amount of time, I'd use my third method.

Good point. In real life there would've 23 funerals before the guaranteed solution had run its course.

[phil1882]

it seems to me there should be a better way to gaurantee a solution.

let's label the prisoners 1-23.

prisoners 1 2 4 8 and 16 will act as leaders.

all non leaders will toggle switch B.

prisoner 1 will toggle switch A if the number of times he has seen switch B change is odd. else change switch B.

prisoner 2 will toggle switch A if for the past two times he has entered, the number of changes in switch B is odd. else change switch B.

prisoner 4 will toggle switch A if for the past four times he has entered, the number of changes in switch B is odd. else change switch B.

and so on.

prisoner 16 can declare victory when he toggles switch A 23 times.

i supose technically this is not gauranteed to work. but man if this doesn't get you free...

[bonanova]

it seems to me there should be a better way to gaurantee a solution.

let's label the prisoners 1-23.

prisoners 1 2 4 8 and 16 will act as leaders.

all non leaders will toggle switch B.

prisoner 1 will toggle switch A if the number of times he has seen switch B change is odd. else change switch B.

prisoner 2 will toggle switch A if for the past two times he has entered, the number of changes in switch B is odd. else change switch B.

prisoner 4 will toggle switch A if for the past four times he has entered, the number of changes in switch B is odd. else change switch B.

and so on.

prisoner 16 can declare victory when he toggles switch A 23 times.

i supose technically this is not gauranteed to work. but man if this doesn't get you free...

It would be an interesting scheme to simulate.