100 Prisoners and a clock

Question

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 three (3) 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 the optimal solution?

Note:

It could take so long that the prisoners could die during the process.

Answer 1

This one actually can be solved via the same method as the 100 prisoners and a light bulb problem, but there is still a twist because we don't know the initial position of the hand of the clock. I haven't yet figured out what to do with that, so this is only a partial solution. EDIT: I added a paragraph which solves this problem.

They have to choose a leader, who will be the one which will be aware, that everybody has already visited the room.

They also have to split the face of the clock (figuratively!) in two halves, let's say for an upper and a lower half. We should consider 3 o'clock belonging to the upper half, and 9 o'clock belonging to the lower half. With this setup at each visit a prisoner can choose to move the hand to the upper half or to the lower half, which basically works as the toggle did in the light bulb version. So let's say the leader is the only one who moves the hand from the lower half to the upper half (~ switch the light on) (or leave it in the upper half if it was already there). Everyone else can move it from the upper half to the lower half exactly once (~ switch the light off), otherwise should leave it in the half it was before. The leader can count the times he moves the hand from the lower half to the upper half.

But if the hand was initially in the upper half (~ the light was on), he should do that 99 times before announcing everyone has already visited. Noone will turn it back to the lower half any more, so he should not wait for a 100th occasion.
If it was initially in the lower half (~ the light was off), he should wait until he turns it up 100 times.

How to overcome this problem?
I think the following approach works: every non-leader is allowed to 'switch the light off' 2 times. That makes 198 down-switches in total, and maybe as an extra the initial setup was also 'off'. So the leader can 'switch it on' 198 or 199 times depending on the initial state. But if he announces after 198 up-switches, that everybody has visited the room, it will be true. There might be someone who visited it only once if the initial setup was 'off', but it's not a problem.

TL;DR: Chosen leader is the only one who might turn the hand from lower half to upper half, and keeps counting how many times he does this. Everybody else can turn the hand from upper half to lower half exactly twice, otherwise has to turn it so it remains in the half it was before. Leader can announce that everybody has visited on his 198th lower-to-upper half turn.

Answer 2

This can be rescued to the light bulb problem which has the binary condition of a light bulb being on or off. Similarly here we can have the possibilities:

0 < time <= 6 - call state 0

and

6 <= 12 - call state 1

You can always switch between the two by moving just 3 hours. The solution therefore is the same as the light bulb problem from here on. But I actually don't know that solution.

Answer 3

