There are 100 jailed prisoners. They have absolutely no ability of contacting each other or the outside world - each one is held in a closed dungeon with 4 walls. The prison manager told the prisoners that every day he will conduct a random raffle, in which the order of the entrance to the yard is decided. The yard contains one lamp and one switch. If the prisoners will be able to determine, that beyond any shadow of doubt, everyone entered the yard - they will be released.
The yard is empty besides the objects I mentioned, it has 4 walls, the prisoners don't know when a day has passed, they can't mark the wall in any way, or touch the lamp.
It seems impossible. What is the answer?
EDIT: scroll a few posts down for a clearer version of the riddle.
[ July 22, 2006, 12:20 PM: Message edited by: Beanny ]
Posted by Mathematician (Member # 9586) on :
Do the prisoners know that there are 100 of them?
The manager holds a raffle to determine the order the prisoners go into the yard? Do the prisoners know this? Do they know it only effects the order and not the total number who leave?
Do they all march at once? Or are they released one a day? Or at random intervals?
Do prisoners get returned to their cells ever?
What does the switch do? Does it just turn the lamp on and off?
Posted by ssasse (Member # 9516) on :
*suspicious look
Is this a homework problem or any other assignment from some type of authority figure? 'Cause I don't want to have to go all Primal on you.
Posted by Bob_Scopatz (Member # 1227) on :
This is a "classic" logic problem. I'll let others provide the solution.
Posted by kojabu (Member # 8042) on :
Can they touch the switch?
Posted by Gwen (Member # 9551) on :
We're assuming that the prisoners all formulate a plan before going in, right? Because it wouldn't do any good to come up with a plan that would work if not everyone knows it. And I'm guessing there's absolutely no way to draw in the dirt, or bribe the guard, or anything like that. The Lamp Is All. I'll think about it. Too bad they can't touch the lamp!
Posted by dkw (Member # 3264) on :
You are missing some information from the usual way this problem is stated. Maybe this is a different version, but if not you should check your source and present it again.
Posted by Soara (Member # 6729) on :
I don't get it. What do you mean "the entrance to the yard"?
Posted by Hamson (Member # 7808) on :
"If the prisoners will be able to determine, that beyond any shadow of doubt, everyone entered the yard - they will be released."
Huh? That sentence doesn't make any sense. You use the future tense form of a word, and then later in the sentence change to past tense.
Posted by Dr Strangelove (Member # 8331) on :
I was slightly confused as well by the wording of that sentence, but I supposed that was just me not getting the riddle, which is nothing new.
Posted by ElJay (Member # 6358) on :
I was about to ask if there was information missing, because as given I can see several very simple ways for them to do it, and couldn't understand why it would be considered a puzzle.
Posted by Dagonee (Member # 5818) on :
1.) Do the prisoners go into the yard one at a time and remain there until all are in?
2.) Do the prisoners know how many prisoners are in the jail?
(Clearly, both can't be "yes" or this is trivial. But the solution is very different depending on which is true.)
3.) Can the prisoners flip the switch?
4.) Is this something to be repeated each day, or is it a one shot deal?
Posted by ElJay (Member # 6358) on :
I googled for the puzzle and found it here, if anyone would like to read a more detailed version of it. Answer not included. Reading the notes, it's not my kind of puzzle, so I will promptly spot thinking about it now. Posted by Soara (Member # 6729) on :
quote:Originally posted by ElJay: I googled for the puzzle and found it here, if anyone would like to read a more detailed version of it. Answer not included. Reading the notes, it's not my kind of puzzle, so I will promptly spot thinking about it now.
Thanks, that's alot clearer!
Posted by Beanny (Member # 7109) on :
By the way, this is not for homework, I just found the riddle and was interested to see what the Hatrackers could do.
So I can't answer questions either...
Posted by Krease (Member # 9536) on :
quote:Originally posted by ElJay: I googled for the puzzle and found it here, if anyone would like to read a more detailed version of it. Answer not included. Reading the notes, it's not my kind of puzzle, so I will promptly spot thinking about it now.
Hm - this link makes the puzzle a bit harder - coming up with a solution where they'd be released in under 4000 days (11 years) as opposed to the solution I know where the average would be 10000 days (27) years.
Posted by Teshi (Member # 5024) on :
I have a plan but not the mathematical ability to work out exactly how long it would take to be almost 100% sure.
In the one linked to, the prisoners seem to know how many days have passed. In this one, they don't. This is part (but not all) of my solution... which is the proper riddle?
EDIT: The one linked to does say the cells are windowless but are the watchless, clockless, etc., too? EDIT: Hm... my plan's not as good as I thought, but I'd still like to know whether the prisoners can count days or not.
Posted by Teshi (Member # 5024) on :
If the prisoners can count days, I have a method that could take statistically ages but would definately work. I won't put it here but I know for sure it would work.
I need to work on it to bring it down to a reasonable amount of time.
Posted by Krease (Member # 9536) on :
The prisoners cannot count days. Imagine that they're all in solitary confinement and are (on average due to the the riddle) taken out once every 100 days.
Posted by TomDavidson (Member # 124) on :
There's a possible solution which does not require the prisoners to count days and which guarantees 100% accuracy -- but which will take, on average, around 28 years.
That's the EASY solution. There are also some much harder solutions out there which can cut this time.
Posted by Dagonee (Member # 5818) on :
The immediate one that comes to mind is an O(n^100) solution, which will be guaranteed to work in 3.5 x 10^27 years.
I need to generalize it so that more than one person can play the key role, but it's too hard to do the math right now.
Posted by Enigmatic (Member # 7785) on :
quote: Before this whole procedure begins, the prisoners are allowed to get together in the courtyard to discuss a plan.
The solution is all in the planning, and much simpler than most of you seem to be making it out to be. The prisoners gather in the courtyard and form a big huddle to discuss the plan, speaking loudly and animatedly about logic, statistics, and mathematics. Whenever the warden asks them if they're ready to begin they answer "No, no, we've almost got this worked out perfectly" or "We just need to make sure everyone understands the plan, some of these guys are a little slow, you know." Meanwhile, the prisoners in the middle of the huddle are digging a tunnel out of there, because that's a lot more reliable than 100 convicts agreeing on and successfully implementing some complex statistical analysis without somebody just guessing and screwing it all up.
--Enigmatic
Posted by Krease (Member # 9536) on :
quote:Originally posted by Enigmatic: Meanwhile, the prisoners in the middle of the huddle are digging a tunnel out of there, because that's a lot more reliable than 100 convicts agreeing on and successfully implementing some complex statistical analysis without somebody just guessing and screwing it all up.
Remind me to become your buddy if we ever end up in prison together Posted by Glenn Arnold (Member # 3192) on :
This sounds like the binary counting thing that I've done with students. The students stand in a line, and hold hands. The rule is that everytime your left hand goes down, you switch the position of your right hand. The student on the left end begins by raising his left hand. Count 1.
Then the student on the left lowers his left hand, and raises his right hand (the 2's place). Count 2. The student raises his left hand so 1 and 2 are up. Count 3. Etc.
In this case, the light switch would be the first arm, and somehow the lightbulb communicates to the next person whether to raise their arm. The problem is that you don't have any independent observer who can actually keep count.
Posted by Teshi (Member # 5024) on :
Hm, not being able to count days makes throws a big wrench into my idea.
Posted by happymann (Member # 9559) on :
It is entirely possible that in one lifetime there could be a prisoner who never gets let out if the raffle is random every day and none of the prisoners are excluded. So there's no 100% possibility that all 100 will visit the yard, let alone find a way to communicate with one another. Given a few years (4 or 5) chances get pretty darn close to 100% in that if it hasn't happened by then, then it doesn't matter. I know I'd probably just go insane if I were in solitary that long.
So, I say, just wait to what kind of feels like 4 or 5 years and then have one of the prisoners claim they've all visited the yard.
Posted by Nighthawk (Member # 4176) on :
Pay off the guards to kill off all the prisoners. Problem solved on so many levels.
Posted by Glenn Arnold (Member # 3192) on :
Nighthawk: Assume the prisoners are innocent victims of an evil dictator. The whole arrangement seems pretty sadistic to start with, and the prisoners sure didn't come up with it.
Also: Kill one prisoner before he's been to the room and there's no solution.
Actually, (in reviewing my own post) the lightbulb is irrelevant, because no matter what happens, it's in the same state as the switch. The position of the switch could just as easily communicate with the rest of the prisoners. (especially if the bulb burns out)
Posted by Angiomorphism (Member # 8184) on :
You find someone in the group who is an electrical engineer, and knows something about lightbulbs, then you estimate what the average lifetime of the bulb will be in minutes, and divide that by 100. Each time someone goes in, they turn on the lightbulb for their designated period of time (and they only do it once, no matter how many times they get called back in). Then, when the lightbulb finally dies, you wait an extra 100 or so days before claiming that everyone has been there (just to be safe) and then you're all out!
Posted by Launchywiggin (Member # 9116) on :
It's
just
IMPOSSIBLE.
There's no way to be sure who the last prisoner will be if all you've got is a lightswitch and they can't see it from their cell. And if there's no other way of communicating to other prisoners other than the lightswitch (IE, marking the wall with your shive), then no plan will work.
Without introducing new information into the riddle, it is impossible.
Posted by Launchywiggin (Member # 9116) on :
Well...
The only 100% solution (no probability involved) I've found is to have one person designated as the only one who will turn the light off.
The rest will only turn the light on for their first visit.
On subsequent visits, the prisoners do nothing.
The "counter" will eventually turn the light off 99 times, though it could take years.
Posted by TomDavidson (Member # 124) on :
Launchywiggin is broadly correct, although a more exact statement is "the rest will only turn the light on the first time they encounter it off."
And as has been noted, this will take -- on average -- about 28 years. There are faster solutions, mainly involving "batches" of prisoners.
Posted by Krease (Member # 9536) on :
Launchywiggin's solution is a correct one, and is the 10000 day average solution. Supposedly there's a solution that takes under half of that on average though.
Posted by The Pixiest (Member # 1863) on :
"Oh crap! Did I turn the light on last time? I don't think I did. Better turn it on again just to make sure!"
Posted by Glenn Arnold (Member # 3192) on :
quote:"the rest will only turn the light on the first time they encounter it off."
Which I think is similar to what I said about switching the position of your right arm when you lower your left arm. Except that you only do it once, and then wait for the guy on the left end to lower his left arm (I think).
![[Smile]](smile.gif)
![[ROFL]](graemlins/rofl.gif)