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