Originally posted by XanthosNZ Bad 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.
Got it. That aspect is correct then. The counter must be designated during the collaboration.
Assume the switch is known to start in the down state. If you can construct a rigorous proof that your strategy is correct under that assumption, it may lead to an idea of how to generalize the strategy for an unknown initial state.
Originally posted by TheMaster37 What about the situation that one of the prisoners never gets chosen?
I know it's unlikely, but that would blow a huge hole in any strategy.
Exactly what I was thinking. This is the nub of the problem that was (and still is) stumping me.
Surely, if the prisoners are chosen at random, there is absolutely no way of 'ensuring' their freedom. No matter how long the experiment goes on for, there will always be a probability (however small), that at least one prisoner has not been chosen.
The best the prisoners could hope for was a solution where the probability that they have not all been in to the room with the switch is so small that it could be effectively discounted, surely?
Surely, if the prisoners are chosen at random, there is absolutely no way of 'ensuring' their freedom. No matter how long the experiment goes on for, there will always be a probability (however small), that at least one prisoner has not been chosen.
The best the prisoners could hope for was a solution where the probability that they have not all b ...[text shortened]... en in to the room with the switch is so small that it could be effectively discounted, surely?
Surely, if the prisoners are chosen at random, there is absolutely no way of 'ensuring' their freedom.
False.
No matter how long the experiment goes on for, there will always be a probability (however small), that at least one prisoner has not been chosen.
True.
The best the prisoners could hope for was a solution where the probability that they have not all been in to the room with the switch is so small that it could be effectively discounted, surely?
I think I've got it. Each prisoner flips the switch up twice. If there are X "non-counting" prisoners, then the "counter" must count to 2X. At this point it won't matter if his first count was bogus (due to the switch being up to start with).
Originally posted by leisurelysloth I think I've got it. Each prisoner flips the switch up twice. If there are X "non-counting" prisoners, then the "counter" must count to 2X. At this point it won't matter if his first count was bogus (due to the switch being up to start with).
Very good. What remains is to combine your idea with Xanthos's in order to fully specify the complete strategy, and then to provide a proof that it is correct.
Originally posted by DoctorScribbles Very good. What remains is to combine your idea with Xanthos's in order to fully specify the complete strategy, and then to provide a proof that it is correct.
Originally posted by leisurelysloth busy work. 😞
It's going to busier if you have to fend off lots of doubters without a solid proof in hand.
For example, what about those who said that all prisoners may never get picked? And now you're saying the correct strategy requires them to get picked twice! If I were you, I'd prepare a proof.
Originally posted by DoctorScribbles [b]Surely, if the prisoners are chosen at random, there is absolutely no way of 'ensuring' their freedom.
False.
No matter how long the experiment goes on for, there will always be a probability (however small), that at least one prisoner has not been chosen.
True.
The best the prisoners could hope for was a solution wh ...[text shortened]... oom with the switch is so small that it could be effectively discounted, surely?
False.[/b]
Forgive me for keeping on this one point, but if...
No matter how long the experiment goes on for, there will always be a probability (however small), that at least one prisoner has not been chosen.
is True, as you state above, then they cannot 'ensure' their freedom, because there is always a possibility that they have not all been picked?
If been over and over this for days now, and cannot get around this, no matter how I look at it. Help!
Originally posted by tojo Forgive me for keeping on this one point, but if...
[b]No matter how long the experiment goes on for, there will always be a probability (however small), that at least one prisoner has not been chosen.
is True, as you state above, then they cannot 'ensure' their freedom, because there is always a possibility that they have not all been picked?
...[text shortened]... d over this for days now, and cannot get around this, no matter how I look at it. Help![/b]
I think the idea is that they agree on a strategy that will prevent them from triggering their own executions by incorrectly stating that all prisoners have been chosen. However, you are correct in stating that they cannot 'ensure' their freedom, since their strategy could end up taking longer than their lifetimes.
Originally posted by tojo Forgive me for keeping on this one point, but if...
[b]No matter how long the experiment goes on for, there will always be a probability (however small), that at least one prisoner has not been chosen.
is True, as you state above, then they cannot 'ensure' their freedom, because there is always a possibility that they have not all been picked?
...[text shortened]... d over this for days now, and cannot get around this, no matter how I look at it. Help![/b]
The solution merely needs to have the property that it will not halt until all prisoners have been chosen, this means it will wait as long as necessary. If it takes a long time for one guy to be picked it will take a very long time, but our solution will not mind waiting for a very very long time.
Put it this way:
You have a fair coin, if you toss it one hundred times are you guaranteed to get a head? one thousand times? one million? How about if you toss it "until you get a head", are you guaranteed to get a head now?
Originally posted by tojo Forgive me for keeping on this one point, but if...
[b]No matter how long the experiment goes on for, there will always be a probability (however small), that at least one prisoner has not been chosen.
is True, as you state above, then they cannot 'ensure' their freedom, because there is always a possibility that they have not all been picked?
...[text shortened]... d over this for days now, and cannot get around this, no matter how I look at it. Help![/b]
Ignoring the case that one of them dies while in prison, the process the guard uses guarantees that each will be picked. Under that process, it is impossible for any prisoner to never be picked.
This is not contrary to saying that at any given time, there is a non-zero probability that at least one prisoner will not have been picked.
Both claims are true. Iamatiger's example is a fine illustration of this.
A new prisoner problem
24 Mar '06 05:33
Back to Top