Author |
Topic: 100 prisoners & a light bulb (Read 166663 times) |
|
Zar
Newbie
Posts: 2
|
 |
Re: 100 prisoners & a light bulb  Prison.bmp
« Reply #425 on: Aug 16th, 2005, 12:57am » |
|
1 day on the VERY first day a prisoner, any prisoner can actually claim he and the other 99 have in fact been in that center room
since, to actually get into that court yard, outside a the prison, they would have all infact had to exit their cells
since cells tend to have 1 entrence and exit, thers no other way to get in that court yard, without going through the center room
*see diagram attached
Signed
Matthew McCay
|
|
 IP Logged |
 |
|
|
rmsgrey
Uberpuzzler
    
Gender: 
Posts: 2872
|
|
Re: 100 prisoners & a light bulb
« Reply #426 on: Aug 16th, 2005, 4:08am » |
|
on Aug 16th, 2005, 12:57am, Zar wrote:1 day on the VERY first day a prisoner, any prisoner can actually claim he and the other 99 have in fact been in that center room
since, to actually get into that court yard, outside a the prison, they would have all infact had to exit their cells
since cells tend to have 1 entrence and exit, thers no other way to get in that court yard, without going through the center room
*see diagram attached
Signed
Matthew McCay |
|
Unless, for example, you have the cell-block as a ring with the central room in the enter, the corridor surrounding, and cells outside that, or any of several other possible arrangements - while the cell block will generally have just the one entrance/exit, that doesn't mean that you have to go through the showers (say) to get to the cells...
It's quite plausible that the chosen room is actually off a corridor (if not, the authorities wuold probably have chosen another room for the purpose - or Mensa's really letting its standards slip!)
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
 
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #427 on: Aug 16th, 2005, 7:26am » |
|
One day soon - when I'm not working 16 hours a day on my current project, I will finish what I started during the last high-energy cycle of this riddle - the various simulations under one unified engine that will add credibility to the different solutions, and in some cases show them up as the fraudulent works they are (my proposal will probably be a member of the latter group). In the meantime let's just be satisfied with the solution that the prisoners were all given a key to their cells and every other door separating them from their freedom. After all, we're ignoring the most fundamental technique to problem solving - contriving an environment that trivialises the solution. I'm all for being open minded for the purposes of brainstorming and thus allowing everyone to put in their two cents no matter how ridiculous their ideas may seem, but I think there are limits that should be imposed on this flexibility. One has to ask oneself, why have the problem in the first place, if some reengineering of the factors can illiminate the need for a solution? Here's an example:
Q: What is 2 + 2?
A: I don't know but if you had asked what 1 + 2 was, the answer would have been 3.
A: Who needs mathematics anyway?
A: That's racist.
|
|
IP Logged |
|
|
|
Zar
Newbie
Posts: 2
|
|
Re: 100 prisoners & a light bulb
« Reply #428 on: Aug 16th, 2005, 10:24pm » |
|
Quote:Unless, for example, you have the cell-block as a ring with the central room in the enter, the corridor surrounding, and cells outside that, or any of several other possible arrangements - while the cell block will generally have just the one entrance/exit, that doesn't mean that you have to go through the showers (say) to get to the cells...
It's quite plausible that the chosen room is actually off a corridor (if not, the authorities wuold probably have chosen another room for the purpose - or Mensa's really letting its standards slip!) |
|
often is puzzles they add a 'factor, that is in fact useless, in this one the light bulb is useless
secondally, as you saw everyone automatically goes for the hardest posible soultion most people are thinking inside the box, of the puzzle, the whole ide of menza is to get people who think outside the box in, and keeping, the 'inside the box' people out
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: 100 prisoners & a light bulb
« Reply #429 on: Aug 17th, 2005, 1:04am » |
|
But in this case, thinking inside the box is much more interesting than thinking outside of the box.
The easy way out has been proposed before and isn't worth more than a couple of messages. The hard way has lead to a number of creative solutions, and a discussion as to which is better.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 100 prisoners & a light bulb
« Reply #430 on: Aug 17th, 2005, 4:03pm » |
|
Actually, Zar, your 'solution' is not "thinking outside the box". Thinking "outside the box" is coming up with solutions such as "first prisoner breaks bulb and leaves 99 pieces. All other prisoners take one piece on their first visit. when all the pieces are gone, everyone has been there". (For the record, this particular solution has been suggested at least 10 times. Numerous other "leave/take something to inidicate your visit" solutions have also been given.)
Your 'solution' is more "reinterpreting the problem to my liking". And it (and variants) have also been suggested many, many times.
It is true that for many problems, coming up with "outside the box" solutions shows creativity and intelligence. But this is not the case for this problem. "Outside the box" solutions are fairly trivial and easy to find. "Inside the box" solutions require much ingenuity and creative effort to devise.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #431 on: Aug 17th, 2005, 4:07pm » |
|
Grimbal,
I don't think with this problem, that thinking inside the box is any more interesting than thinking outside the box - I think the real solutions that have been proposed thus far have incorporated a good deal of out-of-the-box type of thinking.
I think it is a matter of our individual interpretation of creative thinking. There is a difference between being creative in the context of a problem and being completely arbitrary. In my opinion, the fabrication of solution-trivialising factors is not creative thinking... it's problem avoidance. An open minded approach to problem solving encourages creative thinking in order to solve the problem - not avoid it. It is a different means to the same end.
The reasoning in a solution should make sense no matter which side of the box you're on, and too many of these "right-brained" solutions introduce speculations as fact in order to satisfy their solution. Such as suggesting that the prison has a particular shape, or that the bulb is within reach and can be broken into 100 pieces. While these things may be true, there is no information provided which would inform us of them.
Another point to note is that real right-brained solutions are rare and usually elegant - the so-called outside-the-box solutions provided in this thread have been the most common suggestion by new comers - are they all thinking outside the box and shocking us all with their insight?
I may as well say "BLAH" to any puzzle given to me and claim that my response is valid as it is the result of my thinking outside the box.
|
|
IP Logged |
|
|
|
shanky
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #432 on: Aug 24th, 2005, 12:45pm » |
|
the answer is --
the courtyard and living room are same room.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #433 on: Aug 24th, 2005, 1:37pm » |
|
You know, I think Shanky is right. All jokes aside, there was some discussion earlier in the thread where William had mentioned that he didn't know the true origin of the riddle or what the expected answer was or even if there was one.
Despite the fact that our investigation into the statistical solutions have proved more interesting, I have to believe the riddle was originally developed with Shanky's (and the 500 others with the same answer) as the correct answer.
Any new comer to the discussion who hasn't read the thread and answers definitively has stated without uncertainty that the solution is that the two rooms are in fact the same. Uncorrupted by this thread and having heard the riddle before and its answer, it must be the original intended answer.
Any thoughts?
|
| « Last Edit: Aug 24th, 2005, 1:39pm by mattian » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: 100 prisoners & a light bulb
« Reply #434 on: Aug 25th, 2005, 9:02am » |
|
on Aug 24th, 2005, 1:37pm, mattian wrote:You know, I think Shanky is right. All jokes aside, there was some discussion earlier in the thread where William had mentioned that he didn't know the true origin of the riddle or what the expected answer was or even if there was one.
Despite the fact that our investigation into the statistical solutions have proved more interesting, I have to believe the riddle was originally developed with Shanky's (and the 500 others with the same answer) as the correct answer.
Any new comer to the discussion who hasn't read the thread and answers definitively has stated without uncertainty that the solution is that the two rooms are in fact the same. Uncorrupted by this thread and having heard the riddle before and its answer, it must be the original intended answer.
Any thoughts? |
|
If you assume the mention of Mensa membership for the prisoners on their release was an incidental corruption, then it's plausible that the originally intended answer was "They've all been in the room already." (While I don't think much of Mensa generally, I don't think that demonstrating the ability to recognise a room would be sufficient for membership)
On the other hand, friends of mine have encountered this puzzle or variants previously under circumstances that make it quite clear that the intention is to require a more mathematical solution.
It's quite possible that there are actually two (now) separate family trees for riddles of this type - one expecting the trick answer; the other looking for the mathematical solution.
The fact newbies are showing up with variant forms suggests that the puzzle is relatively popular, so it's quite plausible for it to have split.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #435 on: Aug 25th, 2005, 9:26am » |
|
I agree with you, but one thing to note is that the mathematical riddles of this type are generally solvable in finite time - not that it should necessarily be that way, but in general it is. The puzzles with trick-type solutions tend to create an impossible problem that can only be solved by means of said trick.
A good example of the latter is the three light bulb, three switch problem: Presented with three switches in the off position, fiddle with them appropriately and then visit the adjacent room containing three previously unseen light bulbs and state which switch is connected to which bulb. Mathematically, this is unsolvable - the practical ("trick") element is the saviour here.
I agree with your perspective on Mensa, precisely because there is a tendency to consider these trick solutions as outside-the-box type, right-brained thinking, which, though valid at a fundamental level, become nausiating as manifestations of self-attributed intellectual credit.
In short: I don't believe that this riddle's original author had any intention of creating a puzzle warranting the sort of effort that the members of this forum have put into its solution. This puzzle created itself in response to a growing irritation with an inundation of "creative", outside-the-box solutions. I think the original problem was one with cleverly chosen wording that went something like this:
100 prisoners are assembled in a rooml of a prison where they are given instructions by the warden. The warden says, "Starting tomorrow, I will pick one prisoner per day and bring him to this room where he will be allowed to operate this light switch ... BLAH BLAH ... when any one prisoner can say with certainty that all of his fellow inmates have visited the room at least once, you will all be set free. QED.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 100 prisoners & a light bulb
« Reply #436 on: Aug 25th, 2005, 1:17pm » |
|
I know this problem from a course in automated reasoning (theorem provers and model checkers). One assignment was to give and prove an algorithm that solved the prisoners and a lightbulb problem; under the assumption of fairness (i.e. every prisoners gets infinitely many turns to enter the room over the course of infinite time).
Such an algorithm was all that was asked here. But after several were given it became a quest to find the fastest; which is a different, much more difficult problem.
|
| « Last Edit: Aug 25th, 2005, 1:18pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 100 prisoners & a light bulb
« Reply #437 on: Aug 25th, 2005, 3:52pm » |
|
I am sure that this riddle was originally intended to be of a mathematical/logical nature, not wordplay or trickery. I am also pretty sure that the original intended answer was the "Leader" solution, possibly with starting "snowball" round.
Certainly, we know (because he said so) that William posted it here to be that sort of puzzle, and his intended solution was "Leader with snowball". The existence of better solutions took him by surprise.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #438 on: Aug 25th, 2005, 4:02pm » |
|
I'll take your word for it. And besides, I concede that the originally intended puzzle is irrelevant in the current context of the problem anyway. None of us would have had any interest in the puzzle had it been anything other than what we deem it to be. It just seems odd to me that this puzzle is so much more popular than all the others by (orders of magnitude). Are there any other optimization puzzles of this sort in the forum?
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 100 prisoners & a light bulb
« Reply #439 on: Aug 25th, 2005, 6:01pm » |
|
There are few others. Until this last year, the 0.999... threads had more posts. But that one died off and this one underwent a new spat of activity after being almost completely dormant for some time. This isn't surprising, as this thread still has things to discover, whereas the other merely introduces the uninitiated to a well-established fact.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #440 on: Aug 25th, 2005, 6:11pm » |
|
I haven't seen the 0.999 puzzle, but I assume it is the 0.999... = 1 thing.
We need some more puzzles without concrete solutions. Anyone care to author puzzles without solutions?
I've tried, but you guys have them all solved within three posts. And the contributed solutions are more elegant than my own anyway.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: 100 prisoners & a light bulb
« Reply #441 on: Aug 30th, 2005, 4:26pm » |
|
on Aug 25th, 2005, 6:11pm, mattian wrote:| We need some more puzzles without concrete solutions. Anyone care to author puzzles without solutions? |
|
I seem to remember a thread or two about the hypothetical "God Algorithm" for Rubik's Cube - which never achieved anything like the popularity of this thread - possibly because the Cube results were reported rather than derived.
Another reason why this thread has been so popular is the dual nature of the problem - most "open" problems require "difficult" solutions. The hundred prisoners offers solutions at every level, from "easy answers" like "break the bulb and use the pieces" through to heavily abstracted token exchanging methods via the relatively simple "single leader" solution. As a result, the thread has been more or less constantly at the front of the forum and consequently stayed very much on people's radar...
|
|
IP Logged |
|
|
|
raven
Senior Riddler
"Why is a raven like a writing desk?" ~M. Hatter
Gender:
Posts: 560
|
|
Re: 100 prisoners & a light bulb
« Reply #442 on: Aug 31st, 2005, 5:42pm » |
|
I'm by far no mathematician, but I am still working on it. I did have a decent solution once, but having read the whole bloody thing realized it was not original or optimized.... nor the best time, but it was better than the leader solution.
|
|
IP Logged |
|
|
|
Nasta
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #443 on: Sep 3rd, 2005, 2:16pm » |
|
on Jul 29th, 2002, 2:05am, johnP wrote:Heh, I'm no expert, but these are my thoughts on the subject:
1) There's no way to make sure all the prisoners will be picked by the warden. No matter how many years pass, you can never be 100% sure all the prisoners get picked.
|
|
wrong, there is, that is why the bulb is there, to form some kind of a trigger. if the trigger does not go off, then the prisoner can be sure that someone has not yet been to the room. so yea, all the prisoners may not be selected, but then no one will claim that they have been.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 100 prisoners & a light bulb
« Reply #444 on: Sep 4th, 2005, 11:28am » |
|
johnP (who probably doesn't visit this forum anymore) was refering to the fact that there is no guarantee that any particular prisoner will ever be picked. No matter how many days have gone by, there is a small, but still non-zero, probability that at least one prisoner has never been picked to go into the room (if there wasn't, then the problem would admit the very easy solution of simply waiting for the probability to drop to zero).
All the bulb does is provide a means for prisoners to communicate their visits to the room to other prisoners. It does not in any way guarantee that they will each get to visit at all.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #445 on: Sep 4th, 2005, 12:36pm » |
|
JohnP's statement is open to interpretation. On the one hand it looks like he's saying that probability does not GUARANTEE that all prisoners will be selected in finite time.
On the other hand, it looks like he's saying that no prisoner can say with 100% certainty that all prisoners have been selected even when in fact they have.
I believe Nasta understood it according to the latter interpretation.
|
| « Last Edit: Sep 4th, 2005, 12:37pm by mattian » |
IP Logged |
|
|
|
Nasta
Newbie
Gender:
Posts: 9
|
|
Re: 100 prisoners & a light bulb
« Reply #446 on: Sep 6th, 2005, 5:48am » |
|
sure, there's probability that a fair coin will forever and ever go only heads and it's probably close to that probability. but that's not the point. unless the time comes that EVERYONE has been in the room, the system that the prisoners have formed beforehand will not trigger and the leader(or whatever the system looks like) can be sure 100% that at least one prisoner has not yet been in the central room. so that's not a problem. after all i believe the solution will not be exact with respect to time, but will be 100% exact with the respect to the confidence that all the prisoners have visited the central room. so e.g. if the optimal solution is for example around 10 years(just guessing), there is still probability, however small, that this period is 1000000000 years, and there's probability, also as small that the period is 100 days...the one thing that must be known for sure is that everyone has been there, that, given thanks to the system they use.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #447 on: Sep 6th, 2005, 5:58am » |
|
on Sep 6th, 2005, 5:48am, Nasta wrote:| the system that the prisoners have formed beforehand will not trigger and the leader(or whatever the system looks like) can be sure 100% that at least one prisoner has not yet been in the central room. |
|
Not quite true - After day 100, a prisoner can not say for certain that at least one prisoner has NOT visited the room. All prisoners may have been selected by day 100, but the process will continue for another few thousand days anyway.
But we know what you mean.
If (time_comes)
{
declare_with_certainty
}
else
{
wait_an_eternity
}
|
| « Last Edit: Sep 6th, 2005, 6:03am by mattian » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 100 prisoners & a light bulb
« Reply #448 on: Sep 6th, 2005, 7:09am » |
|
The usual specification of the problem includes that there is fairness. I.e. that every prisoner would be led to the room infinitely often, [forall] t: [exists] v > t : visit_room(prisoner, v) , (in a welldefined sequences, so not infinite times prisoner 1 followed by an infinite times #2).
So then the process can't stall, and there is no waiting for an eternity (it may just seem that way).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #449 on: Sep 6th, 2005, 7:19am » |
|
the "waiting_an_eternity" bit was solely in the context of JohnP's statement - that a prisoner will never be 100% certain that all have visited.
Nasta and I are saying - JohnP's statement can only be true IF the prisoners are waiting an eternity. Because: either a prisoner will claim freedom with 100% certainty... or he will be waiting for the day to do it. There is no middle ground where, for example, on day 20000, a prisoner arbitrarily claims freedom without being 100% certain.
A quick note on the even distribution of random selection: This does not ensure that the prisoners don't sit around eternally. I'm sure there are several poor solutions which will ensure an infinite sentence despite the fair selection.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Notify of replies
Send Topic
Print