31
$\begingroup$

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.

Does anyone know The optimal solution?

Note:

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

$\endgroup$
  • 6
    $\begingroup$ I think there strategy should be revolt and break out of the prison :P $\endgroup$ – Beastly Gerbil Sep 28 '16 at 10:28
  • 5
    $\begingroup$ What are we optimizing in "The optimal solution"? $\endgroup$ – JiK Sep 28 '16 at 12:28
  • 1
    $\begingroup$ what if someone die before he have the chance to go in the room ? $\endgroup$ – Seb Sep 28 '16 at 14:56
  • 4
    $\begingroup$ "The prisoners are to enter the room and move the clock exactly three (3) hours backwards or forwards." Can you clarify this? Does it mean that, if the clock says 6:00, a prisoner can leave it at 6, 3, or 9 when they leave the room? Or must they leave it at either 3 or 9? Or does it mean that if the initial position is 6, the puzzle is solved when all 100 prisoners have entered the room AND the final position of the clock is either 3 or 9? $\endgroup$ – Kokiomot Sep 28 '16 at 16:09
  • 4
    $\begingroup$ While it has been compared to "100 Prisoners and a light bulb", it is actually just a rewording of "100 Prisoners and two light bulbs", which I don't see on this site, but can be found on the Wu Puzzle forum (which has made significant contributions to the 100 Prisoners puzzles). The 4 possible states of the two light bulbs there corresponds to the 4 possible states of the clock here. $\endgroup$ – Paul Sinclair Sep 28 '16 at 20:29

10 Answers 10

