[Guest]

I recently came across an interesting variation of the classic logic puzzle "100 Prisoners and a Light Bulb", which has been posted on this site.

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.
  

This is solved without tricks of any kind. Please do not raise semantics (it could take so long that the prisoners could die during the process).

Also, if you've heard this before, please do not post outside a spoiler. The idea is for people to determine the solution on their own even if they're already familiar with the original puzzle.

[Guest]

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

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.

[Guest]

This can be solved by transforming it into the original problem. First, the prisoner's designate from 12 clockwise to 6 (6 inclusive) as 'off' and from 6 clockwise to 12 (12 inclusive) as 'on'. Thus, at any position, 3 hours one way has it in the same region and 3 hours the other way changes the region. Now the solution is similar to the original.

Designate a counter. Whenever he goes in the room and the clock is at 'on', he turns it to 'off' otherwise he leaves it alone. For everyone else, whenever they go into the room and see the clock is 'off', if it is the first or second time they've seen it that way, they turn it 'on', otherwise they leave it alone.

Once the counter has turned the clock to 'off' 198 times, he asserts that they've all been in the room at least once.

The difference from the original problem is that you don't know what the starting configuration is AND you can't know if you are the very fisrt person in the room or not. That's why each person has to be counted twice. This way, if the clock starts in the 'on' position, then by the time the counter gets to 198, 98 people will have turned it to 'on' twice, one person will have turned it to 'on' once and once the counter will have counted it for nobody.

Though to be honest I'm hoping a more unique solution exists for this problem.

Edited July 7, 2010 by Tuckleton

[Guest]

Tuckleton, you have the answer that's most well known.

I doubt a more optimal solution exists (although I could never prove that).

I would definitely be interested in hearing it, however, if you cam across it.

[bushindo]

Tuckleton, you have the answer that's most well known.

I doubt a more optimal solution exists (although I could never prove that).

I would definitely be interested in hearing it, however, if you cam across it.

Tuckleton is correct. I don't think it is possible to find a more optimal solution because of the way the information can be passed between turns. The requirement to either move the clock forward or backward 3 hours on a clock every turn gives a little bit more than 2 pieces or information, but not quite 4 neither. If the prisoner can turn the clock to any of the four positions, that would be a different matter. It's an interesting extension, so I'll post a new thread on it.

Edited July 7, 2010 by bushindo

[unreality]

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

edit: nevermind, Tuckerton's solution still works. You can retain the state by simply moving the dial to the other position within the same state!

Edited July 7, 2010 by unreality

[unreality]

[12,3) - region 0

[3,6) - region 1

[6,9) - region 2

[9,12) - region 3

at any point you can always go down a region or up a region (wrapping around 3 up to 0 and 0 down to 3).

Think of the clock just a dial: 0 1 2 3, and the prisoner can rotate it one click in either direction if they choose.

1 counter prisoner and 99 normal prisoners.

If a normal prisoner sees it as 2 or 3 they must leave it alone unless they were the prisoner that moved into that 2or3 state. In that case they move it up (2 to 3, or, 3 to 0). Upon moving it to 0 they have "gone".

If a normal prisoner sees it as a 1 and have not yet "gone", they move it up to 2. Otherwise they ignore it.

If a normal prisoner sees it as a zero, they leave it alone no matter what.

If the counter sees it as a zero, the counter adds 1 to his score (his score starts at -1) then moves it up to 1.

When the counter counts to 100, he knows all prisoners have been there.

I think that might work but it's probably NOT more efficient than the other way. I guess it all depends on that roulette wheel

EDIT: nevermind! There's a 50% chance the dial will start in a 2 or 3 position, which creates an endless moratorium

Edited July 7, 2010 by unreality

[Guest]

Why is it 198 times? Why not 100? 99 times to count each prisoner other than himself, and one time in case it was "switched on" at the beginning?

Regarding Vinay's original riddle.

[Guest]

Why is it 198 times? Why not 100? 99 times to count each prisoner other than himself, and one time in case it was "switched on" at the beginning?

Regarding Vinay's original riddle.

Because then if the dial did not start in the 'on' position then the counter will never get past 99 (since all the prisoners have each turned it 'on' once and will not touch it again).

[Guest]

This can be solved by transforming it into the original problem. First, the prisoner's designate from 12 clockwise to 6 (6 inclusive) as 'off' and from 6 clockwise to 12 (12 inclusive) as 'on'. Thus, at any position, 3 hours one way has it in the same region and 3 hours the other way changes the region. Now the solution is similar to the original.

Designate a counter. Whenever he goes in the room and the clock is at 'on', he turns it to 'off' otherwise he leaves it alone. For everyone else, whenever they go into the room and see the clock is 'off', if it is the first or second time they've seen it that way, they turn it 'on', otherwise they leave it alone.

Once the counter has turned the clock to 'off' 198 times, he asserts that they've all been in the room at least once.

The difference from the original problem is that you don't know what the starting configuration is AND you can't know if you are the very fisrt person in the room or not. That's why each person has to be counted twice. This way, if the clock starts in the 'on' position, then by the time the counter gets to 198, 98 people will have turned it to 'on' twice, one person will have turned it to 'on' once and once the counter will have counted it for nobody.

Though to be honest I'm hoping a more unique solution exists for this problem.

So for this to work, the counter has to visit the room after each visit by a regular prisoner?