Author |
Topic: 100 prisoners & a lightbulb (Read 43070 times) |
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 2084
|
 |
100 prisoners & a lightbulb
« on: Mar 10th, 2009, 6:58am » |
 Quote  Modify
|
This thread is for general discussion of the "100 prisoners and a lightbulb" riddle. The previous thread is one of the most popular on the board, but it has grown so large and so technical that it's probably scaring people off, so I'm starting two new ones: this one for general discussion, and another one for in-depth technical discussion of the best known solutions.
What has gone before- Many "outside the box" solutions (hold the meeting in the "common" room, break the lightbulb, make marks on the wall, defecate in the corner, etc.) have been discussed. While some are humorous, we try to focus on serious solutions to the riddle.
- There two fairly-simple solutions which many people come up with. The quicker of the two would still take >10,000 days (~28 years) on average for the prisoners to be released.
- More complex solutions are possible, most of which take around 3500-4000 days on average. The best known strategy (due to a genetic algorithm by Hippo) looks to average a bit under 3400 days.
- For a concise summary of the known solutions, see this post by Hippo in the old thread and follow the links. For an earlier but much more in-depth summary, start with this post by Icarus.
There are also several similar threads floating around the forums, the most general being Hippo's n prisoners and a k-state switch. Also of note are 100 prisoners & 2 lightbulbs, Prisoners again- with 2 switches, and 5 Prisoners And A Light Bulb.
Enjoy the discussion! 
--SMQ
|
|
 IP Logged |
