Click and Claps, the famed Tapit brothers of the PBS program CarTalk, have put forth a real brain twister of a puzzle.
So far no luck with me, I'm still trying, but my ideas are getting more and more farfetched. 
Here is the puzzle...New Puzzler: Prison Switch ScenarioRAY:
I got this from my pal, Stan Zdonik, who teaches at Brown University. It was given to him by a colleague who failed to provide him with the answer -- maybe because he didn't know it?
This puzzle has been making the rounds of Hungarian mathematicians' parties. Here it is... The 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."
What strategy should the prisoners devise? 
Since the prisoners will have not chance to communicate, their only safe strategy is to
agree never to say all have been to switch room. They will never get free, but they will
never get fed to the alligators.
Maybe they could all visit the switch room before they are quarantined and then he will have to let them go.
However, there is a rider to that, the warden says, "If this is true"; how on earth is he going to confirm that?
In reality, I think there is no hope. For, whatever strategy they plan, the prisoner picker is the warden and he could go on picking the same guy, or the same ten or the same twenty two, but never ever twenty three.
methinks, the puzzle itself evadeth me!
The warden could easily keep records to know when every prisoner had been to switch room.
The prisoners could not.
i think that the solution is somehow dependent that there is an uneven number of them they should agree on an initial position of the switches, which the 1st prisoner will make, say A and B switched off. discovering this position, the next prisoner changes this to A and B are on. if anybody visits the switch room second, third etc time, he doesn't touch anything... or even more complicated plan
A B
1. off off
2. on off
3. off on
.....
don't ask me will it work or not. this is the end of the day. i am capable of inventing an insane plane but not seeing its consequences
Dear vika: I'm not good at games, but I see no way the prisoners could know initial position,
nor communicate status of switches to others. The warden could send same guy 23 times
and the others would never know.
vika, such a scheme is not doable: 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.
ok, this just came to me:
if they agree to only flip the left switch, for example, until someone goes for the second time; then he flips the other switch. they continue to swith that switch until a second person goes twice. then he goes back to flipping the first switch. etc.… they could count the number of times they have reversed. when they get to 23, they would know that they all have gone once.
have I missed something?
I feel like I'm being led down a primrose path by the creator of this puzzle, but the careful wording below seems critical, but cryptic, wording to me...
"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'. "This seems to indicate that the total number of visits (or switches thrown) would have to be either 23, or a multiple of 23, that is, 46, 92, 184, etc. All even numbers, naturally, except 23.
Now say, for example, if the prisoners could distinguish between the two switches beforehand
* and assign beforehand a separate meaning for the switch position of each...eh??? (odd/even)
Well, you see what I'm getting at.
And if you do will you please post it, because I sure as heck don't.
* (Post Edit: Of course they can, Milo-you-big-dummy, they are labeled A and B!) 
Second Post Edit: Etaoin, how is the counting known to the isolated prisoners? But if, let's say, that if eleven prisoners have pre-agreed to always switch the A switch and the other twelve have agreed to switch the B ???
And remember the prisoners are selected at random (or whim, if you perfer,) and then their name, so to speak, goes back into the hat, which is the crux of the quiz: Randomness tamed by order.
I'm not sure the problem has a solution as stated. It contains internal inconsistencies.
--I will select one prisoner at random...
--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...
--given enough time, everyone will eventually visit the switch room as many times as everyone else...
If he is picking, and can elect not to choose prisoner X ever, it isn't random. And if the problem is inconsistent in its presentation, can it still have a logical answer?
I thought of it might involving odd/even parity, but if any one can visit the room multiple times that won't work...
Can our collective self-esteem wait a week for the answer?
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
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...
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...
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!"
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
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.
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.
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
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. (
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.
For those, like my own sef, who want to hear the probably bogus answer
in loco[sic], here's the web site where you can find if and at what time on the weekend your local NPR affiliate carries the show. The answer will also be posted on the site and furriners can also hear it in a variety of ways:
http://cartalk.cars.com/show/
I guess I'm a little curious what a theoretical computer science problem has to do with cars.
k
You've obviously never heard the program, FF. I don't know from cars, don't care about them, but I wouldn't miss this weekly show unless I absolutely had to! Please give it a try; it's hilarious. Cars are just the excuse, or the casus radii, if you will.
They will occasionally have a Puzzlah, that's explicitly automotive (or at least quasi-automotive) just to keep some semblance of propriety.
Check what Ænigma did with quasi-automotive. And we thought she was dumb.
If you have any questions about Car Talk just write their lawyers at the firm Dewey, Cheatham and Howe.
Well, all I heard back from my bro to whom I sent this puzzle, was that he would try to work on it when he had some time, and a suggestion: i would try to solve the problem for the case of 3 prisoners and then see if it is possible to extend or modify the method for larger numbers.
But but but....With only three prisoners, it's easy, is it not? The three agree among them which one will use the B switch - only one of them - and then the other two use the A switch.
Say I am the prisoner who gets to use the B switch. I go into the room. Both switches are up. I put B down. Okay, this ain't gonna work either, ais it?
Damn! Damn!
Near as we can tell, we have another week to puzzle this one out. We heard little bits and pieces of the weekly broadcast from one of our available NPR stations (the one that is entirely funded by the host college) and it would appear that either no one has come up with an answer or they were intending a two week puzzle in the first place. Our standard NPR station is in the throes of fund drive and was running an old show that was fine-tuned for money raising. They didn't even touch the Puzzlah. We have to wait till Monday before it shows up on the web site. One thing we did catch was that Ray suggested solving for three prisoners (let's hear it for mg's bro). Tommy mentioned that this puzzle had been given to some MIT engineering types and they wasted a bunch of time figuring that the fact that 23 is prime had something to do with it.
What if the 23 prisoners were to agree to ask the question once a year, drawing straws to determine the asking order? They might lose a few to the alligators, but eventually the rest would be freed.
What if the 23 prisoners were to agree to ask the question once a year
The way I interpret the problem, if the first prisoner says, "We've all been here," and is wrong then they all get fed to the gators. That's "what if" the way I interpret it.
I am told you can go to tsuwm's link and get the problem; you have to click on another link within that link to get the answer.
Maybe I'm dense, but the strategy offered by the site tsuwm posted seems without logic. I'll read it carefully again but in the meantime I'd like to post a strategy that is in a large part based on delimiting comments made by contributors to this thread. As given below...After much hand wringing and gnashing of teeth the prisoners finally realized that their fate was left to the less than exacting craft of Probability Math. And since fractioning a .9999999 likelihood will never reach a certainty of 1, they sighed and voted on what percentage of chance that they would collectively accept against the unpleasant act of being eaten alive and torn limb from limb by prison alligators.
But prison itself wasn't much of lark either so they found a point of convergence that would spring them from jail at the earliest time, while at the same time giving them a 98 per cent chance of not being thrown to the gators. The trigger is the number of trips to the switch room by the most frequent prisoner, the math works out something like this...
The odds of all prisoners being selected at random on the first round of 23 are against selection at about a trillion or so to one.
But surprisingly only 92 random trips to the switch room gives a 94 percent likelihood that everyone has visited the switch room at least once.
As well, after 92 random visits to switch room the chance of one prisoner haven visited the switch room four times was 88 percent likely. But our understandably nervous prisoners weren't much at close gambling, so here is the plan they devised...
The first prisoner to visit the switch room was to leave the switch room with switch (A) in the DOWN position by either pulling it down or leaving it and pulling switch (B). All prisoners were afterwards to pull switch (B) only. Except for the first prisoner to visit the switch room for the fifth time. (This maths out to a 98 percent likelihood that all prisoners have visited the switch room.) Then he is to say to the warden
"EVERYONE HAS VISITED THE SWITCH ROOM" and then throw switch (A) to the UP position.
Why does the prisoner throw the switch to UP after just haven been saved from death by alligators? Well that's a prisoners way of saying...
"UP YOURS WARDEN!".
In reply to:
"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."
The warden made a point to include all in the freeing but said only you when refering to the alligators. [shrug-e]
f 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."
The warden was talking to all of them when he said that.
The warden meets with 23 new prisoners when they arrive.
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." ~
picky consueloThe warden was talking to all of them when he said that. ~
faldageConsuelo, mam. That's why we of the south have the human decency to say "you all". I deduce that the hated warden was a cruel northerner lacking in even the most elementary language training.
have the human decency to say "you all"
Which would be all well and good if y'all'd limit it to the plural, of which I've heard it in the singular, too. Mo better we shutn't a gone away from thee/thou. (And folks complain about they in the singular. At least it retains the nominative vs. accusative/dative distinction stead a using only the accusative/dative)
Milo's answer has a sweet reason to it....I vote for it.
My bro couldn't come up with anything, except the probability factor (without Milum's added touch of leaving the A switch in the UP position until one prisoner made his fifth visit to the room).
Is there really a semantics problem with you/you all? No one prisoner is going to want to speak out and find himself the only one thrown to the 'gators; but none but the hardendest of criminals (which they all might be, granted!) would want to proclaim a death sentence on everyone, himself included, either. Yes?
Oops! 
I think I had better wait until my know-it-all physicist buddy gets back in town wednesday to check my figuring before I post the supportive math to my solution to the prison puzzle here on Awad and before forwarding it on to the Tapit Bros.
Either these folk's
http://randomizer.org research randomizer generator atoms aren't decaying properly, or I have made a slight mistake in my calculations.
Whew! That was close. Twenty-three prisoners thrown to gators because of a misplaced digit. Or two.
The good news is that the low-life, scum-of-the-earth, prisoners might have to stay in jail a tad longer than I originally thought.
the supportive math
Why settle for a solution that has a finite chance of failing when you can have one that will succeed every time?
Why settle for a solution that has a finite chance of failing when you can have one that will succeed every time?
I'm with you. Any bright ideas?
what's wrong with this picture then, milum?
http://www.sucs.org/~crystal/solution.php
what's wrong with this picture then...http://www.sucs.org/~crystal/solution.phpAs this particular version is worded, N prisoners will eventually visit the room N times each, which is all well and good, except that freedom is not claimed until ~2N visits.
In the *original version, no N-visit constraints are imposed. Nonetheless, on average, each prisoner will visit the switch room once per successful spokesman 'count'. (This assumption uses a linear model to predict successful non-spokesman visits, which in reality will be exponential, thus greatly increasing the figures used herein.) Thus, 23x44 = 1012 visits are required - a mere 2 years, 282 days, assuming daily visits. However, "from time to time" imples, to me, a maximum of weekly visits, and significant periods of non-visitage. Thus 19 years, 144 days (assuming 5 leap years) will elapse, on average, before freedom is to be claimed. Any solution which relies on the ability of all 23 prisoners to maintain their sanity over 2 years in isolation, let alone 19 years, must surely be doomed to failure, regardless of the mathematical correctness. The prisoners would do much better simply rushing the warden and guards there and then - the only time they will all be together.
*sigh* It never worked with my Dad, either. He'd always get bug-eyed and yell "You know what I mean." Mom and I would usually chew it over for awhile though.