posted
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.
posted
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?
Posts: 168 | Registered: Jul 2006
| IP: Logged |
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.
Posts: 132 | Registered: Jun 2006
| IP: Logged |
posted
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!
Posts: 283 | Registered: Jul 2006
| IP: Logged |
posted
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.
Posts: 9866 | Registered: Apr 2002
| IP: Logged |
posted
"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.
Posts: 879 | Registered: Apr 2005
| IP: Logged |
posted
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.
Posts: 2827 | Registered: Jul 2005
| IP: Logged |
posted
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.
Posts: 7954 | Registered: Mar 2004
| IP: Logged |
posted
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. Posts: 7954 | Registered: Mar 2004
| IP: Logged |
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.
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.
Posts: 22 | Registered: Jun 2006
| IP: Logged |
posted
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.
Posts: 8473 | Registered: Apr 2003
| IP: Logged |
posted
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.
Posts: 8473 | Registered: Apr 2003
| IP: Logged |
posted
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.
Posts: 22 | Registered: Jun 2006
| IP: Logged |
posted
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.
Posts: 37449 | Registered: May 1999
| IP: Logged |
posted
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.
Posts: 26071 | Registered: Oct 2003
| IP: Logged |
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.
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 Posts: 22 | Registered: Jun 2006
| IP: Logged |
posted
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.
Posts: 3735 | Registered: Mar 2002
| IP: Logged |
posted
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.
Posts: 258 | Registered: Jul 2006
| IP: Logged |
posted
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)
Posts: 3735 | Registered: Mar 2002
| IP: Logged |
posted
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!
Posts: 441 | Registered: Jun 2005
| IP: Logged |
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.
Posts: 1314 | Registered: Jan 2006
| IP: Logged |
posted
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.
Posts: 37449 | Registered: May 1999
| IP: Logged |
posted
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.
Posts: 22 | Registered: Jun 2006
| IP: Logged |
posted
"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!"
Posts: 7085 | Registered: Apr 2001
| IP: Logged |
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).
Posts: 3735 | Registered: Mar 2002
| IP: Logged |
Printer-friendly view of this topic
![[Smile]](smile.gif)
![[ROFL]](graemlins/rofl.gif)
