3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ When/how do they get freed? $\endgroup$
    – ken
    Jun 2 at 20:42
  • 1
    $\begingroup$ I could have formulated better, but: See point 2: If a prisoner can state with 100% certainty that all 100 prisoners have visited (and gives their reasoning) all prisoners gain their freedom. $\endgroup$
    – Retudin
    Jun 2 at 21:05
3
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ I have a hunch that this strategy works, but can you also cover the case where the collector happens to always be called when the counter is empty (e.g., by calling two prisoners who still have points consecutively before the collector)? I think you need to show that this event has probability 0. Just ensuring that the collector is eventually called doesn't directly guarantee this. $\endgroup$
    – justhalf
    Jun 3 at 5:00
  • 1
    $\begingroup$ @justhalf I show that the collector is eventually called immediately after a point is deposited. After a point is deposited, the counter is not empty. $\endgroup$
    – Deusovi
    Jun 3 at 5:12
  • $\begingroup$ Ah, I see, so by "This is another sequence of independent randomly generated names" you mean all instances of names that appear when a point is on the clock, not necessarily a single instance of the clock having a point (e.g., specifically at step K where K is found on the previous step). I initially understood this as the sequence of names appearing any time after this point. The proof works, then. Thanks for the clarification! $\endgroup$
    – justhalf
    Jun 3 at 5:25
  • $\begingroup$ For fun, can you calculate the expected number of turns until success? I simulated for N=3 (3 prisoners) and it turned out to be 37 turns. $\endgroup$
    – justhalf
    Jun 3 at 5:26
  • $\begingroup$ The histogram looks quite smooth for 1 million trials: i.stack.imgur.com/rxUVv.png (also, I just realized that calculating the average is part of the question as well, for bonus) $\endgroup$
    – justhalf
    Jun 3 at 8:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.