Author |
Topic: 100 prisoners & a light bulb (Read 167259 times) |
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender: 
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
|
|
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
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  ).
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
|
|
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
|
|
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
|
 |
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
|
|
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
|
|
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
Gender:
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.
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 |
|
|
|
DanS
Guest
|
|
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.... 
|
|
IP Logged |
|
|
|
Vivek
Guest
|
|
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
|
|
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
|
|
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
    
Gender:
Posts: 2873
|
|
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
Gender:
Posts: 2873
|
|
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
Gender:
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:
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)
|
|
IP Logged |
|
|
|
Volume 3 Xanos
Guest
|
|
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
|
|
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:
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:
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!
|
| « 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
Gender:
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  ). 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.
|
| « Last Edit: Jul 11th, 2003, 7:45pm by Chewdog » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Notify of replies
Send Topic
Print
