Fog Creek Software
Discussion Board




switches solution?

i've come up with a solution, but surely not the simplest or fastest...

the prisoners pick one person to be the "counter."

every time the counter goes into the room, he/she looks at switch A.  if it's up, he/she moves it down and adds 1 to his/her count.  if it's down, he/she toggles switch B.

all the other prisoners need to signal TWICE to the counter that they've been there.  which means everyone else needs to move switch A from down position to up position twice.  if switch A is down, and they haven't already flicked it up twice, then they move it up (for either the first or second time for that person).  if switch A is up, or if they've already used it twice to signal the counter, then they simply toggle switch B.

when the counter has caught switch A in the up position 44 times, he/she knows for a fact that everyone has been in the room.


originally, i thought people would only have to signal the counter once, and the counter could stop at 22.  (the counter doesn't have to count his/herself.)  however, if the initial position of switch A is in the up position, and the counter finds it like that on the first visit and counts it as a person, then the count is off by one person (that is, 1 initial up position plus 21 prisoners = 22 counts, leaving 1 prisoner out).  forcing everyone else to signal TWICE via switch A allows for that initial position to be accomodated for (that is, 1 initial up position plus (21x2) prisoner signals = 43 counts, leaving 1 prisoner out, so when the count gets to 44, everyone else HAS to have been there).


this solution doesn't seem to be the BEST solution, as it seems like it would take a very long time to come to fruition, especially since the counter has to visit the room to reset the switch between counts, and if the counter were one of the last people to visit the room, well, it would take quite a while.  but at least it's a surefire method...

Pan Walker
Thursday, December 09, 2004

Here is my solution. I'm not 100% sure it's correct, but I wrote a script to simulate it, and it seems OK. Like yours, there is one master counter, and the other prisoners check in with the master counter. However, they only check in once each. To achieve this, the non-counters do not move A until they have seen it moved. That ensures that the master counter will catch the check-in. Here are the rules:

Master Counter:
If A is off: Flip A to on. Next time, flip it from on to off (see next rule).
If A is on when first seen or due to self-flip: Flip A to off.
If A is on due to another prisoner flipping it (the only remaining case): Flip A to off and tally the check-in.

Other Prisoners:
If A is on: Flip B.
If A is off, this prisoner has not flipped it yet, and A has moved between visits in the past: Flip A to on.

The catch here is that the master counter has to flip the A switch frequently (I chose every time, but that may not be optimal) to ensure that newly arriving prisoners see movement in A and realize they are allowed to check in. This means that A is on a large portion of the time. For that reason, it may not actually be faster than yours. I'll try it in the simulation and report back.

masharpe
Monday, January 03, 2005

Sorry, I mistated my solution.

"To achieve this, the non-counters do not move A until they have seen it moved."

should be

"To achieve this, the non-counters do not move A until they have seen it on."

and

"If A is off, this prisoner has not flipped it yet, and A has moved between visits in the past"

should be

"If A is off, this prisoner has not flipped it yet, and A was on in a past visit"

I think the way I originally posted would work, though.

masharpe
Monday, January 03, 2005

(another error in my first post: there should be an else clause at the end of the "Other Prisoners" rules that has the prisoner flip the B switch)

The results are in. I ran five sets of a thousand trials for each strategy. The average visits in each set are rounded to the nearest integer.

Single Check-In:
721
717
711
715
721

Double Check-In:
723
709
720
715
717

The two methods seem to perform pretty much the same, assuming my simulation is working correctly. I also tried single check-in with the leader randomly not switching A on, but it did not make a noticeable difference.

masharpe
Monday, January 03, 2005

masharpe's solution does not always work: The warden may bring the master counter in twice in a row always. (He could bring each prisoner in twice in row always to make the totals work out.)

In that case, no one but the master counter ever sees the A switch on.

Pan Walker's solution may be unclear about why 44 works but 43 does not.

Solution:

Master
If A is on, flip B.
If A is off, flip it on, and tally a count.
When count hits 44, you are done.

All others
If A is on, and this is either the first or second time you have seen it on, flip it off.
If A is off (or if A is on and you have seen it on at least twice before) flip B.

Why are 44 sufficient? Two cases:
1) A starts out off.
In this case, the master will tally a false count. So 43 are not sufficient. That would be 1(false) + 2*21(repeaters), so it would be possible for one prisoner never to have reported.

