# Puzzler: Prisoners and the light switches

#1

The solution given was incorrect. Ray clearly stated that the warden might choose the same prisoner multiple times. Therefore the warden could choose prisoner 2, say, 42 times and the leader only twice. The solution given only works if the warden brings each prisoner in only once until all 23 have visited the room, then repeats the process.

#2

You’re forgetting that if the warden chose prisoner #2 all those times in a row, he would only have flipped switch A on twice (per instructions). After this he would have just toggled switch B. The prisoner doing the counting would only have counted to 2 by this time, awaiting more switch A “ons”.

#3

Tom and Ray were very perky stating that this could be solved by a over average 6 grade student

Imagine that the warden is a bastard knowing the puzzler. He will then, from time to time feed (…) one of the inmates to the allegators anyway. He is a dobuble bastard, because he will not feed the counter. The only one who knows that the amount of inmates has reduced - is the warden! The others are still in hope, and at one day the counter says “done”. He will then get confused because he counted right but has to follow the other remaining inmates to the allegators dinner, not knowing what went wrong. The warden will restart the puzzler with the next bunch of inmates coming in. This solution is a kind of gladiators game with no winners but the warden.

Mathematically spoken, the prevented solution counts switch moves but does not uniqeally assign a move to an inmate, which is mandatory not to end up with the allegators.

#4

As long as there is no limit to the number of total visits, and each prisoner has a finite probability of being chosen each time, then I think Ray’s solution works. (There’s another thread posted here about some ambiguity in the language that could prevent a solution, but let’s ignore that.)

Ray’s solution doesn’t imply how many visits this may all take. If each prisoner visits 1000 times between the “counter” visits, it could take a long time. Each time the counter takes a count, he can only count 1 visit, even if there were actually 1000 visits. But eventually the counter would reach 46 and know for certain everyone had visited at least once. (It’s 46 rather than 23, b/c the counter must initially reset the counting switch to a known configuration.)

It’s an interesting puzzler for sure. One thing that hasn’t yet been addressed is whether Ray’s solution is the “optimal” solution – in the sense of determining when everyone has visited in the fewest number of total visits. With Ray’s solution everyone will get out, but there may be a way for everyone to get out sooner. One must wonder if there is a better method, maybe using the second switch to count with too, or having more than one counter-person, or is in fact Ray’s solution the best possible?

#5

But George, how does it work with an infinite # of visits? Surely each visit cannot be done in less than a few seconds. With a base limit on necessary time per visit, but no upward limit on number of visits, the prisoner’s risk becomes untenable. It becomes a better choice to not take up the challenge at all.

#6

and, hey, let’s not ignore that other thread which brought the problem to light in the first place…

I think we’ve nailed this puzzler to the Bogosity Hall of Shame! right here… http://community.cartalk.com/discussion/2297001/puzzler-bogosity/p1

#7

#8

A few points:

The puzzler states:
“But, given enough time, everyone will eventually visit the switch room as many times as everyone else.”

So that precludes allowing the warden to feed the alligators.

However, the given solution does rely on the prisoners being more reliable that one would generally want to bet their life on.

I take the statement that the warden chooses “randomly”, along with the “eventually the same” comment above as their folksy way of saying the prisoners are chosen from a uniform distribution; that is: the warden rolls a D-23 and picks that prisoner.

The given solution is “conservative”, the prisoners will not falsely declare and therefore be fed to the alligators. But it is a ‘brittle’ algorithm; while fine in a computer, maybe not so good for a prison… If a prisoner muffs and flips the wrong switch, or otherwise decides to not follow the given instruction, then bad things happen.

Also, the bit about “take the long view” is serious. For the given solution, the prisoners can expect to be in prison until the warden has them to flip the switches over 1500 times!
If the warden chooses only once per week, that would take ~30 years!
Never mind the alligators, they will be dying of old age (or boredom)
[Note: generally, everyone will have visited the switches after about 150 flips;
so the prisoner are staying in prison 10 times longer that necessary]

