FacebookTwitter
Hatrack River Forum Post New Topic  Post A Reply
my profile login | register | search | faq | forum home

  next oldest topic   next newest topic
» Hatrack River Forum » Active Forums » Books, Films, Food and Culture » DIFFICULT RIDDLE: Braincells at work... let's see you, Hatrackers!

   
Author Topic: DIFFICULT RIDDLE: Braincells at work... let's see you, Hatrackers!
Beanny
Member
Member # 7109

 - posted      Profile for Beanny   Email Beanny         Edit/Delete Post   Reply With Quote 
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 ]

Posts: 803 | Registered: Dec 2004  |  IP: Logged | Report this post to a Moderator
Mathematician
Member
Member # 9586

 - posted      Profile for Mathematician           Edit/Delete Post   Reply With Quote 
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 | Report this post to a Moderator
ssasse
Member
Member # 9516

 - posted      Profile for ssasse           Edit/Delete Post   Reply With Quote 
*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.

Posts: 132 | Registered: Jun 2006  |  IP: Logged | Report this post to a Moderator
Bob_Scopatz
Member
Member # 1227

 - posted      Profile for Bob_Scopatz   Email Bob_Scopatz         Edit/Delete Post   Reply With Quote 
This is a "classic" logic problem. I'll let others provide the solution.
Posts: 22496 | Registered: Sep 2000  |  IP: Logged | Report this post to a Moderator
kojabu
Member
Member # 8042

 - posted      Profile for kojabu           Edit/Delete Post   Reply With Quote 
Can they touch the switch?
Posts: 2867 | Registered: May 2005  |  IP: Logged | Report this post to a Moderator
Gwen
Member
Member # 9551

 - posted      Profile for Gwen           Edit/Delete Post   Reply With Quote 
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 | Report this post to a Moderator
dkw
Member
Member # 3264

 - posted      Profile for dkw   Email dkw         Edit/Delete Post   Reply With Quote 
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 | Report this post to a Moderator
Soara
Member
Member # 6729

 - posted      Profile for Soara   Email Soara         Edit/Delete Post   Reply With Quote 
I don't get it. What do you mean "the entrance to the yard"?
Posts: 464 | Registered: Jul 2004  |  IP: Logged | Report this post to a Moderator
Hamson
Member
Member # 7808

 - posted      Profile for Hamson   Email Hamson         Edit/Delete Post   Reply With Quote 
"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 | Report this post to a Moderator
Dr Strangelove
Member
Member # 8331

 - posted      Profile for Dr Strangelove   Email Dr Strangelove         Edit/Delete Post   Reply With Quote 
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 | Report this post to a Moderator
ElJay
Member
Member # 6358

 - posted      Profile for ElJay           Edit/Delete Post   Reply With Quote 
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 | Report this post to a Moderator
Dagonee
Member
Member # 5818

 - posted      Profile for Dagonee           Edit/Delete Post   Reply With Quote 
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?

Posts: 26071 | Registered: Oct 2003  |  IP: Logged | Report this post to a Moderator
ElJay
Member
Member # 6358

 - posted      Profile for ElJay           Edit/Delete Post   Reply With Quote 
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. [Smile]
Posts: 7954 | Registered: Mar 2004  |  IP: Logged | Report this post to a Moderator
Soara
Member
Member # 6729

 - posted      Profile for Soara   Email Soara         Edit/Delete Post   Reply With Quote 
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. [Smile]

Thanks, that's alot clearer!
Posts: 464 | Registered: Jul 2004  |  IP: Logged | Report this post to a Moderator
Beanny
Member
Member # 7109

 - posted      Profile for Beanny   Email Beanny         Edit/Delete Post   Reply With Quote 
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...

