wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> 100 prisoners & a lightbulb
        
(Message started by: SMQ on Mar 10th, 2009, 6:58am)
Title: 100 prisoners & a lightbulb
Post by SMQ on Mar 10th, 2009, 6:58am
This thread is for general discussion of the "100 prisoners and a lightbulb" riddle.  The previous thread (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1027805293) 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 (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1236693415) 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 (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1027805293;start=600#615) in the old thread and follow the links.  For an earlier but much more in-depth summary, start with this post by Icarus (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1027805293;start=375#382).

There are also several similar threads floating around the forums, the most general being Hippo's n prisoners and a k-state switch (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1177584051).  Also of note are 100 prisoners & 2 lightbulbs (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1030162865), Prisoners again- with 2 switches (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1203963868), and 5 Prisoners And A Light Bulb (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1170120860).

Enjoy the discussion! :)

--SMQ
Title: Re: 100 prisoners & a lightbulb
Post by brac37 on Apr 1st, 2009, 12:08pm
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  :)
Title: Re: 100 prisoners & a lightbulb
Post by sgoglia on Oct 5th, 2009, 7:02am
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.
Title: Re: 100 prisoners & a lightbulb
Post by towr on Oct 5th, 2009, 8:27am

on 10/05/09 at 07:02:31, 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.
Title: Re: 100 prisoners & a lightbulb
Post by elani on Dec 25th, 2009, 11:12pm
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.  

[hide]
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.

[/hide]

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!
Title: Re: 100 prisoners & a lightbulb
Post by towr on Dec 26th, 2009, 3:51am
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.
Title: Qu
Post by elani on Dec 26th, 2009, 4:40am
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.

Title: Re: 100 prisoners & a lightbulb
Post by elani on Dec 26th, 2009, 4:49am
And by "finishing the ordeal" I meant to say all have been randomly selected to come out. My apologies for the confusion.
Title: Re: 100 prisoners & a lightbulb
Post by towr on Dec 26th, 2009, 12:38pm
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).
Title: Re: 100 prisoners & a lightbulb
Post by towr on Dec 26th, 2009, 12:41pm
For the single leader strategy, around an expected 10419 days (a number mentioned before) and you get the following graph.
Title: Re: 100 prisoners & a lightbulb
Post by rmsgrey on Dec 27th, 2009, 10:26am
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...
Title: Re: 100 prisoners & a lightbulb
Post by ExplosiveDuck on Jul 20th, 2010, 3:48pm

on 12/27/09 at 10:26:17, 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.
Title: Re: 100 prisoners & a lightbulb
Post by Grimbal on Nov 9th, 2010, 6:58am
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.
Title: Re: 100 prisoners & a lightbulb
Post by nickhinojosa on Nov 27th, 2011, 8:48pm
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.
Title: Re: 100 prisoners & a lightbulb
Post by towr on Nov 27th, 2011, 10:23pm

on 11/27/11 at 20:48:33, 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.
Title: Re: 100 prisoners & a lightbulb
Post by Grimbal on Nov 28th, 2011, 1:01am
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.
Title: Re: 100 prisoners & a lightbulb
Post by towr on Nov 28th, 2011, 2:48am
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...
Title: Re: 100 prisoners & a lightbulb
Post by Grimbal on Nov 28th, 2011, 5:01am
I'd rather use an oil lamp.  Or a candle.
Title: Re: 100 prisoners & a lightbulb
Post by playful on Nov 28th, 2011, 1:00pm
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.
Title: Re: 100 prisoners & a lightbulb
Post by sefero on Dec 14th, 2011, 6:08pm
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
Title: Re: 100 prisoners & a lightbulb
Post by Jessi on Jan 30th, 2012, 3:10am
Ya sure interesting 100 Prisoners and there is no light in  Prison
Title: Re: 100 prisoners & a lightbulb
Post by mnbbnm on Sep 19th, 2012, 6:00pm
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.
Title: Re: 100 prisoners & a lightbulb
Post by Acequotes on Oct 8th, 2012, 5:12am
I have to agree with everyone here  :)
Title: Re: 100 prisoners & a lightbulb
Post by mdg on Nov 22nd, 2012, 5:11am
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?
Title: Re: 100 prisoners & a lightbulb
Post by mdg on Nov 23rd, 2012, 2:16am
Never mind, just saw stage I has a predefined duration :-p
Title: Re: 100 prisoners & a lightbulb
Post by socrateinpigiama on Nov 26th, 2012, 7:33am
The solution is:
The prisoners agree on who counts. Say his name is Tom.
When a non-Tom prisoner is called he:
-turns on the light if the light is off and he never turned it on
-nothing otherwise

So, a non-Tom prisoner will, some day, turn the light on, then never do anything again.

Every time Tom gets called, if he finds the light turned on, he turns it off and count +1.

When he reaches 99 he can say without doubt that everyone has been called.

You can do this for N prisoners also.
Title: Re: 100 prisoners & a lightbulb
Post by Paul Hammond on Nov 26th, 2012, 4:59pm
Yes, that is the so-called "single leader" solution. It takes about 10,418 days on average  (see graphs on the previous page of this thread):

We have to wait 99 times for the counter to turn the light off, with an average wait of 100 days each time, so that's 9,900 days.

Then for the last prisoner to be counted we have to wait an average of 100 days for him to turn up, for the second-last we have to wait 100/2 = 50 days (because it could be either of the two remaining prisoners), and so on. Total expected wait for all the other prisoners is 100/1 + 100/2 + ... + 100/99, or 100 times the 99th Harmonic number, which is approximately 5.18.

That gives 518 days, and 9,900 + 518 = 10,418 .


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