As someone pointed in another answer, the same solution described by Dr. Yisong Song in the topic 3.4 (https://www.math.washington.edu/~morrow/336_11/papers/yisong.pdf) can be used here by making the clock simulate the bulb states on/off.

I will just copy and paste his explanation here since it fits perfectly:

3.4.2 Explanation: The idea behind this protocol is that every prisoner besides the counter will turn ON the bulb exactly once, whenever he can. When the bulb is ON, no one can turn it OFF except for the counter. Eventually the counter will enter the room, turn this bulb OFF, and increment the count T . In this way, each prisoner indicates his presence in the room to the counter by leaving an ON bulb which is eventually recorded by the counter.

There is only two things we need to do in order to use this solution here:

1. Simulate states ON/OFF: that one is easy, the prisoners just need to agree that when the hour on the clock is between 0 (or 12) and 5 that means ON and between 6 and 11 that means OFF.

2. Mandatory movement: There is a small difference here as you may noticed. The original problem states the prisoner can choose not to change the bulb state, but the problem proposed here states that the clock must always be set 3 hours backwards or 3 hours forward. No problem, a clock that moves 3 by 3 hours has 4 possible positions (12 divided by 3), or 4 states. Two of these states will always mean ON and two will mean OFF, as stated on item 1. Explaning by example: suppose a non leader prisoner already moved the clock to ON state, on his second visit to the room he must not change the clock state at all, if it's ON it must keep ON, if it's OFF it must keep OFF, suppose the hour is 4 (ON) he just need to move the clock to 1 (also ON), and that's it. Same logic applies to the leader when he visits the room and the clock is at one of the two OFF positions.

There's only one more complication here, we don't know the initial state, if it's OFF the solution works perfectly, but if it's ON we have a problem. If it's ON and the first prisoner picked is the leader he will start counting when he shouldn't, if it's a non leader he will not now he's the first and will leave the clock ON without considering he was the one who set it to ON when he actually should. That leads to a very small possibility of counting 100 prisoners when only 99 visited the room. Since we want the perfect solution, the only way is to make each prisoner "turn" the clock ON two times each, and instead of counting until 100, the leader counts until 200 (or maybe 199 will do, I'm not sure and I'm too tired to think).

More details about the complexity can be found on the same link.

That's it.

Answer 4

Probably an oversimplified way of trying to solve this.

Assign leader to keep tabs on the number of visits. Each visit is then recorded to the final count.

• Reset Position: 12 and 3
• Count Position: 6 and 9
• Your visit is recorded if you move from reset to count position
• If during your visit, the clock is in count position, your visit is not recorded
  
  

Resetting Initial State on Clock

During the first month, no one’s visit is recorded. Within the next 30 days, if the clock is in count position, return to reset position.

If your visit has not been recorded:

• If the number is in reset position, move to count position
• If number is in count position, keep in count position. This visit has not been recorded.
  

If your visit has been recorded:

• Keep the number in the reset or count position.

Leader will add to total count and reset clock everytime he enters the room. Do this 99 times.

Answer 5

Assign a leader, he will be the one keeping the tally.

Hours 9/12 mean the clock is reset.
Hours 3/6 mean the clock is active.

If the leader finds the clock at 12, he'll move it to 9
If the leader finds the clock at 9, he'll move it to 12

If a prisoner finds the clock at 12

• If it's his first or second time there, he moves to 3
• If not, he moves to 9

If a prisoner finds the clock at 9

• If it's his first or second time there, he moves to 6
• If not, he moves to 12

If the leader finds the clock at 3, he'll move it to 12 and count +1
If the leader finds the clock at 6, he'll move it to 9 and count +1

If a prisoner finds the clock at 3, he'll move it to 6
If a prisoner finds the clock at 6, he'll move it to 3

When the count is at 198, the leader is absolutely sure everyone entered the room. Next time he goes there, he can then announce it.

Why does each prisoner need to 'activate' the clock twice? To account for the fact that the leader does not know if he is the first to enter the room or not, if he somehow finds the clock at 3 or 6 the first time he enters.
When the count is at 198 then he is absolutely sure that 98 other prisoners visited the room at least 2 times, and the other 1 visited at least 1 time.

If the clock somehow shows an hour different from 3/6/9/12, then it's just a matter of rotating the solution.
1=2=3
4=5=6
7=8=9
10=11=12

Answer 6

There is no solution to this problem:

Issue 1: The number of prisoners at the end of the experiment is unknown (prisoners may die during it). Suppose No 67 and 33 die. There is no way of knowing whether they are dead or have not yet been randomly selected to set the clock.

Issue 2: Randomness means there is no way for the participants to know what signal to set. The original lightbulb form of the question was when will there be a 50% probability that all prisoners have entered the room. This question is when will you know. There is also no answer to that.

Answer 7

I'm going to make some assumptions for this strategy to work:

• the clock can be removed from the wall to be placed anywhere in the room and the guards will respect that placement
• if a prisoner dies, the required number of unique visits is adjusted accordingly
• the clock is a basic wall-mounted clock with a circular shape, and has markings for seconds

The first prisoner butts the clock against any wall with 12 perpendicular to the wall. Subsequence prisoners will rotate the whole clock counter clock-wise half a second, but ONLY on their first visit. Once the clock is rotated to (prisonersAlive/2 - 0.5) seconds perpendicular to the wall, that prisoner can make the announcement. The clock time can be arbitrarily moved forward or backwards 3 hours as it doesn't matter in this strategy.

Answer 8

A slight improvement we can take advantage of the fact that the clock has 4 quadrants to solve the problem faster. It looks like roughly 2/3 as many visits would be needed.

We divide the clock into 4 quadrants of 4 hours each and designate 1 prisoner as a counter.

The quadrants have the following meanings

12 - 3 0 people have visited the room since the last time the counter last visited 3-6 1 person 6- 9 2 people 9 -12 3 people

The first time the counter visits the room he sets the clock to the first quadrant but ignores the count. There after he sets the clock back and adds the total to his count.

Everyone else just increments the clock 1 place when they visit. But they can only increment it 4 times, no matter how many times they enter the room, and when it is at the last quadrant they leave it alone.

How do we deal with the fact that there could be 3 counts missed in the initial clearing of the clock?

We have each person increment the clock 4 times and have the counter call success after 400 - 3 counts have occurred.

That insures correctness but how about speed?

On average 50 people will be called into the room between every time the counter is called in, so on average he will count 3 every time he enters.

So on average it would take 50 * 397 /3 = 6,616 visits. The standard version with 2 flips per person takes 50 * 198 = 9,900 visits. This analysis does not take into account the coupon collector problem that will make the last few flips hard to get but the standard solution with have a worse time with that, I will add this if I have time.

Basically getting the counter in the room is so rare we need to make the most of the situation.

Answer 9

Think of the clock as having three positions.

So,

Non-leader prisoners are only allowed to move the clock backwards, and only if the clock is different from their last visit.

And

The leader's first visit will be to move the clock forward, after that he'll either move it forward again if it's still in that spot (to the 2nd "forward" position), or if it's already on the 2nd "forward" position he'll move it backwards to the 1st "forward" position.

And

Different non-leader prisons will have different ideas on what the "original" clock position is. But the leader will count how many times someone else moved it backwards.

For Clarity:

Think of the clock has having positions "A", "B", and "C". Non-leaders can only move the clock from "B" to "A", and from "C" to "B". If the leader finds the clock at "A" he can move it to "B" (and he knows if he moved it to "B" or "C" so that counts one or two prisoners). The leader himself switching the clock between "B" and "C" solves the "unknown init state" issue.

Answer 10

First thing first, the prisoners split the clock into two parts, and assign them into either ON and OFF zone. For instance, [12, 6), which is technically 12 to 5:59:59 (ON), and [6, 12) and 6 to 11:59:59 (OFF).

Then they need to elect a leader. The leader, will carry a counter, which starts at 0, and must always leave the room with clock set to OFF state. The rest of the prisoners, must only switch the clock to ON state IF AND ONLY IF

• Not first visit, AND
• Light bulb is OFF, AND
• This is the first time switching to ON

otherwise, just leave the room without changing the state.

Whenever the leader enters the room, he increments his counter IF AND ONLY IF

• First time seeing it in OFF state (would only happen if the clock initial state is OFF), or
• When it is ON

Then the leader MUST always leave the room with the clock set to OFF state.

When the counter reaches 100, that is the day everyone gets freedom (:

When will this fail

• Initial state is ON (this causes the counter to reach 100 earlier):
  1. The leader enters 2 times in a row
  2. No new prisoners visit the room between a 2 consecutive visits by the leader
• Any prisoner dies in between