100 Prisoners and 3-state clock

Question

100 Prisoners and a clock seems far too easy on the prisoners, so the exact same question, except that they must change the clock by exactly 4 hours:

There are 100 prisoners who are given a chance at freedom. The prisoners are randomly picked to visit a room where there is only a nonfunctional wall clock with a knob for manually changing the time.

The rules are as follows:

• The prisoners are to enter the room and move the clock exactly four (4) hours backwards or forwards. They must choose one and may not try to communicate with the others in any fashion (aside from changing the time).

• On any visit, a prisoner can announce that all 100 prisoners have visited, but must be absolutely sure (he will be required to divulge his strategy to win everyone's freedom).

• For each visit, the prisoner will be picked by spinning a 100-slot roulette wheel. Thus, the order will be completely random (Prisoner 5 might be chosen 100 times before Prisoner 99).

• Additionally, the visits will also occur randomly (perhaps 100 in a day, or perhaps a week without visits) and the prisoners have no knowledge of any visits aside from their own.

• The initial setting of the clock will also be unknown to the prisoners.

• As always, they may discuss a strategy beforehand.

What is a strategy that eventually leads to the prisoners being freed? (with chance arbitrary close to 100%)

bonus: How many visits will it take on average?

Answer 1

Here's how you can do this:

Everyone will have an internal counter, starting at 2 points. Choose one prisoner to be the "collector". We will use the clock to simulate transfer of "points" between players; the goal of this strategy is for everyone to transfer their points to the collector.

We consider the clock to be "full" when it is at 12:00. Otherwise, it is "empty".
The distinction between 4:00 and 8:00 will not matter for this puzzle - they are both considered "empty".

Now, if a prisoner enters the room and the clock is empty, they can deposit a point by changing it to full. (They then subtract 1 from their score.) If they currently do not have any points, they change it to the other empty state.

If a prisoner enters the room and the clock is full, they are forced to change it to an empty state. (They then must add 1 to their score, because they have picked up a point.)

If the collector enters the room, they will always make the clock empty; if there was a point, they will add that point to their score. When the collector's score reaches 200, they can successfully make the declaration and escape.

This works with probability 1:

Say the strategy is currently ongoing, and consider the sequence of names called from now on. It will almost surely¹ contain a point-holder's name, so a point will be deposited in the clock sometime in the future.
Now, take a look at only the names called after a point is deposited. This is another sequence of independent randomly generated names (in fact, a subsequence of the original). So it will almost surely contain the collector's name.

Therefore, with probability 1, the collector will pick up another point in finite time. This implies that as long as there are still points floating around the system, the number of these points will almost surely decrease. So the collector will pick up all points in finite time with probability 1.



And the collector cannot declare ending early: depending on the starting state of the clock, there are either 200 or 201 points total. In the first case, the prisoners each must have been in the room twice to deposit both of their points. In the second, the collector will declare the ending while there is still one point floating around, so each player has deposited at least one point.

---

¹ "almost surely" is a mathematical term meaning "the probability is 100%, but there may still be possibilities that violate this". For instance, if you flip a coin infinitely many times, you will almost surely get a heads. The sequence "tails-tails-tails-..." still exists, but the probability of you getting that sequence is 0.