--SMQ
|
|
|
brac37
Newbie
Gender:
Posts: 23
|
|
Re: 100 prisoners & a lightbulb
« Reply #1 on: Apr 1st, 2009, 12:08pm » |
Quote Modify
|
Hello all,
I was searching for the 100 prisoners and boxes problem, so I typed "100 prisoners" in Google. Most hits were of another problem, namely the 100 prisoners and one light bulb problem. So I tried to figure out what the problem was and came at
http://www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBulb.pdf
Since it interested me, I printed it and read it.
I read the solutions with one counter and with one primary and several secondary counters. For the algorithm with one counter, a solution with a fixed counter is improved to a solution with a dynamic counter. But the solution with more counters is not improved in this way. So I started thinking about that.
After thinking out some ideas, I found this forum. I saw that some of the ideas are similar to those of others and read some new ideas as well. Furthermore, I understood why the improvement of the multi-counter algorithm with dynamic counters is not included in the above pdf: the improvement is not very large. I will make a post about it in the Technical topic.
Wow, what a problem. It has not only strategically algorithmic aspects: currently, I am thinking about computing the outcome of an algorithm instead of estimating by sampling. I do not understand the binary algorithm yet, but I have not made much efforts in that direction either. I understood that the outcome of the binary algorithm is somewhat worse than the solution with several counters.
Regards
|
| « Last Edit: Apr 1st, 2009, 12:16pm by brac37 » |
IP Logged |
|
|
|
sgoglia
Newbie
Gender:
Posts: 1
|
|
Re: 100 prisoners & a lightbulb
« Reply #2 on: Oct 5th, 2009, 7:02am » |
Quote Modify
|
I realize that it is not up to the new guy to try and guess the most popular riddle, but since you pushed it so far with algorithms, can anybody tell me what is wrong with the solution that:
They agree the first one in breakes the light bulb in exactly 100 pieces (quite doable, takes some effort to count it all in the dark, but it is doable. if there are extras, he just picks up as many as necessary to leave 99 in the room). Everyone picks up one piece when they are in the room for the first time. The one to pick up the last piece - claims they've all been in. It is 100% the fastest way to get out.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 100 prisoners & a lightbulb
« Reply #3 on: Oct 5th, 2009, 8:27am » |
Quote Modify
|
on Oct 5th, 2009, 7:02am, sgoglia wrote:I realize that it is not up to the new guy to try and guess the most popular riddle, but since you pushed it so far with algorithms, can anybody tell me what is wrong with the solution that:
They agree the first one in breakes the light bulb in exactly 100 pieces (quite doable, takes some effort to count it all in the dark, but it is doable. if there are extras, he just picks up as many as necessary to leave 99 in the room). Everyone picks up one piece when they are in the room for the first time. The one to pick up the last piece - claims they've all been in. It is 100% the fastest way to get out. |
|
The room might get cleaned of sharp objects every now and then, to ensure the prisoners can't harm themselves. And they might not have access to the light bulb in the first place: the fixture might be out of reach, or protected against tampering.
Of course the real problem is that it totally bypasses the point of the riddle, and does so in a not very interesting way. It's like peeling the stickers off a rubix cube and sorting out the colors that way. Sure, you get a cube in its solved state, but you didn't really solve it.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
elani
Newbie
Posts: 3
|
|
Re: 100 prisoners & a lightbulb
« Reply #4 on: Dec 25th, 2009, 11:12pm » |
Quote Modify
|
While it defeats the point of the riddle, I still think its pretty interesting; I overlooked the possibility of breaking the light bulb.
Anyhow, having only worked on this riddle for a small time, I think I probably came up with the two most "generic" answers. Can anyone tell me the probabilistic expected times of these two solutions. This is my first time posting, and I think I'm supposed to use the "hide" function, hopefully I'm using it correctly.
1) Any time a prisoner is chosen for the first time, he or she switches the light bulb. After which, any time he or she is selected she counts to see if the light bulb has been switched from its previous position he or she witneesed. First person to reach 99 wins..
2) Same as above but with only one counter. And his or her job is two switch on the light bulb. Every time a new person is selected they turn it off. Every time the "counter" is selected he or she turns it back on, and once again the counter wins when he or she gets to 99.
As I said earlier, these are probably generic answers. The first is intuitively much faster (I am assuming its probably the 28 years answer?) I would appreciate if some one helped me do a "probabilistic analysis" and showed me the steps in doing so. Thanks!
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 100 prisoners & a lightbulb
« Reply #5 on: Dec 26th, 2009, 3:51am » |
Quote Modify
|
I don't think your first solution will work.
There are only 100 switchings in total, so unless one person counts them all, none of them will count up to 99.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
elani
Newbie
Posts: 3
|
|
Qu
« Reply #6 on: Dec 26th, 2009, 4:40am » |
Quote Modify
|
Yes my first solution is very dumb. Good point.
Two Questions:
For people who are good at probability, what is the expected time for the prisoners to finish this ordeal? Then, it would be cool to compare to the expected time our algorithm succeeds.
Also, I was thinking about solutions that would require a confidence interval. My feeling tells me that even if you had an algorithm that gave you 95 % confidence you could save a huge amount of time, which would perhaps be accepted by the prisoners as a risk worth taking, seeing as they may not live through a 28 year expected time algorithm if it has a high variance! Are there known solutions with confidence intervals?
(if you have already mastered advanced algorithms for this riddle, you probably wouldn't want to read on, I Im just going to brainstorm for people who are new to it..)
Maybe there is some way to have switch watchers to "help" finish the win for the chosen lead switcher. The only way involved I could see, however, is if they viewed all the switches, which is very unlikely i suppose.
But maybe there's something I can't see.
Probably the best answers have to do with numbering the days in weird ways.
|
|
IP Logged |
|
|
|
elani
Newbie
Posts: 3
|
|
Re: 100 prisoners & a lightbulb
« Reply #7 on: Dec 26th, 2009, 4:49am » |
Quote Modify
|
And by "finishing the ordeal" I meant to say all have been randomly selected to come out. My apologies for the confusion.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
If you want to know how long it is until all prisoners have been in the room, that's about 518 days. The distribution is as in the attached graph (showing the probability per day of the 100th unique prisoner visiting the room).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
For the single leader strategy, around an expected 10419 days (a number mentioned before) and you get the following graph.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: 100 prisoners & a lightbulb
« Reply #10 on: Dec 27th, 2009, 10:26am » |
Quote Modify
|
The simplest strategy for getting out with 95% probability is to ignore the bulb and simply make the claim after 2-3 years (I've not bothered to work out the precise value, but, eyeballing towr's graph, it's somewhere around there) - saving around 25 years.
Improvements on that are a little tricky to work out since the "claim anyway" day is the day on which the probability of having all visited is at least 95% given that no-one's claimed (or no-one's known to have claimed) on any previous day...
|
|
IP Logged |
|
|
|
ExplosiveDuck
Newbie
Gender:
Posts: 1
|
|
Re: 100 prisoners & a lightbulb
« Reply #11 on: Jul 20th, 2010, 3:48pm » |
Quote Modify
|
on Dec 27th, 2009, 10:26am, rmsgrey wrote:The simplest strategy for getting out with 95% probability is to ignore the bulb and simply make the claim after 2-3 years (I've not bothered to work out the precise value, but, eyeballing towr's graph, it's somewhere around there) - saving around 25 years.
Improvements on that are a little tricky to work out since the "claim anyway" day is the day on which the probability of having all visited is at least 95% given that no-one's claimed (or no-one's known to have claimed) on any previous day... |
|
To me, this is the most interesting answer so far =)
Great riddle though, it's fantastic when such complexity can be achieved through what appears on the surface to be a quite simple dilemma/game.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: 100 prisoners & a lightbulb
« Reply #12 on: Nov 9th, 2010, 6:58am » |
Quote Modify
|
If you take this option of accepting a small risk to die, you still can improve the mark by a few days if the prisoner P going to the room considers the probability that none of the 99 remaining prisoners have been in the room in the days where P hasn't been in the room. So the less P was in the room, the more the others have been, so the shorter the threshold time where he will make the claim.
|
|
IP Logged |
|
|
|
nickhinojosa
Newbie
Gender:
Posts: 1
|
|
Re: 100 prisoners & a lightbulb
« Reply #13 on: Nov 27th, 2011, 8:48pm » |
Quote Modify
|
Okay, so maybe I'm crazy (this solution seems to be a little too simple) but it seemed like the easiest solution would be as follows:
1. Prisoners find out how long the lifetime of the light-bulb is.
2. They equally divide the lifetime of the light-bulb between themselves.
3. Agree that when they are in the living room that they each turn the light on for their allocated time (no more - no less, even if they are brought to the room multiple times).
4. When the light-bulb finally dies, they know that they have all been inside of the living room.
The biggest thing that jumps out at me as a possible problem with this would be the variation in the lifetime between light-bulbs (the average time for some light-bulbs can vary by as much as 1,000 hours), but considering the way that creep-testing works for light-bulbs we know that the maximum amount of time that a light-bulb's manufacturer is allowed to print is the lifetime of the bulb under "ideal conditions". If you ask me, not considering over-heating or excessive movement of the fixture, I would say that this whole prison scenario would be as "ideal" as it gets. The standard deviation for the lifetime of the bulbs is supposed to be 99.7% too, so the odds of getting a dud would be pretty low too.
So as long as they pick the maximum amount of time they should be relatively safe, right?
Now, this solution doesn't seem to be in the spirit of the question, and I know someone had to have come up with this idea before me, but that's the best guess that I have.
PS: So glad I found this website. Incredibly interesting.
|
| « Last Edit: Nov 27th, 2011, 8:51pm by nickhinojosa » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 100 prisoners & a lightbulb
« Reply #14 on: Nov 27th, 2011, 10:23pm » |
Quote Modify
|
on Nov 27th, 2011, 8:48pm, nickhinojosa wrote:| So as long as they pick the maximum amount of time they should be relatively safe, right? |
|
Suppose the maximum lifetime is 100 hours, but it actually burns out after 99 hours, then the 99th prisoner see the light die and declares they've all been in the room. But he'd be wrong.
If they pick the minimum lifetime instead, then you'd have the problem no one will declare they've all been in the room (because the bulb will have burn-time left that no one uses).
This can only work if the burn-time falls into a very, very narrow range. And that's assuming the bulb doesn't simply get replaced periodically.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: 100 prisoners & a lightbulb
« Reply #15 on: Nov 28th, 2011, 1:01am » |
Quote Modify
|
And the burn time is probably not the same if you just switch it on once or if you repeatedly switch it on and off. Finding out the daily allowance to get a burn-out exactly on the 100th day requires experimenting with multiple light bulbs, switching them on and off with different periods.
But OK, it can be done.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 100 prisoners & a lightbulb
« Reply #16 on: Nov 28th, 2011, 2:48am » |
Quote Modify
|
Maybe if you have a light bulb with a chip that disables it when it's reached its allowed burn-time, like you have in (some) beamers...
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: 100 prisoners & a lightbulb
« Reply #17 on: Nov 28th, 2011, 5:01am » |
Quote Modify
|
I'd rather use an oil lamp. Or a candle.
|
|
IP Logged |
|
|
|
playful
Junior Member
meet me at the second fork in the road
Gender:
Posts: 100
|
|
Re: 100 prisoners & a lightbulb
« Reply #18 on: Nov 28th, 2011, 1:00pm » |
Quote Modify
|
This is one of my all-time favorite puzzles. Since the thread is back on "out of the box" solutions, I'll share one of my miserable (but now comical) attempts at finding an answer, way back when, before the counter solution finally came to me. For archival purpose on the encyclopaedic discussion of this puzzle. (I am wowed by the complex algorithms people have come up with.)
Maybe it has already been suggested, as all good theories come with two distinct discoverers, but all bad ones come with about a thousand.
Okay. This solution requires the bulb to be the screw-on type (rather than the bayonet type). These prisoners are amazingly sensitive with their fingers. Somehow they are able to measure one hundredth of the difference between fully screwed and fully unscrewed. The first time you visit the room, you screw the bulb in by one hundredth. If you reach the fully screwed position, you raise your hand.
|
|
IP Logged |
my favorite puzzles
|
|
|
sefero
Newbie
Posts: 1
|
|
Re: 100 prisoners & a lightbulb
« Reply #19 on: Dec 14th, 2011, 6:08pm » |
Quote Modify
|
The shortest possible time that they would be freed is exactly 100 days... right?
the plan is:
1. the first visitor would saw the bulb turned on and turn it slowly until it turns off
2. that would be the start point then turn it 7.2 degrees to off state
3. the rest would find the bulb turned off
4. if its their first time visit in the room turn it 7.2 degrees.
5. If they have visited they would do nothing
6. then they would mark the new original position and turn it on
7. if it have gotten two full rotation which is 720 degrees to turn on.. its confirmed that they all have visited the room
8. if not they would return it to its new original position
everyone can declare when they have visited the room at the minimum time possible
the minimum possible is 100
when luck is on their side
|
|
IP Logged |
|
|
|
Jessi
Newbie
farnandasamith
Gender:
Posts: 1
|
|
Re: 100 prisoners & a lightbulb
« Reply #20 on: Jan 30th, 2012, 3:10am » |
Quote Modify
|
Ya sure interesting 100 Prisoners and there is no light in Prison
|
|
IP Logged |
|
|
|
mnbbnm
Newbie
Posts: 1
|
|
Re: 100 prisoners & a lightbulb
« Reply #21 on: Sep 19th, 2012, 6:00pm » |
Quote Modify
|
To improve on the counter solution leave the first person takes the light bulb out, the bulb remains out until the first person to repeat screws in the light bulb and turns it on. The count starts at a much higher number... day of first repeat-1.
|
|
IP Logged |
|
|
|
Acequotes
Newbie
Gender:
Posts: 5
|
|
Re: 100 prisoners & a lightbulb
« Reply #22 on: Oct 8th, 2012, 5:12am » |
Quote Modify
|
I have to agree with everyone here
|
|
IP Logged |
|
|
|
mdg
Newbie
Posts: 2
|
|
Re: 100 prisoners & a lightbulb
« Reply #23 on: Nov 22nd, 2012, 5:11am » |
Quote Modify
|
I read the pdf with possible solutions, but have one question about "One Counter Protocol, with Dynamic Counter Assignment". How does everyone know stage I ended? The first one who enters twice turns on the light, now suppose the next day, a fresh person enters and turns off the light. Next day, someone who has been there before, turns on the light again and assumes he is the counter (he has never seen the light on). Thus he will disturb the original counter's process and have a wrong starting number himself as well?
Or am I missing something?
|
|
IP Logged |
|
|
|
mdg
Newbie
Posts: 2
|
|
Re: 100 prisoners & a lightbulb
« Reply #24 on: Nov 23rd, 2012, 2:16am » |
Quote Modify
|
Never mind, just saw stage I has a predefined duration :-p
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print