A more reasonable and more stable solution is to rely on statistics:
The probability that any one prisoner could be called 15 times when each of the other prisoners has not been called at least once is very small (~1%);
At 18 times, the probability is maybe ~0.2%; and at 20, the risk is way, way less than the probability of dying in prison of other causes.

So I would suggest a simpler solution: when any prisoner has been to the switch room 20 times, that prisoner declares “we’ve all been to the switch room”!

This works, and gets them out of prison is about 1/4 or 1/5 of the time for the given solution,
and is robust in the case of prisoners dying before they can flip the switch the requisite 2 times!
(especially consider the case where the designated ‘counter’ dies)

ps, yes: I wrote program to simulate this and confirm the stats.

#9

@insightful, wow, how did you establish my analysis was bogus? I don’t see that anywhere.

GoldEye, there’s no way prisoners can plan for the Warden’s choices based on statistical probability projections. Also, what if each prisoner has visited 6 times (not enough times for Ray’s answer to work out). Might the alligators still get fed?

#10

Let’s go back to the Puzzler itself. We’re given a quirky real-life situation set in a prison, and told to figure out how to free the prisoners early without risking loss of life. So, how do we (1) ELIMINATE the chance of the alligators getting a banquet, and (2) free all the prisoners before release or natural death has occurred?

Ray’s solution was, choose a Counter who will visit the room 44 times to find that ALL other prisoners have been there at least once.

Does anyone still think this answer is not bogus?

#11

Tom and Ray’s answer is 100% correct, and GoldEye has a more practical answer (if the prisoners had knowledge of his analysis).

#12

wow… ok, statement without proof must be OK. best wishes to you, unsightly.

#13

wow… ok, such a way with words.

#14

I think this is a simpler solution. I’d appreciate it if anyone could either show me why it’s not a solution or confirm that in their opinion it is.

Non-counters put or leave the designated switch ON upon leaving on their first trip and OFF every subsequent trip.

The counter leaves it OFF when leaving every trip.

Starting on his second trip, the counter counts the number of times he finds ON upon entering. When the count reaches 22 he declares a win. (22 + 1 = 23)

Explanation: If he finds an ON on his second trip he know someone else has been there because he left it OFF. (On his first trip, he could be the first person admitted to the room.)

Whenever he goes in again and finds and ON, he knows it’s the result of an additional person’s first trip because he knows he left it OFF the last time he was there.

My personal email: pauldeykay AT the-well-known-google-email.com

#15

hmm … It’s interesting whether Ray’s solution is the optimum solution or not. I think the jury is still out on that. What about the solution proposed above? Well, here’s the problem I think. For a solution to work, each prisoner must eventually be counted. In the solution above, a prisoner might never be counted as having visited, even if they had. For example, if a prisoner hadn’t yet been counted, then made two visits occurring between a pair of counter visits, he’d turn the light on, then off, and never be counted then, or in the future.

#16

Paul Kay,
Not clear what you are proposing. When you say the non-counters “leave the switch … OFF every subsequent trip” does that mean they take action to turn it OFF?
If so, then they would [potentially] be erasing any other prisoners “first time switch it ON”.

So I assume you mean the non-counting prisoners turn the switch ON exactly once each.
If the switch is ON, they leave it ON, if the switch is OFF they turn it ON only once?

The counter, as you suggest, sets the switch to OFF every time, and starts counting…
The problem is that if the switch is originally OFF, and the first [non-counting] prisoner turns it ON (consuming his “one-time turn ON”) then the counter cannot detect that; the counter cannot discriminate that situation from the switch being originally ON. So if the counter chooses to not count the first time he finds the switch ON, then he will never reach the total of 22 (since that first prisoner will never again turn the switch ON).

