24 Mar 06
5 edits
N prisoners gather to decide on a cooperative strategy after hearing the rules to the following game:
Each prisoner is to be taken to his own isolated cell.
A prison guard goes to a random cell and takes its prisoner to a room where there is a switch.
The initial state of the switch can either be up or down, unknown to all prisoners.
The prisoner is allowed to inspect the state of the switch and then has the option of flicking the switch.
The prisoner is then taken back to his cell.
The prison guard repeats this process infinitely often until the game ends, each time choosing randomly among the prisoners. That is, the prison guard will choose each prisoner infinitely often, and none is ever more likely than another to be chosen. The state of the switch persists between visits
At any time, any prisoner can exclaim "Now, every prisoner has been in the room with the switch". This ends the game. If, at that time, the statement is correct, all prisoners are set free; if the statement is not correct, all prisoners are immediately executed.
Is there a strategy that the prisoners can agree on prior to their isolation to ensure their eventual freedom?
What strategy could they use if there were two labled switches rather than only one?
24 Mar 06
1 edit
Originally posted by DoctorScribblesWow, great problem. Yours? So they can beforehand say, nobody change the switch. Or conversely each one of you change the switch.
N prisoners gather to decide on a cooperative strategy after hearing the rules to the following game:
Each prisoner is to be taken to his own isolated cell.
A prison guard goes to a random cell and takes its prisoner to a room where there is a switch.
The initial state of the switch can either be up or down, unknown to all prisoners.
The pr eedom?
What strategy could they use if there were two labled switches rather than only one?
or every third one switches. They would of course know how many prisoners there were at the start. The one thing they don't know is how many other prisoners have seen the switch. Since they are drawn at random, the same guy could see the switch three times in a row, for instance. Moggles the bind.
24 Mar 06
2 edits
Originally posted by sonhouseI wish I did compose this problem, but I didn't. The two-switch formulation is the traditional one, and it is much easier. I have a reference to an analysis of the one-switch formulation, but I haven't examined it yet. I'm still trying to solve it.
Wow, great problem. Yours? So they can beforehand say, nobody change the switch. Or conversely each one of you change the switch.
or every third one switches. They would of course know how many prisoners there were at the start. The one thing they don't know is how many other prisoners have seen the switch. Since they are drawn at random, the same guy could see the switch three times in a row, for instance. Moggles the bind.
All of your other observations are correct.
24 Mar 06
2 edits
Originally posted by XanthosNZNo.
Do the prisoners know how many times the room has been viewed? For example does the second prisoner to be randomly chosen know exactly one prisoner has been there before him?
However, I don't think that assuming that they do affects the solution. I'd be interested to see if you can formulate a simpler strategy that relies on that assumption.
Dr. S
P.S. Actually, in some formulations of the problem, it is given that each day one prisoner is taken. So, in some formulations they do know, but this fact is definitely unnecessary for a solution, and I'm not sure that it's useful in constructing a simpler solution.
24 Mar 06
1 edit
Originally posted by DoctorScribblesHere's a simple extremely suboptimal solution.
No.
However, I don't think that assuming that they do affects the solution. I'd be interested to see if you can formulate a simpler strategy that relies on that assumption.
Dr. S
P.S. Actually, in some formulations of the problem, it is given that each day one prisoner is taken. So, in some formulations they do know, but this fact is defi ...[text shortened]... essary for a solution, and I'm not sure that it's useful in constructing a simpler solution.
Each prisoner except one (N-1) will flick the switch if the switch is down and they have not flicked the switch before. The final prisoner upon entering the room for the first time will flick the switch to down (if it needs it) and then start counting (with himself as 1). Every future time he enters the room if the switch is up he adds one to his count and sets it to down again. When his count reaches N he declares that every prisoner has been in the room.
This would take a horrifically long time (The counting prisoner has to enter the room at least N times).
This doesn't rely on knowing the number of visits. I'm sure an better solution exists that does rely on it though. The fact that the switch position is unknown to start with is frustrating my efforts though.
24 Mar 06
1 edit
Originally posted by XanthosNZYou have the essence of the solution. Once you solve how to deal with the unknown initial state, you can provide a proof of correctness.
Here's a simple extremely suboptimal solution.
Each prisoner except one (N-1) will flick the switch if the switch is down and they have not flicked the switch before. The final prisoner upon entering the room for the first time will flick the switch to down (if it needs it) and then start counting (with himself as 1). Every future time he enters the roo The fact that the switch position is unknown to start with is frustrating my efforts though.
I can't conceive of a more efficient solution. I suspect this is optimal.
24 Mar 06
2 edits
Originally posted by DoctorScribblesWell I don't know how I didn't see it at first but if the first prisoner picked is designated to put the switch into a known position (down say) then we have solved the unknown inital condition and can continue.
You have the essence of the solution. Once you solve how to deal with the unknown initial state, you can provide a proof of correctness.
I can't conceive of a more efficient solution. I suspect this is optimal.
So here's a more (but probably not 'the'😉 optimal solution.
It is decided that the first prisoner to visit the cell twice will be the counter. On his second visit he turns the switch to up and sets his count to the current visit number (as that number of distinct visitors must have come before him). For the first N-1 visits every other prisoner does nothing.
The (N+1)th randomly selected prisoner to be selected will do one of the two things; if the switch is down he will declare that everyone has visited the room; if the switch is up or he is the counter he will turn it down.
From the Nth visit on we proceed as before with our selected counter.
What we've done is reduced the amount of time it takes before the counter initialises his count. In the improved system it is:
The sum from 1 to N+1 of k * (N!*(k-1)!) / (N^k * (N-k+1)!
where k is the sum variable. For say 100 prisoners this is around 15 visits (I think).
EDIT: A more efficent solution would likely involve multiple counters and interaction between them. Personally I can't even concieve how it'd work but who knows.
24 Mar 06
4 edits
Originally posted by XanthosNZThis doesn't work, because we cannot assume that once a prisoner is picked, he knows whether or not he was the first. He has no mechanism of knowing if any have been picked before him. He can't know whether the group is in the initialization phase or the main phase of the algorithm, and he can't deduce it from the state of the switch.
Well I don't know how I didn't see it at first but if the first prisoner picked is designated to put the switch into a known position (down say) then we have solved the unknown inital condition and can continue.
I suppose this could work in the day-by-day formulation, provided all prisoners also know what day the visits begin. But for the more general formulation without this assumption, your solution does not work.
24 Mar 06
2 edits
Originally posted by DoctorScribblesYou said you would be interested to know if a simpler solution could be provided if number of visits was known. This is more complex than my earlier answer however it will mean less visits are required on average before the declaration can be made (by how much I'm not sure).
This doesn't work, because we cannot assume that once a prisoner is picked, he knows whether or not he was the first. He has no mechanism of knowing if any have been picked before him.
I suppose this could work in the day-by-day formulation, provided all prisoners also know what day the visits begin. But for the more general formulation without this assumption, your solution does not work.
As for knowing who is the first prisoner to visit twice it's simple. First note that there must be a duplicate visitor on or before the (N+1)th visit (pidgeon hold principle or just logic).
Say on the Ath (where A < N) visit a prisoner is selected for the second time. He enters the room and discovers the switch down. He then knows that no other prisoner has entered the room twice or else the switch would be up. As no one has visited the room twice prior to the Ath visit he can say that there have been A-1 distinct visitors (obvious).
He sets his count to this and turns the switch to up. Any second time visitor between the Ath and the (N+1)th visit will see the switch in the up position and know they are not the first repeat visitor.
Now the (N+1)th visitor will turn the switch down (thus entering the second phase) if it is up. This is needed so we can use the switch without messing up our earlier work.
From here on we work before except with one change (which I forgot to mention above).
If a prisoner enters the room and the switch is down they will switch it up if and only if both:
a) They have not switched the switch down before (excluding first overall visit and the (N+1)th visit)
b) They did not enter the room before the Ath visit (if they had they would have entered the room before the (N+1)th visit to see the switch down).
If the counter enters the room to see the switch up he adds one to his total and turns it to down.
When the counter reachs a total of N he declares.
24 Mar 06
6 edits
Originally posted by XanthosNZOh, OK. I thought you were still working on the general case.
You said you would be interested to know if a simpler solution could be provided if number of visits was known. This is more complex than my earlier answer however it will mean less visits are required on average before the declaration can be made (by how much I'm not sure).
You still haven't solved the general formulation. You have not specified how the unknown initial state of the switch is to be handled when the number of visits is not known. Or if you intended your original answer to account for that, then your original answer is incorrect.
Further, in your original answer, no prisoner can know whether he is the final one to visit the room for the first time, so it is incorrect in that aspect as well.
You have the heart of the algorithm, but the devil is in the details.
24 Mar 06
Originally posted by DoctorScribblesBad wording, in the original answer where I referred to the 'final prisoner' I meant the prisoner predetermined to be the counter. He is the final prisoner in that I mentioned the other N-1 prisoners before him.
Oh, OK. I thought you were still working on the general case.
You still haven't solved the general formulation. You have not specified how the unknown initial state of the switch is to be handled when the number of visits is not known. Or if you intended your original answer to account for that, then your original answer is incorrect.
Furthe ...[text shortened]... n that aspect as well.
You have the heart of the algorithm, but the devil is in the details.
As for finding a way around the inital state I'm stuck. Someone else take over.