Prisoner teamwork

[Bert Bates]

Ok, I'm telling you all right up front that I don't know the answer to this one, so no name calling later on... This puzzle has been haunting me for months now, so if you need for me to have the answer just back away now... and there will be no hard feelings...

Some big number of prisoners (I think I remember it being 21 but I might be off by a few, my guess is any big number will do, so for instance if you can do it with 17 you would still get tons of accolades), are given this challenge...
The warden brings ~21 prisoners into a room. The room has two, two way switches. The warden explains the following:
Every once in a while I will bring one of you into this room. When you arrive, you MUST flip exactly one of these two-way switches.
You will have no contact with each other once this meeting is over.
I will let you meet now, and devise a plan.
When any of you are brought into the room, and you can tell for sure that you have ALL visited the room at least once, tell me.
If you are correct, I will set you all free! If you are wrong, the challenge is over, and you will all serve your full terms.

What plan could the prisoners devise to communicate with each other, via the two switch settings, so that they could tell when they had ALL visited the room?
p.s. I heard this on Car Talk's weekly puzzle segment
[ August 15, 2003: Message edited by: Bert Bates ]
[ August 15, 2003: Message edited by: Bert Bates ]

[Jessica Sant]

damn you bert... I've got work to do and now I'm trying to think about prisoners and light switches....
My first thought was to count sequentially with the lights...
Before the first guy goes in -- both switches are OFF (00).
01 - after guy 1 leaves.
11 - after guy 2 leaves.
10 - after guy 3 leaves.
00 - after guy 4 leaves.
SO, up to this point all these guys can tell how many have been in before them. If we continue in the same pattern:
01 - after guy 5 leaves.
11 - after guy 6 leaves.
10 - after guy 7 leaves.
00 - after guy 8 leaves.
But all guy # 8 knows for sure is that 3 people came in before him... he can't be sure that guys 1-4 were there... so -- the quesiton is, how do you count to 17 or 21 or something with only 2 bits?
What if... you can balance the switch in the middle position between on and off... then you can have base 3 #s
01 - after guy 1 leaves.
02 - after guy 2 leaves.
12 - after guy 3 leaves.
11 - after guy 4 leaves.
10 - after guy 5 leaves.
20 - after guy 6 leaves.
21 - after guy 7 leaves.
22 - after guy 8 leaves.
.... but then you can't get back to 00 without having one guy flip two switches or without jumping directly into the middle of the sequence. Either way you're still in the same situation where the guys won't know if 8 people have been in before them or 1.
blah

[Jessica Sant]

OK -- after a little searchng -- here's the actual problem according to CarTalk's website (doen't make it any easier though...):

A warden meets with 23 new prisoners when they arrive. He tells them, "You may meet today and plan a strategy. But after today, you will be in isolated cells and will have no communication with one another.
"In the prison is a switch room, which contains two light switches labeled A and B, each of which can be in either the 'On' or the 'Off' position. I am not telling you their present positions. The switches are not connected to anything.

"After today, from time to time whenever I feel so inclined, I will select one prisoner at random and escort him to the switch room. This prisoner will select one of the two switches and reverse its position. He must move one, but only one of the switches. He can't move both but he can't move none, either. Then he'll be led back to his cell.
"No one else will enter the switch room until I lead the next prisoner there, and he'll be instructed to do the same thing. I'm going to choose prisoners at random. I may choose the same guy three times in a row, or I may jump around and come back.
"But, given enough time, everyone will eventually visit the switch room as many times as everyone else. At any time anyone of you may declare to me, 'We have all visited the switch room.'
"If it is true, then you will all be set free. If it is false, and somebody has not yet visited the switch room, you will be fed to the alligators."
Here's the question:
What is the strategy the prisoners devise?

[Bert Bates]

Jess -
Apart from the alligators, and 23 vs. 21 prisoners, does your version have any logical differences?

[Roy Tock]

A little googling...and voila! This is no fun...but it's been haunting you. You don't have to peek
the answer

[Bert Bates]

I didn't peek, and I'm happy to know that there IS an answer, now I can get back to being haunted...

[Jessica Sant]

Well, the fact that a prisoner can and probably will be taken into the room more than once is key. Also this line is important too: "But, given enough time, everyone will eventually visit the switch room as many times as everyone else."
And let me just say that my attempt at an answer was totally off -- I peaked at the answer from the page I cut& paster the problem from. I would never have come up with their answer... but at least now I can get back to this dang fake requirements document for school.
[ August 15, 2003: Message edited by: Jessica Sant ]

[Greg Harris]

i think the fact that there are 23 rather than 21 prisoners is important for some reason because 23 is 1 less than a multiple of 4 (24). of course, 21 is 1 greater than 20...

[Jim Yingst]

I confess, I was weak of will, and followed Roy's link. Cool puzzle.
Apart from the alligators, and 23 vs. 21 prisoners, does your version have any logical differences?
The version Jess found does state explicitly that the warden's prisoner selections are random, and that the initial state of the light switches in unknown. Both are potentially useful bits of info to have confirmed. To ensure eventual success, I would want assurance that the room visits will continue indefintely. Otherwise the warden can just stop when he feels like it, and screw everyone. Jess' version does guarantee "given enough time, everyone will eventually visit the switch room as many times as everyone else" - but that's a bit too vague for my taste. For simplicity, just assume there will be one visit per day, unto eternity, and each visitor will be selected at random, and no prisoners will ever die. (Or if there's any death, the warden will inform the other prisoners of it.)

[Jessica Sant]

Originally posted by Greg Harris:
i think the fact that there are 23 rather than 21 prisoners is important for some reason because 23 is 1 less than a multiple of 4 (24). of course, 21 is 1 greater than 20...

you'd think that 'cause 23 is prime, that might mean something too -- but nope, the solution given can work for any number of prisoners (given enough time as Jim said)

[Mark Herschberg]

When the last prisoner completes his term and is about to be set free, you can declare that everyone has visited the room, since by then, everone else would've had to or else the warden's claim of everyone visiting it would not be true.
--Mark

[Mark Herschberg]

Some thoughts on a better solution... Now I'm assuming there's no trick (e.g. they all write their name of the wall when they come in there).
You start with 0 bits of information about the state of the room, i.e. there are two unknown, random bits. Each prisoner effectively ANDs one bit with one of the two random bits. This makes it hard to send information through the switch states.
Also since each person must flip a bit each time, and since any person may apprear N times (N >= 1) we cannot assume each person represents a bit in some master code.
--Mark
[ August 15, 2003: Message edited by: Mark Herschberg ]