wu :: forums
« wu :: forums - 100 prisoners & a light bulb »

Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 9:44pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: Eigenray, Icarus, SMQ, william wu, Grimbal, ThudnBlunder, towr)
   100 prisoners & a light bulb
« Previous topic | Next topic »
Pages: 1 ... 5 6 7 8 9  ...  25 Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: 100 prisoners & a light bulb  (Read 166507 times)
Icarus
wu::riddles Moderator
Uberpuzzler
*****



Boldly going where even angels fear to tread.

   


Gender: male
Posts: 4863
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #150 on: Feb 12th, 2003, 3:51pm »

That is an interesting idea, John, and no it has not been suggested before. Unfortunately, light bulbs vary a lot in lifetime, and this also depends on how often they are turned on and off. It's also true that the lifetimes are longer than 2400 hours, so the prisoners would each half to visit more than once to get their allotted bulb time in.
 
Still - this is the first alternative to the counting methods that does not depend on conditions not mentioned in the puzzle. (Okay - it does depend on someone knowing the lifetime, and on the bulb being fresh at the start.)
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
poopie
Guest

Email

Re: How to Solve 100 prisoners & Light bulb?  
« Reply #151 on: Mar 2nd, 2003, 8:57pm »

stumbled on this riddles page.  nice.
as for this problem:
 
Each day, the warden picks a prisoner equally at random, and that prisoner visits the central living room; at the end of the day the prisoner is returned to his cell.
 
the light bulb can convey 2 bits of information
 
is it on or off
is it hot or cold
 
if left on long enough by the end of the day when the warden takes the prisoner back and picks up the next prisoner, that prisoner could see if the bulb is on or not and also feel if it's hot or cold.
 
dunno if this helps :p
IP Logged
harpanet
Junior Member
**





   
WWW

Posts: 109
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #152 on: Mar 8th, 2003, 11:17am »

Whew, this is some thread! I have read most of the posts (not the same as understanding though  Embarassed).  
 
I notice that some of the posts talk about 'day #' and use the days to synchronize or drive the solution. However the riddle now states that the cells are windowless and soundproof. Therefore is it not impossible for any of the prisoners to track time and, by extension, how many visits there have been?  
 
Although I suppose there may be daily routines that allow them to keep track (e.g. slop out, meal times).  
 
Is a multi-stage solution possible if time cannot be tracked?
 
 
IP Logged
Jeremy Randolph
Guest

Email

Re: How to Solve 100 prisoners & Light bulb?  
« Reply #153 on: Mar 13th, 2003, 6:33am »

Whew… seven pages. Ok. I reread the original riddle and saw that a solution had been found that put the average solve time at about 11 years (instead of 27). A while ago I though up the single leader solution, so I figured I would try to figure out this 11 year solution before coming back to the forum. Well, I got something like the binary passing of information. But my way was not ideal. Basically in stage one I had 50 designated counters, and 50 designated passers of information. In stage 2 however 14 of the passers from the last round became pseudo-counters (in that they pretend they counted a second prisoner when actually they did not). This makes it seem like there are a total of 128 prisoners, instead of 100, which makes halving the number of prisoners much more neat and tidy each round. It goes from 64 counters, to 32 to 16 to 8 to 4 to 2 to 1 person who counts 128 prisoners. My average time was about 13 years… 15 if I wanted to be conservative and try to get them out in round one pretty much all the time. A lot of tweaking can be done by adjusting the round lengths. I have 1000, 900, 800, 700, 600, 400, and 200 days for each respective round. Back in high school I took a statistics class and I learned all about standard deviation and what not… so I figure the way to optimize these round lengths (actually the round lengths you all came up with, because yours are better) is to calculate the standard deviation for each round, and make the rounds with a bit higher deviation a little more conservative.  
 
I also wrote a C program for the solution I came up with… but it’s a hell of a lot longer than what AlexH posted. Yeesh… well this is my first programming class…. Ummm… actually I have a test right now.  
IP Logged
Trichoplax
Guest

Email

Re: How to Solve 100 prisoners & Light bulb?  
« Reply #154 on: Mar 14th, 2003, 7:40pm »

Here's a semantically pendantic solution:
Apologies if it's been mentioned already (I don't feel like wading through 7 pages...).
 
