24 Mar 06
Originally posted by XanthosNZGot it. That aspect is correct then. The counter must be designated during the collaboration.
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.
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.
24 Mar 06
Originally posted by TheMaster37Exactly what I was thinking. This is the nub of the problem that was (and still is) stumping me.
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.
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?
24 Mar 06
1 edit
Originally posted by TheMaster37Such a situation is impossible under the correct strategy, which can be proven based on the process governing how prisoners are selected.
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.
24 Mar 06
1 edit
Originally posted by tojoSurely, if the prisoners are chosen at random, there is absolutely no way of 'ensuring' their freedom.
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?
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?
False.
24 Mar 06
Originally posted by leisurelyslothVery 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.
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).
24 Mar 06
Originally posted by leisurelyslothIt's going to busier if you have to fend off lots of doubters without a solid proof in hand.
busy work. 😞
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.
24 Mar 06
Originally posted by DoctorScribblesForgive me for keeping on this one point, but if...
[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]
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!
24 Mar 06
Originally posted by tojoI 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.
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]
- Joined
- 26 Apr 03
- Moves
- 26771
24 Mar 06
1 edit
Originally posted by tojoThe 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.
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]
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?
24 Mar 06
2 edits
Originally posted by tojoIgnoring 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.
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]
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.