|
Joined: Jun 2002
Posts: 1,624
Pooh-Bah
|
Pooh-Bah
Joined: Jun 2002
Posts: 1,624 |
No, the drunken doctor is quite right. There is no way of calculating when all prisoners have been to the switch room; in fact the switching issue itself is neither here nor there because the act of switching adds no information for the other prisoners about who has done it or how many prisoners have been to the switchroom.
It's a guess, pure and simple.
- Pfranz
|
|
|
|
Joined: Sep 2001
Posts: 6,296
Carpal Tunnel
|
Carpal Tunnel
Joined: Sep 2001
Posts: 6,296 |
At this point, I agree with Wof' that there are so many inconsistencies built in that it seems impossible for the inmates to work it out beforehand.
...unless there is a fine syntactical clue embedded within the problem
Consider the use of the word equal again as put forth in the problem. There may be a clue there...
|
|
|
|
Joined: Jun 2002
Posts: 7,210
Carpal Tunnel
|
Carpal Tunnel
Joined: Jun 2002
Posts: 7,210 |
Etaoin, how is the counting known to the isolated prisoners?well, I asked if I had missed anything!  however, I'm going to go from this line: given enough timeif they each keep track of how many times the switches have been reversed(as per my first concept), then the first person to reach 23 can reliably say that they have all visited the switch room. I can't quite get this to jibe with the "as many times as everyone else" thang, but... then, I can't count to infinity either. or even to .9999...
formerly known as etaoin...
|
|
|
|
Joined: Dec 2000
Posts: 13,803
Carpal Tunnel
|
Carpal Tunnel
Joined: Dec 2000
Posts: 13,803 |
given enough time, everyone will eventually visit the switch room as many times as everyone else
I would say that this means that it will not necessarily be the case that everyone visit the room the same number of times. If the choice is truly random (say the warden computes the next prisoner from a random number table) then, given enough time, everyone will eventually visit the switch room as many times as everyone else. But if he gets everyone except #23 and has gotten #14 twice and they *have worked out a strategy (and knowing the Tappet brothers, they do have an answer that at least one of them thinks is not bogus) and the next one in is #23 then he wasn't given enough time.
From the wording it sounds like the warden can bring more than one prisoner in on a given day and can even pass several days without bringing in a prisoner so it looks like the prisoners can't even tell if the first one has gone in. This would mean that the warden could wait 30 days before bringing anyone in. The switches would then have a one in four chance of being in the orientation that they have agreed to be the sign that all 23 have been in and it's alligator lunch time.
I'd say the chances are good that, when we all tune in to hear the answer we will be greeted by the dulcet tones of Tommy saying, "Bo-o-o-o-o-o-o-gus!"
|
|
|
|
Joined: Jan 2002
Posts: 1,526
veteran
|
veteran
Joined: Jan 2002
Posts: 1,526 |
I think the problem wording is a little vague and that the attempts to help have hindered. The statement "random" in conjunction with "But, given enough time, everyone will eventually visit the switch room as many times as everyone else" means that the distribution is uniform (all equally likely). The statement that he "MIGHT" pick a single person three times in a row indicates that each selection is independent of the ones that went before. I think he was just trying to say this in a way that was not intimidating for his audience.
No time for solutions at the moment, but here are 3 paths.
1. Cheat. Each person has a location wrt the switch box and makes a small indentation with fingernail on his first visit, but never again. The first person to realize that all the positions have been ticked off, announces to the warden.
2. Probability. When a person is picked the first time, he doesn't know if he was the first person picked or not, but he knows, if the choices are independent, that the odds are pretty rare that he would be picked 10 times in a row. Chances are also slim that there were 11 picks or 12 picks or even 20 picks. Blah blah blah. The source distribution is uniform, but the CLT (central limit theorem) says that any distribution will approach a normal distribution in the limit. Let success = I get picked. Let M = # times I am picked. Let N = total number of picks (which I do not know); however, I can compute the binomial for it (in my copious time in my cell). Blah blah blah ... handwaving ... fake out ... mental laziness ... miscellaneous BS ... eventually you realize that once you go, say, 20 times, that the chances that someone is left who has not yet gone are pretty small. Without doing the math (which is not hard, but I'd have to think about it), we could just guess and say 20 ... if I get in this room 20 times then the chances that there is someone who has not gotten in the room are negligible.
3. Again, no solution. Just a path. Some observations.
The states are 00, 01, 10, 11. Label them A, B, D, C, with each state representing two bits of information.
A state diagram shows how the state CAN change, but I can't figure how to draw one in here. A connects to B connects to C connects to D connects back to A. Draw lines that connect each of them in each direction. An outer ring of lines going clockwise and an inner ring of lines going counter-clockwise.
Each person knows whether he has visited the room, but needs to know the state of the other 22. This means he needs to know 22 bits of information WHEN the 22 bits are all on. Since the states can only represent two bits, we realize the states alone do not represent sufficient info.
However, each individual knows not just the current state, but all the previous states he has seen. Each observation is two bits. He needs to know 22 bits of information; therefore, there is an absolute minimum of 11 visits anyone can make to be certain of the other states (assuming it's possible, which we're not sure of at this point).
We can imagine that each individual is a turing machine. He has a tape which is a memory of what he has seen in the room. (It's not clear at the moment whether it's better to think of this as a two tape or three tape machine, but of course they are equally powerful. We just choose whichever is easier.) So each prisoner is a turing machine. He looks at the current letter on the tape AND all of the past letters and determines what the next letter is that he should write on the tape. The question is this: Is there a program for this TM (turing machine) that can answer this question.
Well, I've gotta go right now. That's as far as I've gotten in a few minutes. No idea these idea will be fruitful or dead-ends, but so far I'm inclined to cheat even if we are able to find a solution by some other means.
k
|
|
|
|
Joined: Sep 2001
Posts: 6,296
Carpal Tunnel
|
Carpal Tunnel
Joined: Sep 2001
Posts: 6,296 |
All of this interpreting is complicated, but take a look at this sentence and read it for what it is:
"But, given enough time, everyone will eventually visit the switch room as many times as everyone else.
1. We've commented here on "given enough time" 2. But everyone will visit the switch room as many times as everyone else? 3. That could take a helluva long time. The warden could save the last guy for last. He could let the others visit the switch room countless times, knowing full well that he's saving the last guy for the final count. Say, let the others each visit it three, four, even five times or more before introducing the last guy whom he fully intends to let visit the switch room many times in a row to reach his own 'equality' of number of visits. [Hang in here with me; I'm about to make a point.] 4. The catch is: At what point would the prisoners know the last guy (if that's the warden's plan) had gone his first time thereby being able to say all had visited, but not necessarily the equal number of times. Equality of visits was never a consideration, but multiple visits was.
I like the fingernail scratch idea someone proposed up there. I don't think the problem could be worked out mathematically given the fact that the warden could juggle around visits in any dadburned way he wanted to, always leaving at least one guy behind.
|
|
|
|
Joined: Jan 2001
Posts: 13,858
Carpal Tunnel
|
Carpal Tunnel
Joined: Jan 2001
Posts: 13,858 |
The switches would have to be ten feet long and made of cheese for fingernail to mark them. Even if guards watching to prevent double switching did no snitching.
|
|
|
|
Joined: Dec 2002
Posts: 555
addict
|
addict
Joined: Dec 2002
Posts: 555 |
you will be fed to the alligators.
Wondered earlier on, if there was some difference between crocs and alligators that might have saved the prisoners. No such luck, but in the process learnt a little more about these awesome creatures. Here's a link for anyone who might be interested:
http://www.aquariums.state.nc.us/ata/croc.htm
|
|
|
|
Joined: Jan 2001
Posts: 13,858
Carpal Tunnel
|
Carpal Tunnel
Joined: Jan 2001
Posts: 13,858 |
I think I have read somewhere that crocodiles may grow to be far larger than alligators, and so more easily able to kill a swimmer. I have also read that they roll over very powerfully, so that prey gets battered against the bottom of the water.
From the Internet: The most believable record-holder for the longest saltwater crocodile was a massive adult male killed on the Fly River in Papua New Guinea in 1982. The animal had already been skinned when a visiting zoologist measured it at 20.3 feet (6.2 meters), and because we know skins shrink slightly it's likely the animal was nearly 21 feet long. It would have weighed between 1 and 1.5 tons!
Here's figure for alligator. Not as much difference as I thought.
5. What's the biggest alligator in the Park? No one really knows for sure. There are some that measure 15 to 16 feet in length that live here. (
|
|
|
|
Joined: Feb 2002
Posts: 833
old hand
|
old hand
Joined: Feb 2002
Posts: 833 |
This is hurting my brain. I keep thinking of things and then realising they wouldn't work....
Everybody who goes to the room, flips the A switch the first time he goes, and the B switch ever after, all the while noting the position of both switches on entering the room? until the switches have changed position enough times?
Let's see:
Say I go into the room for what is my first time. I know the plan is that I am to switch A this time, and B any subsequent time I visit the room. When I arrive, A is up and B is down. I switch A down.
Some time elapses. I return to the room. I notice that A is up again and B is also up. From this I deduce that someone new has visited the room, and someone who has returned at least once.
I reckon each prisoner has to adhere to this method until he's visited the room a minimum of 23 times - possibly more....Say the next time I return to the room, A is still up, and B has also returned to the up position (because I put it down the time I visited before, right?). That means either no one new has visited, or two new people have visited; but it certainly means that someone has returned in the interim.
By my 23rd visit, if switch A appears never to have moved - according to what I see, and only what I see - then it is possible that everyone has visited the room. However, if....
Bah, humbug. I can't do it. What on earth plan could they devise? They can't decide that only the last guy to go can switch the B switch and all the rest will use the A - how can they know who's going to be the last guy?!
But given that there are 23 of them, methinks it must be a numbers game....Perhaps it could be something pivotal: 11 of them will only use the A switch, 11 will only use the B switch, but the 23rd person may use either....Nah, how would that work? he still wouldn't know, whichever switch he decided to use, how many had gone before him on either switch, or how many times each had gone.
I'm going to stop thinking a-write here, and go to bed so I can lose sleep over this.
|
|
|
Forums16
Topics13,913
Posts229,810
Members9,187
|
Most Online3,341 Dec 9th, 2011
|
|
0 members (),
458
guests, and
1
robot. |
Key:
Admin,
Global Mod,
Mod
|
|
|
|