"There's a central living room with one light bulb; the bulb is initially off."
 
Notice how this does not state that the bulb is connected to a fitting! Of course, were it simply a loose bulb, it WOULD be initially off... And there is nothing in the riddle which disqualifies it from being a loose bulb.
Thus, all the prisoners have to do in the meeting beforehand is decide upon a sequence of 100 different positions of the bulb in its loose state, with those new to the room placing it in the next positions and those who are not leaving it...
 
This action complies with the dictionary definition of the term "toggle", as "To alternate between two or more electronic, mechanical, or computer-related options".
IP Logged
Wil
Guest

Email

Re: How to Solve 100 prisoners & Light bulb?  
« Reply #155 on: Mar 17th, 2003, 8:37pm »

Back to the bits of information thing...
 
The light can store a single bit (either on or off).  This is a good start.  How 'bout if one of the prisoners also stores state? (i.e. every time he sees the light on, he increments his internal counter, then toggles the light off.  If any other prisoner sees it off, he turns it on, otherwise, he just leaves it alone).  
 
Since the state storing prisoner knows that the light was originally off, then counting and toggling 99 lit bulbs should be all he needs to do to get them inducted into Mensa right?
 
IP Logged
Wil
Guest

Email

Re: How to Solve 100 prisoners & Light bulb?  
« Reply #156 on: Mar 17th, 2003, 8:50pm »

Oops.  looks like that was already suggested but not optimal.  That'll learn me about not reading all prior posts on a subject.
 
Won't happen again.
IP Logged
Wil
Guest

Email

Re: How to Solve 100 prisoners & Light bulb?  
« Reply #157 on: Mar 22nd, 2003, 11:40pm »

I was examining the probabilities that 100 prisoners have each entered the room at least once, but I couldn't see how they were calculated.  Any help as to how you might calculate the probability as a function of the number of days?
IP Logged
Boody
Newbie
*





   
Email

