One more good puzzle

[doormat]

This is not really a probability problem but a good one nonetheless. I will be out of town for awhile after tomorrow so I may not be able to confirm any solutions or answer questions after that, but it does have a solution.

You are one of seven prisoners. The seven of you are each housed separately, and each has no contact with any others. There is a room containing two switches, each switch having two possible settings: up, or down. You have no information on the starting position; the switches might currently rest in any of the four combinations.

In a short while the authorities will begin to conduct random drawings. Each drawing will select a prisoner to go to the switching room. There, the prisoner must flip exactly one switch on each visit. Because the drawings are random it is possible for prisoners to make repeat trips, or be skipped entirely for long stretches. Moreover, there is no way to draw an inference from elapsed time - you might make two trips an hour apart, then one a week later, yet no other prisoner might have made an intervening trip.

There is a way out. As soon as one of you can state with CERTAINTY that all seven of you have made at least one trip to the switching room you will all be freed. If one of you decides to guess instead and is wrong, you will all be killed. You will be brought together before the trips start for one strategy session. What is your strategy?

doormat

[AwesomeAli]

could you clarify the rules

I believe it can be done by leaving a mark in the room, is this allowed?

If so, in my strategy meeting with the other 6 prisoners i would tell them to all leave a mark of some sort in the switch room and once there are 7 marks, i know all 7 of us have been in there

FREEDOM!!!

AwesomeAli

[Gus]

Quite a tough one I guess... I read your post this afternoon and have been thinking about it on and off for a few hours. I might have a solution but it seems a bit twisted. Anyway, here we go:

7 prisoners : A, B, C, D, E, F, G.

2 switches : Left and right (for my solution you have to be able to differentiate the 2 switches, so we assume we've got a left one and a right one).

The prisoners agree on the following strategy: prisoner A will be the 'counter', he will have a special role and is the only one allowed to go to the guard to give the answer. He will also be the only one allowed to pull the left switch down. Each prisonner must switch according to the following table (depending on what state the switches are when they enter the room):

UD ... means left switch Up , Right switch Down

Prisonner A
UU -> UD
DU -> UU
UD -> DD
DD -> UD

Prisonner B to G
UU -> UD
UD -> UU
DU -> UU
DD -> DU ... if the last time you came you were not in DD
DD -> UD ... if the last time you came you were in DD

Prisonner A will only start counting after having put the switches in DD position. Then if he sees them in position DU 6 times in row he knows that every prisonner has come to the room (including himself of course). If this does not happen (say he sees them only 3 times, then sees DD because he's been coming twice consecutively), the sequence starts from scratch again until he is allowed to put the switch in position DD. Those rules should also cover the 'doubling counting of prisonners).

The sequence you will need to be free would be something like... A-B-A-C-A-D-A-E-A-F-A-G-A. I guess it could take some time for that sequence to 'randomly' happen.

There is no guarantee that prisonner A will be able to tell on the first time this sequence happens: for the sequence to work you also need to have none of the prisonner B to G to have seen DD just prior to the sequence... if one of them has then you need to wait for another occurence... probably a few hundreds years... they'll be all dead by then anyway.

This would actually work whatever the number of prisonner... Is this close, or is there an obvious solution that I missed?

[CMangano]

I don't think this is the right solution, but I think it could be close.

One of the prisoners has to be a counter. The counter will only move the switch on the left if it is in an up position. He will also add 1 to his count. The remaining prisoners will only move the switch on the left if:

1) It is in a down position

2) It is their first time moving the left switch.

If both of these conditions are not met, the prisoner will move the switch on the right.

So everytime the counter sees the switch up, he counts it and moves it down, until it has been up 6 times. The only problem with this solution occurs when the switch starts in the up position AND the counter is the first prisoner sent into the room.

Looking forward to hearing the correct solution.

[cepstrum]

solution:

designate one switch the "odd" switch, and one switch the "even" switch. every time a prisoner makes a visit, he toggles the "odd" switch if this is an odd visit for him (1, 3, 5, ...), and the "even" switch if this is an even visit (2, 4, 6, ...).