13
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ @Lynn, I'm afraid that's not true. What if that non-leader turns the hand 'off' two times before one of the other non-leaders does it once and the hand was initially 'off' too? It might happen that the leader announces 'done' too early. $\endgroup$ – elias Sep 28 '16 at 11:45
  • $\begingroup$ You're right... I overlooked that case. $\endgroup$ – Lynn Sep 28 '16 at 11:46
  • $\begingroup$ still doesn't solve the case where a prisoner may die in between (and do not have a chance to turn the clock) lol $\endgroup$ – Jeffrey04 Sep 29 '16 at 9:25
  • 2
    $\begingroup$ @Jeffrey04, I'm not sure how the OP meant that note, and it needs some clarification: do the prisoners get notified if one of them dies or not? do they know who it was (specifically if it was the leader)? do they know if he already visited the room or not? $\endgroup$ – elias Sep 29 '16 at 9:31
  • $\begingroup$ meanwhile I posted another solution, that should theoretically do not need everyone to flick the state twice (: $\endgroup$ – Jeffrey04 Sep 29 '16 at 9:43
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I think a quite important difference from the well-known light bulb-version is that here the prisoners don't know the initial state, while in that one the light bulb is known to be off initially. $\endgroup$ – elias Sep 28 '16 at 11:43
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 197 will do, it ensures every person must have been in the room at least once, as 98 people visiting twice only achieves 196 total "on" states. The counter doesn't create "on" states at all (so just 99 people need to be counted). $\endgroup$ – Nij Sep 28 '16 at 23:39
  • $\begingroup$ @Nij, an initial 'on' state may result in 197 being too few: 1 coming from the inital state, and 2x98 from 98 other people $\endgroup$ – elias Sep 29 '16 at 8:06
  • $\begingroup$ @elias So 198 will be enough, then. Done! $\endgroup$ – Nij Sep 29 '16 at 8:09
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What does actually 'being recorded' refer to? Also, as the time between the visits is not deterministic, we cannot be sure if anyone was in the room in the first two months, and the clock has been reset, can we? $\endgroup$ – elias Sep 29 '16 at 8:08
  • $\begingroup$ Sorry about that. One person keeps tabs on the number of visits. So by turning the clock in the count position, this visit is 'recorded' and added to the final count. Yeah the reset is a little sloppy I'd say. I was considering counting up twice like the other answers but I'd probably not be free for a very long time since visits are determined by the roulette. $\endgroup$ – Putra Nursallihin Sep 29 '16 at 10:53
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I'm not sure we can suppose the clock's hand points to one of 3, 6, 9 or 12 initially. Otherwise this is the same solution that was provided at least in two different answers already. $\endgroup$ – elias Sep 29 '16 at 10:31
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I think it is a large assumption that you can move the clock. If you can then the problem becomes trivial. $\endgroup$ – sdrawkcabdear Sep 28 '16 at 19:20
  • $\begingroup$ A lot of questions pop up in my mind reading your solution: What happens if a prisoner dies after he has rotated the clock? How could the others know if he had visited the room before he passed away? Would they even be aware that he's dead? $\endgroup$ – elias Sep 29 '16 at 8:11
  • $\begingroup$ @sdrawkcabdear I thought I was thinking outside the box! $\endgroup$ – jstnthms Sep 29 '16 at 15:14
  • $\begingroup$ @elias I'd would assume they have to know how many prisoners are alive, otherwise it's impossible. As long as prisoners only rotate the clock 0.5s on their first visit, it will work out. At 100 prisoners, the requirement is 49.6s. Every time a prisoner dies, the requirement does down 0.5s. If 99 prisoners entered at least once and the clock would be rotated 49s. If one died, the requirement would be 49s. That last prisoner would see the requirement and make the announcement. If they died before entering, the next prisoner would see the requirement is surpassed and make the announcement. $\endgroup$ – jstnthms Sep 29 '16 at 15:30
  • $\begingroup$ Well, I think there is a difference between the cases if the one who has died did already turn the clock before or not. The required rotation decreases only in the latter case. So either they get this information as well, or a reset-strategy should be applied for that case so they can start over. $\endgroup$ – elias Sep 29 '16 at 18:34
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If the clock is in quadrant 3 when the counter visits, the counter can't reset it to quadrant 1 $\endgroup$ – Wossname Sep 28 '16 at 22:57
  • $\begingroup$ shoot you are right, he can only move it to quadrant 2 and increment his count by 1 $\endgroup$ – sdrawkcabdear Sep 28 '16 at 23:04
  • $\begingroup$ The solution would still work this just slows it down toward the end. In the early cycles they will be many more than 3 new increments before the counter returns so he just move the clock from 4 to 1 $\endgroup$ – sdrawkcabdear Sep 29 '16 at 0:46
-1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ can you elaborate this a little? what are the three positions? the hand can take 4 different positions if we move it by 3 hours - how do your selected positions relate to those? what should a non-leader do if the clock is in the same state as it was on his last visit? $\endgroup$ – elias Sep 28 '16 at 12:39
  • $\begingroup$ Prisoners always have to move the clock. They can not keep it at the same position. $\endgroup$ – w l Sep 28 '16 at 12:44
  • $\begingroup$ If they always have to move the clock then the problem is not solvable. A non-leader ignores the clock if it's in the same state as his last visit. $\endgroup$ – Dark Matter Sep 28 '16 at 13:29
  • $\begingroup$ @elias The three positions are "the initial position" (A), and the two "forward" ones the counter can move them to (B, C)... although it'd probably better to add in the fourth and use wrap around in terms of counting all this faster. $\endgroup$ – Dark Matter Sep 28 '16 at 20:53
-1
$\begingroup$

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
$\endgroup$
  • $\begingroup$ what happens if the initial state of the light bulb is off, but before the first visit of the leader another prisoner switches it on? the counter will never reach 100, i think. also, 'first time seeing it in off state' is better to be phrased 'seeing it off on his first visit', as if it's his first time seeing it off on his - let's say - 60th visit, it does not mean, the light buld was initially off (although i'm not a native english speaker, so i might be wrong with this one). what if the hand of the clock initially points to 5.30, is it on or off? $\endgroup$ – elias Sep 29 '16 at 10:23
  • $\begingroup$ also has another problem, when the initial state is ON, if old prisoners sent to the clock between leader's two visits, then the leader will have an extra increment, hmmmmmmm $\endgroup$ – Jeffrey04 Sep 30 '16 at 2:20
  • $\begingroup$ @elias when it is set to OFF initially every prisoner will contribute a +1 to the counter, the last +1 will happen when the leader sees the light bulb OFF the first time (subsequent visit seeing OFF doesn't count) $\endgroup$ – Jeffrey04 Sep 30 '16 at 2:25
  • $\begingroup$ old prisoner in my previous comment = not first visit $\endgroup$ – Jeffrey04 Sep 30 '16 at 2:26

Your Answer

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