Hacker News Reader

Comment by SilasX | Hacker News Reader

>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).

View on HN

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.

So? It doesn't have to be true that each prisoner will be visited within any particular time frame.

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.

> 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.

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.

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.

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.

Reply on news.ycombinator.com