each prisoner also keeps a running count of even toggles and odd toggles that he observes (not including when he moves the switch himself). that is, if the odd switch has changed positions since his last visit, he concludes that at least one other person has made an odd visit, and increments his odd visit counter. similarly, if the even switch has changed positions since his last visit, he concludes that at least one other person has made an even visit, and increments his even visit counter. also, since the total number of even visits can never exceed the total number of odd visits, each prisoner also adjusts the odd counter to be the same as the even counter if and only if his even counter is higher.

since the difference between odd visits and even visits for a given prisoner can only ever be 0 or 1, then each prisoner merely has to wait until his personal odd counter exceeds his personal even counter by the number of prisoners excluding himself. it may take a long time, and a ton of visits, but this will eventually happen.

a problem related to this one that is more in keeping with the spirit of this board: how many total visits, on average, should we expect for a correct answer given n prisoners?

good luck

cepstrum

[Gus]

I probably missed something in your explanation, but I think there might be a problem with your solution: It appears to be very easy to 'double count' a prisonner: let's consider the following events:

Let's say the left switch is the 'odd' counter, the right one the 'even' counter. For each event, I give:

_ the name of the prisoner (A or B)
_ the number of visit the prisoner has made
_ the position of the switches when he enters (UU, UD...etc)
_ the position of the switches when he leaves
_ the 'odd' count of prisonner A
_ the 'even' count of prisoner B

A (1) DD -> UD 0 0
B (1) UD -> DD - -
A (2) DD -> DU 1 0
B (2) DU -> DD - -
B (3) DD -> UD - -
B (4) UD -> UU - -
A (3) UU -> DU 2 0
... etc

So after those events, the difference between A 'odd counter' and A 'even counter' is already at 2, even though only B has been coming to the room so far.

Let me know what you think.

[daryn]

this answer by CMangano seems to be perfect. the prisoners get together, and elect a foreman. say it's me. i tell everyone:

if you go in, and you see the switch on the left is in the down position, AND it's the first time you've entered and seen the left switch in the down position, then switch it up. if you go in and the left switch is in the up position, don't touch it, do whatever you want with the right switch and leave. and then i'm the counter, and every time i go in and see the left switch is up, i switch it down, and add 1 to my count (starting from zero). as soon as i get to 7, then we all definitely have come into the room. i say 7 to handle the situation where i come into the room first and the switch is in the up position. good solution by CMangano i think.. if anyone thinks this is less than perfect, i'd like to hear why. i just wanted to clarify it totally, mostly for myself, i'm not trying to take any credit whatsoever for this solution.

[CMangano]

I don't think you can count to 7, as there is a very good chance you will never get to 7. The only way you could get to 7 is if the switch started in the up position when the counter went in (meaning no one had flipped the switch yet). Otherwise, he will be stuck on 6 forever. I don't think my solution is perfect, but I think the chances of the prisoners leaving the prison in a reasonable time frame without being killed is pretty high. I can only think of one scenario where they would guess wrong and die.

[Gus]

Sorry I made a typo while giving the switch tables for the prisoners.. it should read...

Prisonner A
UU -> UD
UD -> DD (counter starts at zero again)
DU -> DD (counter starts at zero again)
DD -> UD

Prisonner B to G
UU -> UD
UD -> UU
DU -> UU
DD -> DU ... if the last time you came you were not in DD
DD -> UD ... if the last time you came you were in DD

cheers

[Gus]

yet another mistake.... for prisoner A,
When DU -> DD ... then the counter does not go to zero but prisoner A increaes his counter if he left it at DD previously.

[doormat]

Cmangano, your solution is almost right - it just fails to account for one case. If the left switch is up when the counter gets there the first time, he doesn't know if someone was there before him or if it started that way. So to be sure that all the prisoners are accounted for at least once, the strategy is that everyone should move the left switch the first TWO times they find it in a down position, otherwise they flip the right switch. Now it doesn't matter in what position the switches started or who got there first - once the counter counts to 11, he can be sure that everyone was there at least once.

doormat

