Fog Creek Software
Discussion Board




Answer to prisoners and switches

Here is an answer, but it may be suboptimal:

The prisoners elect a "counter" who will be responsible for announcing when all the prisoners have been in the room.

Each prisoner except the counter has the following modus operandi: If you enter the room and light A is off, and you have never switched switch A, then switch A on. Otherwise, toggle switch B.

The counter has a special protocol: If you enter the room and A is on, switch it off, increment your count by one, and leave. If your count has reached 23 (more on this below,) you announce that everyone has visited the room. Otherwise, A is off, and you merely toggle B and leave.

Because the counter only switches A off, and each prisoner only switches A on once, when the counter has switched A off 23 times, everyone must have been in the room. The reason the counter must count to 23, and not 22 or 24, is that there are 23 prisoners, but the counter having visited the room is trivially satisfied (so subtract one leaves 22) but the initial state of A is unknown, so we have to count one more just to be sure, to account for the case where A was initially on.

Note that this situation guarantees the prisoners' freedom with no risk to themselves (that is, assuming there are no homicidal prisoners) however it will take a very, very long time for them to be free!

Dominic Cooney
Tuesday, April 01, 2003

Almost!  Problem is if the initial state was A off and some prisoner other than the counter entered, he'd switch it on... which means the counter would never actually get to count up to 22... (counter would come in and see it on, but wouldn't know that another prisoner had switched it on.. .it could just have randomly been in that position).

mhp
Tuesday, April 01, 2003

I came up to the same solution  but with a small addition that fixes the problem: each prisoner, except the "counter", has two counts. The "counter" announces that everyone has visited the room when 44 has been reached. At worst, one prisoner will have visited the room only once.

Pierre B.
Tuesday, April 01, 2003

Taking it a bit too far... you need to tell the inmates that switch A is the highest and/or the on on the left.

David Rhoades
Tuesday, April 01, 2003

...and so you get into the room and find that A and B are rotary switches mounted on a single shaft.

Rick Pack
Tuesday, April 01, 2003

At says A and B are labelled and that they have an off and on position. Also, they are light switches but there is no light - they are not connected to anything.

OK, so you guys come up with that plan. But did you notice "given enough time, everyone will eventually visit the switch room as many times as everyone else".

So, all I gotta do is bring your counter guy in the first 23 days, and then bring in everyone else after him. What then?

X. J. Scott
Tuesday, April 01, 2003

The prisoners are sent into the room at RANDOM.  The guard isn't trying to foil their plan.. he just picks at random.

mhp
Wednesday, April 02, 2003

I think the answer should be modified to: "the prisoners other than the counter should switch switch B on if it is the first time that they see switch B is OFF".  Which elinimates the randomness and all situations will be satisfied.

If it wasn't for that "All prisoners are equally likely to visit the room given long enough time there can be no solution, of course.

Chang Zhao
Thursday, April 10, 2003

I like the "counter" solution, and think that you can account for the uncertainty of the first case, except for this:

"At any time anyone of you may declare to me, 'We have all visited the switch room.' and be 100% sure."

Maybe I'm mis-reading it, but that "anyone of you" part says to me that -any- prisoner should be able to tell when they've all visited.

Dan
Thursday, April 10, 2003

The prisoners elect a counter at the meeting.  The other 22 prisoners agree to be the counter's cronies.  The counter barks rules and a warning to any wayward crony:  Break the rules, and I'll feed you limb by limb to the alligators.

crony rules:  Toggle switch B for every visit EXCEPT your "stand up and be counted" visit (described below).  For your first visit, remember the position of switch A.  For your next visits, watch for evidence that the counter has visited (switch A has moved).  Once you've got this evidence (and NOT before), wait for a visit (perhaps this one) in which you find switch A OFF.  This is your "stand up and be counted" visit.  Turn switch A ON.

counter's MO:  In certain situations, the counter uses a two-visit "wave" tactic to avoid stagnation in his pursuit of freedom.  He accomplishes a "wave" in two of his consecutive visits (cronies can visit during a wave - in fact, that's the whole purpose).  From the counter's perspective, a "wave" will be considered an atomic operation.  The counter begins with PUNK=1 (to count himself).  If the counter ever finds switch A OFF, he "waves".  If he finds switch A ON, he turns it OFF and (unless this is his first visit) increments PUNK.  When PUNK reaches 23, the counter declares 'We have all visited the switch room.'

Dave Smith
Friday, April 11, 2003

How do the cronies know the counter has been?

The solution I had is a bit more complicated, and accounts for the case where the initial state of switch a is off.

Cronie algorithm:
  If I've already toggled A,
    toggle B.
  else, if this is my first visit,
    remember the position of A, and toggle B.
  else, if A has changed value at least once since my first visit,
    if A is off, toggle A.
  else
      toggle B.

Counter algorithm:
  If it's our first visit, or A is in a different state to our last visit,
    Toggle A.
  else if A is in a different state to my last visit,
    Toggle A, and increment counter.

Basically, this algorithm relies on some stuff.

The counter keeps toggling A. This is to allow the cronies to know that the counter has been. Once they see that A has changed state, they know they can pass into "stand up and be counted" mode.

I can still see problems with this in unusual sequences... the whole thing relies on not arriving at a stage where a cronie believes the counter has not yet been, and the counter actually having been. And also on everyone having the chance to turn A on, and not settling into an equilibrium where for at least one cronie, A is always on.