Gender: male
Posts: 42
:(Re: How to Solve 100 prisoners & Light bulb?  
« Reply #158 on: Apr 1st, 2003, 8:44am »

I think that my favorite riddle.
I found a basic solution and I would only know if this is the commun solution that everybody found and that take 27-28 years ?
 
[ hide ]

Only one prisonner count from 1 to 99 when he see the light on and then switch off the light (he's designed by all or he is ramdomly choosen the second day for example).
The others have to switch on the light the first time they see it off (and do nothing else).
[ /hide ]
The number of the day is not taken into account (several prisonners by day is possible), and then we lost information. This is not a optimal solution.
 Sad
I'm trying to search with several counters or with counters of counters and by taken days into account but no genius idea had come in my mind.
IP Logged
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #159 on: Apr 1st, 2003, 10:34am »

yes that is the common solution; congratulations
IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
DanS
Guest

Email

Re: How to Solve 100 prisoners & Light bulb?  
« Reply #160 on: May 12th, 2003, 11:37am »

on Mar 22nd, 2003, 11:40pm, Wil wrote:
I was examining the probabilities that 100 prisoners have each entered the room at least once, but I couldn't see how they were calculated.  Any help as to how you might calculate the probability as a function of the number of days?

 
I think that the chance of all 100 prisoners having been in the room after D days is:
 
[ 1 - (99/100)^D ]^100
 
1000 days -> 4.3e-3
1500 days -> 2.8e-5
2000 days -> 1.9e-7
 
I might not guarantee my release, but at least I'll get out of jail before most of the other solutions (or die trying).
 
My first solution was to break the lightbulb, so I guess that shows what kind of puzzle-solver I am.... Smiley
IP Logged
Vivek
Guest

Email

Re: How to Solve 100 prisoners & Light bulb?  
« Reply #161 on: May 12th, 2003, 8:46pm »

Since I am incapable of thinking the optimal solution, I will change the topic. Solve the puzzle when the original state of the bulb is not known. (I hope no-one has already mentioned it).
IP Logged
Leo
Guest

Email

Re: How to Solve 100 prisoners & Light bulb?  
« Reply #162 on: May 13th, 2003, 6:57am »

on May 12th, 2003, 8:46pm, Vivek wrote:
Since I am incapable of thinking the optimal solution, I will change the topic. Solve the puzzle when the original state of the bulb is not known. (I hope no-one has already mentioned it).

 
This puzzle (with some modifications) was given on the PBS show Car Talk. You simply count to 2*n-1, and whoever was allowed to turn the bulb once, is now allowed to turn it on twice.
IP Logged
Leo
Guest

Email

Re: How to Solve 100 prisoners & Light bulb?  
« Reply #163 on: May 13th, 2003, 9:34am »

The multiple counter algorithm, as given in the PDF paper http://www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBulb.pdf
is wrong. Whenever someone has to turn the light off at the end of a stage without incrementing his counter, a message is lost and the count will never converge. Therefore, this message must be carried to the next occurrence of that stage:
 
Here are the missing cases:
 
  • If a drone, or a "sub-completed" primary counter (who already counted to Cp, and cannot increment his 1st stage counter anymore) has to turn the light off at the end of stage 1, he will have to turn the light on whenever he has a chance during following occurrences of stage 1. This may result in a Drone having to turn the light on twice or more - it's OK.
  • If a previously completed secondary counter leaves the light on  
    at the end of stage 1, he will have to turn it on whenever he has a chance during stage 1.
  • If anyone but the primary counter has to turn the light off at the end of stage 2, he will have to turn the light on whenever he has a chance during following occurrences of stage 2

 
What are the optimal stage durations for this algorithm? I got good results with 500/500.
IP Logged
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2872
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #164 on: May 14th, 2003, 1:22pm »

on May 12th, 2003, 8:46pm, Vivek wrote:
Since I am incapable of thinking the optimal solution, I will change the topic. Solve the puzzle when the original state of the bulb is not known. (I hope no-one has already mentioned it).

This is only interesting when the prisoners have no way of knowing that they're not the first person into the lounge - if the first person to enter knows they're the first person, and everyone else knows they're not, then the first one in simply leaves the bulb as he would if he'd come in to find it off in the case with known initial state...
IP Logged
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2872
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #165 on: May 14th, 2003, 1:33pm »

Something I don't think anyone's mentioned yet: many light switches are actually ternary devices - in addition to the stable "on" and "off" states there's often (in theory always) an unstable equilibrium point in between. Of course, there are switches where the equilibrium is sufficiently unstable that it wouldn't be a reliable means of passing data - and in order to be completely certain you'd need the third state to have an infinite half-life...
IP Logged
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #166 on: May 14th, 2003, 1:55pm »

rmsgrey,
 
That's a good point. You could probably find a small range over which the light switch was stable, and use that to encode a real number, specifying which people had already been there. You might say: but without an infinite half-life, we can't give a guaranteed answer.
 
Well here's something to think about: I'm sure there is a finite half-life for the supposedly stable on & off states as well. Ignoring that the prison guards could decide they wanted it on or off, or that there could be an electrical short (or regulation change) requiring the switch to be replaced (and who knows what position it would end up in), I'm sure we could come up with some natural phenomena that could trip the switch (large current spike? Infestation of large high-jumping frogs? earthquake? tornado throwing around shards of glass?).
 
So, in allowing a (presumably large) half-life for the switch in an intermediate position, we're not necessarily violating the sanctity of the solution...
 
Although we might get into corruptibility of our data, especially since you'd need very accurate placement of the light switch to indicate 2^100 possibilities...
IP Logged

Doc, I'm addicted to advice! What should I do?
Leo Broukhis
Senior Riddler
****





   


Gender: male
Posts: 459
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #167 on: May 14th, 2003, 2:37pm »

on May 14th, 2003, 1:22pm, rmsgrey wrote:

This is only interesting when the prisoners have no way of knowing that they're not the first person into the lounge - if the first person to enter knows they're the first person, and everyone else knows they're not, then the first one in simply leaves the bulb as he would if he'd come in to find it off in the case with known initial state...

 
The problem statement does not say that the ordeal is guaranteed to start on the next day after the prisoners are allowed to meet. The only thing we know is that after it starts, there will be one visit to the lounge per day. This reading of the problem invalidates one of the solutions given in the PDF paper, BTW.
IP Logged
andrefmedeiros
Newbie
*





   


Posts: 1
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #168 on: May 19th, 2003, 8:10pm »

As the switch have just 2 states, if the first guy that enter twice in the room turns on the light and just the guys that enter by the firs time in the room turn it off, the firs guy can count until the light to be turned off 99 times. If they teh day it started, he can discount from 99 the days until ho enter the secont time. But it runs in 10000day (e.g. 27 years) in average.
 
But if we assume that the light bulb can be touched and disconnected, it creates more two states. So, it allow the third guy that enter twice in the room starts the countdown and when he enter there again he can count up to 3 guys that was there by the firs time, reducind the average time it runs to less than 3000 days (e.g. 9 years).
 
What do you think? (Sorry for my english, because i'm brasilian and I'm still learning this language)
 Grin
IP Logged
Volume 3 Xanos
Guest

Email

Re: How to Solve 100 prisoners & Light bulb?  
« Reply #169 on: Jun 5th, 2003, 11:40pm »

I'm afraid I don't have a good algorithmic solution, but I thought another hack might be useful to keep minds thinking.
 
The first guy in smashes the light bulb into greater than or equal to 100 pieces (this may cause injury to him, but that seems like a small price to pay). Then he can arrange the pieces so they're easy to find for the other prisoners.  When he leaves he takes all but 99 pieces.  Each time a prisoner comes to the room for the first time he takes a piece away with him.  When there are no more pieces they can make their assertion.
IP Logged
Volume 3 Xanos
Guest

Email

Re: How to Solve 100 prisoners & Light bulb?  
« Reply #170 on: Jun 6th, 2003, 6:03pm »

My apologies,  
 
I was reading through more of the posts and someone else had already suggested the smashing light bulb solution. Would the moderator please remove my posts.
IP Logged
Zeke the Geke
Newbie
*





   


Gender: male
Posts: 31
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #171 on: Jun 23rd, 2003, 1:38pm »

Here's an idea someone could turn into a new problem -- how many posts does it take on a single thread to make the thread self-perpetuating?  That is, due to factors such as perceived complexity, length and clarity of posts, intelligence and humour of submissions, and failure to read previous posts, does a thread eventually reach the point where it will continue to thread-infinity?  I think one of our uberpuzzlers ought to take a stab at this one!
IP Logged
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #172 on: Jun 23rd, 2003, 4:58pm »

Quote:
I was reading through more of the posts and someone else had already suggested the smashing light bulb solution. Would the moderator please remove my posts.

Quote:
does a thread eventually reach the point where it will continue to thread-infinity?

I suppose one could model a thread as an n-dimensional self-avoiding random walk.  
 
However, ever-vigilant sentinel Überpuzzlers (such as wowbagger)  
ruthlessly ensure that all non-avoiding walks are absorbed!  
 
Tongue
 
« Last Edit: Jun 23rd, 2003, 7:06pm by ThudnBlunder » IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
Chewdog
Newbie
*





  Bluefox1287   Bluefox1287


Gender: male
Posts: 50
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #173 on: Jul 11th, 2003, 7:42pm »

Ok, i'm not sure if this has been sugested before and i appologize if it has. My idea is kind of like the one where you put a mark on the wall, but i would guess that the prisoners are not allowed to have any kind of writing utinsel or anything to write on the wall....
 
Anyway, i assume that the light bulb in the room is a conventional bulb and is made of glass that can be broken. In this situation the first prisoner on the first day could break the bulb into a hundred pieces and make a stack of one hundred broken glass shards (hopefully he wont cut himself in the proccess  Wink). Then he moves one piece of glass into a seperate pile.  
 
Each prisoner from that day on will then remove one piece of glass from the original stack to the second stack ON THEIR FIRST VISIT TO THE ROOM WITH THE BULB. If they were to visit the room twice they are not allowed to touch either piles of glass.
 
When the 100th prisoner enters the room will then know that all 99 other men have been in the room for he will see the shards that represents each of the men.
 
I hope that works, once again i'm sorry if that has been thought of before or if it violates any rules of the puzzle.  Tongue
« Last Edit: Jul 11th, 2003, 7:45pm by Chewdog » IP Logged
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2872
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #174 on: Jul 14th, 2003, 4:39am »

on Jul 11th, 2003, 7:42pm, Chewdogscp wrote:
Ok, i'm not sure if this has been sugested before and i appologize if it has.

 
*points at post 5 posts up the page*...
IP Logged
Pages: 1 ... 5 6 7 8 9  ...  25 Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board