[tcdiscenza]

I haven't viewed any of the replies yet - but I'm going to go out on a limb and post my answer first.

I believe there is no mathematical solution to the problem and that this one requires an 'out-of-the-box' solution.

I would propose that each of 'us' (the prisoners) agree to leave some personal item or mark in the switch room on our first visit *only* to signify that we have been there. How obvious or not this item or mark could be would depend upon whether or not the guards or staff ever are permitted to enter this room.

It could be:

- a sock/shoelace
- a scratch mark on the door
- a stone/pebble placed in a certain corner
- a thread from our uniform
- etc.

I don't believe with just four states on the switches and seven individuals this can be solved matematically. Am I wrong? Guess I'm about to find out...

- Todd

[tcdiscenza]

OK...OK...there *does* seem to be a mathematical answer here (I guess...I didn't take the time to really think through all of it yet)...

BUT...

Doesn't the solution that AwesomeAli originally proposed and that I also came up with

MAKE A HELLUVA LOT MORE SENSE?!?

Do you really want to risk your life on the fact that some prisoner who is presumably half starved, dehydrated, and likely sleep deprived is going to remember to count correctly and pull the correct switch.

I guess in retrospect the guards *are* going to be coming into the switch room to check that a switch was flipped, so my proposal would have to be very subtle, but I think a thread from a piece of clothing could be overlooked (or seven for that matter).

I vote for me and Ali! ;-)

- 'Awesome'Todd

[felson]

This problem was presented on the "Car Talk" radio program a few months back. Doormat has gotten it right, nice job!

[tcdiscenza]

umm....he was the one who posted the problem in the first place... lol

[Saborion]

Hi.
Clearly there`s something I`ve missed since people seem to agree on the answer, and I`d like to know what it is. =)

Assume A is the first person to enter, and the left switch is up. He has to count this since he doesn`t know if he`s first or not. Count = 1
Then B will enter twice in a row (with A in between to count naturally). Count = 3
C enter twice. Count = 5
D enter twice. Count = 7
E enter twice. Count = 9
F enter twice. Count = 11

Now, according to the answer, this should be sufficient to know everyone has been in there at least once. But G hasn`t been in there. Where`s my mistake?

[doormat]

Hi Saborion,
The counter, "A", doesn't start his count until AFTER he sees the left switch in the down position. So if the left switch is up, he flips it down and starts his count the next time he sees it up. If the left switch is down the first time the counter gets there, he leaves it down and starts his count the next time he sees it up. So if someone is there before him, that trip doesn't get counted, which is why everyone has to visit twice to be sure they are counted. So in your example, "A" flips the switch down and his count=0 until he returns and sees it up.

doormat

[Copernicus]

Whatever the correct solution is, you can be sure that the Microsoft Engineer in the prisoner group will be about to release Solution 5.125 when they are all killed because of a bug in Solution 5.1.

[cepstrum]

hi gus -

you didn't miss anything; my solution does indeed fail to guarantee success for exactly the reason you mention. i missed this case perhaps because of my method: i first convinced myself that this was the correct answer, and then wrote a simple program to test it. after a few thousand trials, it guessed correctly every time.

this is certainly because, if the prisoner draw is random and uniform, the probability of the sequence you cite coming up is very small - (n choose 2) * (1/n)^7, where n is the number of prisoners. with 7 prisoners, this is 1.2x10^-6 for each of 21 pairs, or 2.52x10^-5. furthermore, when this does happen, it will almost never affect the game in a material way. this is because it takes so many trips to observe the required excess of odd visits - for 7 prisoners, i observed that typical games required 30+ visits for each prisoner before the guessing conditions were met. so even if the observed count is off for any one prisoner, _and_ he is the prisoner who actually guesses (p=1/n), his guess will almost certainly be correct despite the obvious flaw in my method. the failure rate is very small, but it is non-zero.

if the assumption that the prisoner draw is random and uniform does not hold, we may have a problem. we have an even bigger problem if our strategy is public and the guards are trying to make us lose. if this is the case, this "solution" will end in certain death.

cepstrum