One more good puzzle

[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