Not sure if there's a guaranteed end to that scheme...

Dave.

David Neary
Wednesday, April 16, 2003

Typo in the last one - algo for the counter is even simpler...

If it's our first time, toggle A.
If A has changed since our last visit, toggle A and increment counter.
Otherwise, toggle A.

Dave.

David Neary
Wednesday, April 16, 2003

And source to do it... shows an average expectancy of 720 visits (in total), with a fairly big variance. Over 100000 trials, I had a min around 300 and a max around 1500.

http://www.redbrick.dcu.ie/~bolsh/stuff/switches.c

Cheers,
Dave.

David Neary
Wednesday, April 16, 2003

its real easy...each day that prisoner states that all have visited and gets fed to the gators......after 22 times the only one left visits the room and states all have been there and gets released
norm robiosn

norm robison
Sunday, April 20, 2003

David

I think there is a flaw in your algorithm. Let's consider the case of three prisoners (C, P1 P2). Let's start with switch A on.

1) P1 enters, remembers 'On'.
2) C enters, toggles A off.
3) P2 enters, remembers Off
4) P1 enters, toggles A On
5) P2 enters toggles A Off.
5) C enters...

C now does not know whether 0 prisoners or two prisoners have visited, so doesn't know what to count.

P1 and P2 will never touch switch A again, yet C cannot announce.
Or did I misunderstand?

(He cannot infer anything from the position of switch B because we could insert an arbitrary number of other visits from P1 and P2 to get switch B into any position).

David Clayworth
Tuesday, April 22, 2003

Sorry retract that. Can't even read now.

David Clayworth
Tuesday, April 22, 2003

Okay, maybe I'm looking at this as a five-exclamation-point problem, but it seems like an obvious solution is to instruct each prisoner "when you go into the room for the first time, make a mark on the wall."  When a prisoner walks in and counts 22 marks, he declares, and everyone goes home happy.

Matthew F. Ringel
Wednesday, April 23, 2003

The first answer (with a counter to 23) is still correct, kind of, unless I'm misreading it.

If it is your first time in the room while switch A is off, turn it on.  If it isn't your first time, or switch A is already on, toggle B. The counter would then discard the first time (s)he is in the room, as we are unsure of the starting position of A.  A should be in the off position after the counters first visit.  If it was on, turn it off, and if it was off, toggle B.  The second time, however, if A is on, (s)he can add 1 to the counter, making it 1.  Continue this until the count is 23 (22 other inmates, the counter being trivial, and 1 discarded).

Of course, this does not work if anyone is cheating.  If an inmate is cheating, they can flip the switch twice, causing the counter to be off, or never flip the switch on, causing everyone to be there a very long time.  The counter, if they are a masochist, could guess incorrectly, or never guess at all.  The guard could refuse to be random, and leave years between picking the counter.

Assuming that everyone plays fair, and everyone wants out as soon as possible, this would work, but could take a very long time.

Adam Thayer
Wednesday, April 23, 2003

Adam, the problem is that the 'discarded' count might or might not not represent an actual count. If the counter announces when the count reaches 21, then only 21 prisoners might have visited the room, resulting in a severe case of alligators. If he waits to 22, and the counter's first visit represented an actual count, then there might never be a 22nd count. (No prisoner will flip switch A twice).

David Neary's solution is the best I've seen since the original Car Talk solution which required every prisoner to flip the switch twice).

David Clayworth
Thursday, April 24, 2003

Different idea:

The prisoners agree on a grey-code counting scheme:
    AB
0: 00
1: 01
2: 11
3: 10

When one goes in, he notes the state and advances it by one.  When he comes back,  he has some information about how many others have been there.  Of course, if there have been > 3 visits, he can't be sure whether it was i visits or 4*n*i visits.  So he's conservative and uses just the distance.  The puzzle says the warden can pick the same guy "three times in a row" so each guy needs to see 23*3 moves to be sure all 23 guys have visited.  The first guy to accumulate that many visits announces and everyone goes free.

Example1:  You go in, you see 00.  You set to 01 and leave.  Your next trip, you see 11, a distance of 1 from when you last saw the counter.  You know there's been either 1 other visitor, 1+1*4 other visitors, 1+2*4 other visitors, etc.  Also, since one guy might've visited 3 times, there could have been 3 other visitors (1+1+3 mod 4 = 1) You know its at least 1 visitor so you accumulate 1.

Example2:  You come in your second time and see a distance of 3.  You still accumulate 3, but that's why you're letting the accumulator run up to 23*3.


~gb

Greg Bell
Thursday, April 24, 2003

The switch is in an unknown state.  If the counter is the FIRST person in, then the switch could be either.  If he is not the first person then the switch will be on, either because of the initial state or because it has been flipped.

Therefore, he will count 22 prisoners plus 0 or one depending on the inital state.

If every prisoner flips it twice, he will count 44 flips plus 0 or 1. 

Assuming an inital state of 1, on getting to 44 there have been 43 flips.  One prisoner has visited only once.

It then does not matter what the starting state was. 

If single flips, he cannot be sure that all have visited.

Fergus Allan
Tuesday, May 13, 2003

*  Recent Topics

*  Fog Creek Home