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.