3 ms·

>The "easiest" solution would simply be to wait a few billion years Actually that is incorrect as there is no guarantee that every prisoner has been in the roo

>The "easiest" solution would simply be to wait a few billion years Actually that is incorrect as there is no guarantee that every prisoner has been in the room at least once over any amount of time. Of course the probability will get higher and higher that everyone was in the room once if it was completely random but that probability will never be 100%. I know of two legitimate answers to this problem, it took me awhile when I first heard it.

SilasX 10y ago
>Actually that is incorrect as there is no guarantee that every prisoner has been in the room at least once over any amount of time. IIRC, in the original statement of the problem, there's also a stipulation that, for all prisoners, the king/chooser/whatever will visit them an infinite number of times (so at any time it must be true that each prisoner will be visited [again or for the first time] if the game doesn't terminate).
- thaumasiotes 10y ago
  So? It doesn't have to be true that each prisoner will be visited within any particular time frame.
  - SilasX 10y ago
    The solution only requires that they will eventually be visited; you can keep deferring until they are. There's no specific time frame in which you have to make a guess.
    - thaumasiotes 10y ago
      > There's no specific time frame in which you have to make a guess This is correct. > The solution only requires that they will eventually be visited; you can keep deferring until they are. This is false; you can't "keep deferring until everyone is visited" because you have no way of assessing whether that's happened. As a strategy, it is impossible to implement.
      - SilasX 10y ago
        Yes, you can: the designated prisoner waits until the signal has been fipped n+k times where n is the number of prisoners and k is the number of times the guard can intervene. All other prisoners flip it to that state if it isn't already. See the other replies.
        thaumasiotes 10y ago
        That is a completely different strategy than "if we wait long enough, it's bound to work". Waiting is worthless, no matter how long you wait.
        SilasX 10y ago
        But under the corrected assumption about the problem, you can reliably know when it is safe to say that all prisoners have been in the room and when you should keep deferring. In the other version of the problem, I agree there's no such guarantee; hence why I bought up the difference.
- 5tk18 10y ago
  I think dsugarman meant "at least once over any FINITE amount of time", in which case each prisoner might visit again an infinite number of times, but it can be arbitrarily many turns in the future. So, if you wait a finite amount of time (in this case a "few" billion years") it's possible that the visiting condition might not yet be satisfied.
iliis 10y ago
True. I alluded to that further down, as even with the perfect strategy this means that "it is theoretically possible that the goal state never happens", i.e. the probability that the algorithm will terminate will never be 100% (but it terminates with probability 1).

SilasX 10y ago

>Actually that is incorrect as there is no guarantee that every prisoner has been in the room at least once over any amount of time. IIRC, in the original statement of the problem, there's also a stipulation that, for all prisoners, the king/chooser/whatever will visit them an infinite number of times (so at any time it must be true that each prisoner will be visited [again or for the first time] if the game doesn't terminate).

thaumasiotes 10y ago
So? It doesn't have to be true that each prisoner will be visited within any particular time frame.
- SilasX 10y ago
  The solution only requires that they will eventually be visited; you can keep deferring until they are. There's no specific time frame in which you have to make a guess.
  - thaumasiotes 10y ago
    > There's no specific time frame in which you have to make a guess This is correct. > The solution only requires that they will eventually be visited; you can keep deferring until they are. This is false; you can't "keep deferring until everyone is visited" because you have no way of assessing whether that's happened. As a strategy, it is impossible to implement.
    - SilasX 10y ago
      Yes, you can: the designated prisoner waits until the signal has been fipped n+k times where n is the number of prisoners and k is the number of times the guard can intervene. All other prisoners flip it to that state if it isn't already. See the other replies.
      - thaumasiotes 10y ago
        That is a completely different strategy than "if we wait long enough, it's bound to work". Waiting is worthless, no matter how long you wait.
        SilasX 10y ago
        But under the corrected assumption about the problem, you can reliably know when it is safe to say that all prisoners have been in the room and when you should keep deferring. In the other version of the problem, I agree there's no such guarantee; hence why I bought up the difference.
5tk18 10y ago
I think dsugarman meant "at least once over any FINITE amount of time", in which case each prisoner might visit again an infinite number of times, but it can be arbitrarily many turns in the future. So, if you wait a finite amount of time (in this case a "few" billion years") it's possible that the visiting condition might not yet be satisfied.

iliis 10y ago

True. I alluded to that further down, as even with the perfect strategy this means that "it is theoretically possible that the goal state never happens", i.e. the probability that the algorithm will terminate will never be 100% (but it terminates with probability 1).