But 44 = 1(false) + 1(single) + 2*21(repeaters)
You cannot reach 44 without each non-master being counted at least once.

2) A starts out on.
In this case, every flip is counted, and there are guaranteed to be 44 flips.

Christopher Dunn
Monday, January 03, 2005

The best way is when all the prisoners meet they can talk among themselves that whenevr the warden is gonaa ask them about their visit evryone must agree.That way all of them will be freed without bothering abt the switch position

karthik
Tuesday, January 04, 2005

Jeez... Okay, game theory here.

No one wants to get eaten by an alligator, however narrowing down the number of inmates in the prison would make it easier for one to claim that all the switches were flipped. 

The crucial line here... "The switches are not connected to anything."

So, some prisoner who is hearing all the other prisoners say "Hey, the switches aren't connected to anything" is going to think that they are all conspiring against him so that he would be eaten, he won't believe them and continue thinking the switches actually are connected to something.  Once he visits the room, and sees that the switches aren't connected to anything he'll be singing with the choir.

Agg, its late, I'm tired, enjoy.

Brian Momeyer

Brian Momeyer
Tuesday, January 04, 2005

Christopher Dunn,

"masharpe's solution does not always work: The warden may bring the master counter in twice in a row always. (He could bring each prisoner in twice in row always to make the totals work out.)"

The warden says, "I'm going to choose prisoners at random," so I'm safe. Thanks for pointing that flaw out, because I hadn't thought about that possibility. Pan Walker's solution is also a little less complicated, so I admit that on the balance it's a better solution, although I like the elegance of the single check-in system.

masharpe
Tuesday, January 04, 2005

Pan's solution makes a lot of sense...
Quite simply, the first time the Counter enters the room, one and only one of the other prisoners MIGHT have turn A on, no matter how many prisoners visit the room prior to the Counter.

However, the Warden can be a real jerk an extend their stay as long as he wants. 

He makes two claims.  That they will be chosen at random, and they will all eventually enter the room the same number of times.  These can't both be true.  There has to be some order to his selection.

I believe that "random" is just to inform the prisoners that they cannot assume that they will be chosen in a particular order.  However, the Warden may still choose the prisoners in a particular order and they would know no different.

Suppose the Warden selects the same guy to enter the room every day for a year.  Then the next guy the next year, etc.  This will take 23 years, and the prisoners will have learned nothing (the counter visits the room and sees no change to A so he can assume nothing).

If the Warden continues this selection process, it will take potentially another 23 years for the counter to see a change to switch A. 

Eventually at worst to 23*43-1 years (988) for the counter to realize that they have all visited the room.

The prisoners would have to pray for patience and longevity.  :-)

Will Smith
Thursday, January 06, 2005

Now suppose an alternate solution:
The prisoners ignore the switches altogether and...

(1) The first time they visit the room make a scratch on the wall to indicate they were there.  If someone sees 22 scratches, they are free.

or

(2) in general, leave something behind that they can easily count.

This of course assumes that the Warden will allow them to perform such actions.

Again, even if the Warden allows them to do this, it could take them a very long time (see my previous post)

Will Smith
Thursday, January 06, 2005

Pan Walker's solution sounds good, I couldn't come up with anything else.

"But, given enough time, everyone will eventually visit the switch room as many times as everyone else."

Too bad "enough time" isn't defined, otherwise everyone could just count how many times they have been to the room, and when 24 or so is hit, they could be sure they all have.

Erkki
Thursday, February 03, 2005

After a longtime I am visiting this site. karthik's solution seems interesting :)

I solved this problem about 4-5 months back exactly the way Pan did and like him even I got stuck at the 22nd count so I also doubled it to (43/44 counts). Pan I dont think there can be a better solution to this though a long and time consuming but I think its the only way which will give a sure shot escape to the prisoners.

Vivek Gupta
Tuesday, February 08, 2005

Why don't the prisoners just have their "strategy" meeting in the switch room and then go back out and tell the Warden that they have all been there and go home?

R Berry
Friday, March 04, 2005

*  Recent Topics

*  Fog Creek Home