SBM,
Interesting that you say without proof or even justification: "there’s no way prisoners can plan for the Warden’s choices based on statistical probability projections. "
and then explain/complain with sarcasm: “statement without proof must be OK”.

Given that Tom & Ray’s solution/algorithm demonstrably works, it is obvious that any analysis that insists that it doesn’t work is somehow flawed.

If there is still concern that either the given solution or the statistical solution will or will not “work”, then write the simulation program: that constitutes clear evidence. (I would also suggest doing the math to actually “prove” that the [counting] algorithm works, but it seems a stretch to expect the trolls to handle formal logic at that level)
But it goes like this: for the counter turn the switch off 2N times, it must have been turned ON by the prisoners 2N times or if the switch was originally ON, then 2N - 1 times. If some/one prisoner has not been to the room, then the most flips the other (N-1) prisoners could do is 2(N-1) which is 2N - 2; which even with the switch originally ON, would only come to 2N - 1 presentations of the switch being ON for the counter; so therefore the counter will not claim until each prisoner has been to the room, and flipped the switch at least once. In fact, most of the prisoners will have been to the room twice. So, assuming the prisoners eventually get to the room, and the counter eventually gets to the room afterward, then it works.

You can quibble about Tom & Ray’s explanation of the solution, but the solution is mathematically sound. Some of us quibble that a prison is not a mathematical abstraction, and prisoners are not reliable computational elements, so the plan may not work in a real prison…

Going back to “there’s no way prisoners can plan for the Warden’s choices based on statistical probability projections.”: the puzzler clears states (twice) that the Warden will choose “randomly”.
[and given the laymen’s vernacular, and the assurance that each prisoner is eventually chosen as many times as the others, we can make a strong inference that the “random” refers to a uniform distribution. (I doubt that T & R or any 6th grader would know any alternative for “random”)]

So yes, I believe the prisoners can rely on the law of large numbers.
In fact, each or any prisoner can derive and implement the statistical strategy independently.
That is: any one of them can, at any time, realize that if they personally have been to the room 20+ times, then there is good reason to ask the warden for release.

#17

@StormyBlueMerc‌
The statement of the puzzler leaves out an essential bit, that the rest of us are assuming:
The warden will continue to play the game (selecting prisoners at random to flip a switch) for as long as the prisoners are in prison.

We assert that the warden will not stop calling prisoners when they have each visited as few as 6 times.

Mostly, this is implied by the nature of the puzzler, and hinted at by “from time to time I will…” and the hint “take a long view”, and especially the promise “After today…” where we take “after” to be unbounded. You are correct, it is not stated, and should have been; but as you note, the puzzler would not be solvable if that were not somehow given or implied.

Also, although the puzzler states that the prisoners “will have no communication with one another”, it does not preclude the prisoners talking with the guards! So another solution is to influence the guards to help, and thereby escape even sooner. But that is perhaps the point of the original ‘clue’ that this was making the rounds of mathematicians: we should interpret it with the usual caveats and assumptions of math puzzle abstractions.

#18

Brilliant puzzle. I didn’t get it (the first time) because I didn’t realize that the prisoners didn’t HAVE to stop the game as soon as the conditions were met. I thought the guy who completed the circuit had to identify it and stop the game. I probably wouldn’t have gotten it anyway.

Paul Kay if every non-counter comes in before the counter and leaves the switch “on”, then the counter comes in and turns it off. So when the non-counters come back, they won’t put it in the “on” position so the counter won’t count anyone.

The key is that, yes, the counter has to come in 44 different times for the 22 co-prisoners (with each turning it on twice). So it would take a long time. If he takes prisoners in twice a week it’d still take years.

#19

Hey Goldeye, excellent spotting on the assumptions. Now you’re not really going to bring the guards into the mix OMG! ;-D This was a great puzzle for conversation, though!

#20

Thanks to GeorgeSanJose, GoldEye, and kenberthiaume for finding three different flaws (!) in my proposed “simpler solution”. Good to have closure, if embarrassing.