Posts: 803 | Registered: Dec 2004  |  IP: Logged | Report this post to a Moderator
Krease
Member
Member # 9536

 - posted      Profile for Krease           Edit/Delete Post   Reply With Quote 
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. [Smile]

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 | Report this post to a Moderator
Teshi
Member
Member # 5024

 - posted      Profile for Teshi   Email Teshi         Edit/Delete Post   Reply With Quote 
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 | Report this post to a Moderator
Teshi
Member
Member # 5024

 - posted      Profile for Teshi   Email Teshi         Edit/Delete Post   Reply With Quote 
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 | Report this post to a Moderator
Krease
Member
Member # 9536

 - posted      Profile for Krease           Edit/Delete Post   Reply With Quote 
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 | Report this post to a Moderator
TomDavidson
Member
Member # 124

 - posted      Profile for TomDavidson   Email TomDavidson         Edit/Delete Post   Reply With Quote 
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: 37414 | Registered: May 1999  |  IP: Logged | Report this post to a Moderator
Dagonee
Member
Member # 5818

 - posted      Profile for Dagonee           Edit/Delete Post   Reply With Quote 
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 | Report this post to a Moderator
Enigmatic
Member
Member # 7785

 - posted      Profile for Enigmatic   Email Enigmatic         Edit/Delete Post   Reply With Quote 
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

Posts: 2715 | Registered: Apr 2005  |  IP: Logged | Report this post to a Moderator
Krease
Member
Member # 9536

 - posted      Profile for Krease           Edit/Delete Post   Reply With Quote 
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 [ROFL]
Posts: 22 | Registered: Jun 2006  |  IP: Logged | Report this post to a Moderator
Glenn Arnold
Member
Member # 3192

 - posted      Profile for Glenn Arnold   Email Glenn Arnold         Edit/Delete Post   Reply With Quote 
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 | Report this post to a Moderator
Teshi
Member
Member # 5024

 - posted      Profile for Teshi   Email Teshi         Edit/Delete Post   Reply With Quote 
Hm, not being able to count days makes throws a big wrench into my idea.
Posts: 8473 | Registered: Apr 2003  |  IP: Logged | Report this post to a Moderator
happymann
Member
Member # 9559

 - posted      Profile for happymann   Email happymann         Edit/Delete Post   Reply With Quote 
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 | Report this post to a Moderator
Nighthawk
Member
Member # 4176

 - posted      Profile for Nighthawk   Email Nighthawk         Edit/Delete Post   Reply With Quote 
Pay off the guards to kill off all the prisoners. Problem solved on so many levels.
Posts: 3486 | Registered: Sep 2002  |  IP: Logged | Report this post to a Moderator
Glenn Arnold
Member
Member # 3192

 - posted      Profile for Glenn Arnold   Email Glenn Arnold         Edit/Delete Post   Reply With Quote 
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 | Report this post to a Moderator
Angiomorphism
Member
Member # 8184

 - posted      Profile for Angiomorphism           Edit/Delete Post   Reply With Quote 
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 | Report this post to a Moderator
Launchywiggin
Member
Member # 9116

 - posted      Profile for Launchywiggin   Email Launchywiggin         Edit/Delete Post   Reply With Quote 
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.

Posts: 1314 | Registered: Jan 2006  |  IP: Logged | Report this post to a Moderator
Launchywiggin
Member
Member # 9116

 - posted      Profile for Launchywiggin   Email Launchywiggin         Edit/Delete Post   Reply With Quote 
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.

Posts: 1314 | Registered: Jan 2006  |  IP: Logged | Report this post to a Moderator
TomDavidson
Member
Member # 124

 - posted      Profile for TomDavidson   Email TomDavidson         Edit/Delete Post   Reply With Quote 
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: 37414 | Registered: May 1999  |  IP: Logged | Report this post to a Moderator
Krease
Member
Member # 9536

 - posted      Profile for Krease           Edit/Delete Post   Reply With Quote 
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 | Report this post to a Moderator
The Pixiest
Member
Member # 1863

 - posted      Profile for The Pixiest   Email The Pixiest         Edit/Delete Post   Reply With Quote 
"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 | Report this post to a Moderator
Glenn Arnold
Member
Member # 3192

 - posted      Profile for Glenn Arnold   Email Glenn Arnold         Edit/Delete Post   Reply With Quote 
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 | Report this post to a Moderator
   

Quick Reply
Message:

HTML is not enabled.
UBB Code™ is enabled.
UBB Code™ Images not permitted.
Instant Graemlins
   


Post New Topic  Post A Reply Close Topic   Feature Topic   Move Topic   Delete Topic next oldest topic   next newest topic
 - Printer-friendly view of this topic
Hop To:


Contact Us | Hatrack River Home Page

Copyright © 2008 Hatrack River Enterprises Inc. All rights reserved.
Reproduction in whole or in part without permission is prohibited.


Powered by Infopop Corporation
UBB.classic™ 6.7.2