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

Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 1:11pm

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





   
Email

Posts: 156
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #100 on: Aug 20th, 2002, 11:29am »

I ran a test on the 7 stage version with your stage lengths (and 250 for the 7th stage in round 1). Average completion time 6877.Same random number sequence yields average completion time of 4596 using the formulae I have above.  
The deviation of different trials is in the ballpark of 40 days using my curent 2000 times played per test so those numbers aren't exact but they are close.  
 
Those formluae in my program are derived from the proof I gave earlier on why binary stages is O(n (log n)2). The constants .7 and .5 are arbitrary but gave reasonable results on some test cases, with each new round winning somewhere between 2/3 and 3/4 of the still active games.
IP Logged
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #101 on: Aug 26th, 2002, 1:59pm »

I found biwema's proposal interesting, and so I have done some analysis using a spreadsheet. From my calculations, the suggested stage lengths are too short, and the optimal expected time is about 5500 days.
 
The nice thing about the binary solution is that we don't have to pick anybody ahead of time. Consider the first round: the first time a person visits, they will drop off their counter if the light is off, or pick up someone else's if the light is on. The first stage can be over as soon as everyone has visited! This thought encouraged me to try and figure out when everyone will likely have visited the room.
 
At first, I tried to find a formula, but I guess I'm not as good at probability as I once was, because I couldn't find one that seemed consistent. So I made a simulation spreadsheet. This is probably better anyways, since I'm not sure how to differentiate factorials  Wink
 
It turns out that the probability that everyone has visited gets up to 50% when you get to 498 days, and that after 680 days you are up to 90%. This got me thinking: what is the best value for this probability? Should we quit early to make short stages, or should we keep going to reduce the probability of round 1 failing.
 
Of course, the best value is achieved when adding one extra day to a stage reduces the probability of round 1 failure enough so that we can take one day off the expected incarceration time (I used the word incarceration  Cool). After this, you get only marginal improvements in round 1 success rates by adding extra days, and you're better off taking your chances that you'll need a second round. Before this, you can significantly improve your chances in round 1, avoiding the penalty of 7 extra rounds.
 
After calculating this all out, I got the following stage lengths:
 
stage 1 : 1006
stage 2 : 995
stage 3 : 933
stage 4 : 849
stage 5 : 781
stage 6 : 713
 
stage 7 success : ~100
total success : 5377
 
stage 7 failure : 643
round 1 total (failure) : 5920
round 2 : 643 * 6 + ~100 = 3958  
total (failure) : 9878
 
The probability of not getting out after the first round is about 0.2% per stage, for a grand total of about 1.5%. This
gives another 81 days expectation for the second round. The total expectation is therefore close to 5450 days.  
 
This makes good logical sense too: because of the extreme price the prisoners must pay for not making the first round, it's better to wait longer in the first round just to make completely sure. The second round can be played with each stage lasting 643 days to speed things up, since chances are you only have one person left to collect at any stage in the second round.
 
The way I dealt with the extra 32 and the extra 4 was to initially assign 28 people 2 counters instead of 1. This way, there are only 72 people who must be counted in stage 1, and then 64 people who must be counted in stage 2, 32 in stage 3, etc.
 
The problem with the binary solution is that it has so many stages. Each stage eliminates whatever memory the system had, and so you have to wait a long time to be sure of anything.
 
The interesting thing that I find about this is how the stages in which you have fewer people to collect go faster than the stages in which you have more people to collect. In either case, the stage can be over only when everybody visits (before then, somebody you need to collect might not have visited yet).
 
All right, now it's time to consider the solutions where each person is assigned a day... Smiley
IP Logged

Doc, I'm addicted to advice! What should I do?
AlexH
Full Member
***





   
Email

Posts: 156
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #102 on: Aug 26th, 2002, 5:50pm »

Just for the record ...  
on Aug 7th, 2002, 7:19pm, AlexH wrote:
Random additional tweak to the n (log n)^2 method. If we're doing this in binary,  we don't actually have to designate who are drones and who are counters in advance. Everyone starts as active. If an active person enters the room, they toggle the light switch. If it was initially on they call themselves a counter and stay active in the next stage (though they do nothing further during this stage). If it was initally off they call themselves drones and then become inactive from that point on. Of course anyone, whether active or not, has to do the turn off and account for it next time through if the light is on at the end of the stage. This doesn't change anything asymptotically, but it saves a factor of 2 in expectation.  

 
James:  
I wrote a program to perform the binary dynamic method with 7 stages on 100 prisoners. The trick with finding the optimal time is that you're optimizing over all stage lengths simultaneously (including those in later rounds) and there will be local extrema that are not the global extrema. My numbers are certainly not perfectly optimal, but they were derived from the properties of the distribution and should be at least close. The couple lines of code (for determining stage boundaries) I posted above yield close to 4500 days as the expected incarceration time under the dynamic binary method with 100 prisoners. The chance of success in each round with these numbers is in the ballpark of 2/3-3/4. In batches of 2000 trials generally the worst case takes about 5 rounds to complete.  
 
I think its slightly faster to get to 128 by just starting 1 players counter at 29 and all the others at 1, though the difference is very small.  
 
Here is the c++ code for determing the expected mean/variation of each stage's completion time.
 

  // Set up data used for determining stage sizes  
  // slightly inefficient computation method
 
  meanEstimate = new double[stages];  
  varianceEstimate = new double[stages];
 
  k=numPrisoners; // k is anticipated number of message passers in current stage
  for(i=0 ; i<stages ; i++){
   varianceEstimate[i] = 0.0;
   meanEstimate[i] = 0.0;
   for(j=1;j<=k;j++){  
    meanEstimate[i] += // computing H(k) here
     1.0 / (double) j;
    varianceEstimate[i] += // summing variances of geometric variables
     (double) (numPrisoners - j) * (double) numPrisoners / (double) (j * j);
   }
   meanEstimate[i] *= numPrisoners;  // mean =  Harmonic(k) * numPrisoners
   k = (int) ceil((double) k / 4.0) * 2;  
  }  
 
« Last Edit: Aug 26th, 2002, 5:54pm by AlexH » IP Logged
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #103 on: Aug 27th, 2002, 8:06am »

Alex,
Please Ignore Previous Post!  Embarassed
 
I found a couple bugs in my spreadsheet. I had overpenalized the first-round-failure case, leading the longer-than-necessary stages. Now my stage lengths are:  
 
 
stage 1 : 755
stage 1 : 742
stage 1 : 674
stage 1 : 605
stage 1 : 536
stage 1 : 470
stage 7 success : average 151
round 1 success : average 3933
round 1 success probability : 0.774
 
stage failure probability : 0.964 (they're all the same!)
stage 7 failure : 402
all stages in round 2 : 402
 
each round failed : 2814
 
net expectation: 4500 days (roughly)
 
Now this is similar to what you are suggesting. Maybe our solutions are not so different after all...
 
I guess I should check my work more carefully the first time!
Please Ignore Previous Post!
IP Logged

Doc, I'm addicted to advice! What should I do?
biwema
Newbie
*





10470799 10470799    


Posts: 5
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #104 on: Aug 27th, 2002, 8:18am »

Hi,
 
James and AlexH, that are good ideas do merge the 4-chunk. Nevertheless it is time I gave up the approach with the binary stages Sad. However much they will bring down the average running time of each stage, the number of stages is still a big disadvantge.
 
Besides the [2,2,2,2,2,3] approach I also simulated a new [3,3,2d,2d,3d] approach where 3 stages are dynamic. Here only 28 of the 36 assigned counters have to count up to 3, the remaining 8 only up to 2 in stage 1.
 
In my simulations I simulated all the stages separately, that they achieve an overall success of about 70% after round 1. That means, that a 6 stage approach must have 95% in every stage, a 2 stage approach only 85%.
 
[3,3,2d,2d,3d] gains 4100 days, If I replace the [2d,2d] part by a [4] it gets a bit worse.
 
[5,5,4], [5,4,5] and [4,5,5] reach 3700 days each; maybe [5,5,4] is slightly better than the other (between 71.5 and 72%).
 
Surprisingly, [10,10] reaches with an 2200 and 1500 stage also 3700 days at 71.5%. If the first round is unsuccessful, a second round will a fewer days due to the smaller number of stages, and therefore increase the global expected value by a smaller amount. Maybe this approach will ahve the smallest global expeced value.
 
In the riddle itself, William Wu says:
Quote:
Note: OK, so you have a solution. Big deal. Now prove it's optimal! And e-mail me the proof please! =)  

 
Now, several solutions are so close and depend much on fine tuning. I think a proof of a solution being optimal could be quite difficult. I wonder which solution William had in mind when he added that part of the question.
IP Logged
Paul Hammond
Newbie
*





   


Posts: 29
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #105 on: Aug 27th, 2002, 8:47am »

FWIW, with Alex's 7-stage binary method and the stage lengths below, I get a mean release time of ca. 3500 days:
 
-First round-
Stage 0: 600
Stage 1: 500
Stage 2: 450
Stage 3: 400
Stage 4: 375
Stage 5: 350
Stage 6: 250
 
In subsequent rounds, all stages are 200 days long.
IP Logged
AlexH
Full Member
***





   
Email

Posts: 156
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #106 on: Aug 27th, 2002, 9:13am »

James: yep those look pretty close to my stages.  
774
705
639
577
520
448
375
All stages in future rounds: 298
 
Technically my stages are all 1 day longer in some sense, since you can steal 1 extra day per stage by having the last day of 1 stage also be the first day of the next. My stage lengths aren't actually tuned to the 100 case, they are derived from the formulae I posted above which work for any number of prisoners. We differ a little more early on I think because I use 1 prisoner with a 29 counter instead of 28 with counters at 2.  
 
biwema: if we restrict ourselves to these staged counter methods then selecting digit size O(log n) appears to be optimal asymptotically as I discussed earlier. O() notation hides constants of course so this doesn't prove anything with a fixed size problem.  
 
I'd be very impressed with any formal proof of optimality over all possible solutions especially on the specific 100 prisoner case. It seems like it would be very difficult even given that you know the optimal algorithm.  
 
Edited to add: Paul snuck in on me again  Tongue
Wow. That result is faster than I would have expected for the binary method. I will have to take a look at it.  
 
Edited again: I plugged those stage lengths in and I wind up with averages around 5900. I think you might have an error in your formulae somewhere.
« Last Edit: Aug 27th, 2002, 9:24am by AlexH » IP Logged
Penumbra
Guest

Email

Re: How to Solve 100 prisoners & Light bulb?  
« Reply #107 on: Aug 28th, 2002, 9:03am »

First off - nice long thread that actually homes in on the exact mathematical deterministic solution.. so congrats for all your dedication (nay... obsession!!)  Roll Eyes
 
FWIW.. All the mathematical approaches so far are based in some way on the light's binary "on/off" state as the only information that can legitimately be passed on to the next occupant of the lounge.
However.. there is a third "flag".. the silence of the previous person(s).  When you enter the room, you know that the person before you failed to shout out "Release us!".. so they knew that that not everyone had entered the room.  This silence could be used in some way as a decision maker...  
Unfortunately I'm not sure how...!!!
 
One other comment.. I do like the "hold the meeting in the lounge" solution.. it was what I came up with when someone sent me the puzzle via email.. (and which led to my journey here in search of the solution!!)  HOWEVER... It should be pointed out that the later puzzle in the list "100 Prisoners and 2 light switches" specifically states that "the prisoners meet in the CAFETERIA to agree a plan"...  
I guess that's there to rule out the "trick question" solution.  Happy hunting & don't give up......    Smiley
IP Logged
AlexH
Full Member
***





   
Email

Posts: 156
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #108 on: Aug 28th, 2002, 2:52pm »

I'm not sure what you're talking about with regard to people failing to shout out "release us". As soon as someone says that you either 1) get released and know that everyone has been to the lounge (not that you care anymore) or 2) get executed and know that not everyone has been to the lounge (once again, not that you care).
IP Logged
isu_cyclones
Newbie
*





   
Email

Posts: 2
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #109 on: Sep 1st, 2002, 12:54am »

Hi guys,
This might be a solution.
 
In the meeting, one of them is assigned as the leader.
 
Only the leader can switch the bulb off.
Everyother person should switch on the bulb exactly once.
This should be done the 1st time they find the bulb off.
 
Note that this necessarily need not happen in their first visit, as in the case when they find that the bulb was already on.  
 
The leader keeps a count of the number of times he turns on the bulb and when it reaches 99, he announces.
 
===============================
In a world without doors or walls,
who cares for Windows or Gates.
Stand for Free as in FREEDOM
IP Logged
isu_cyclones
Newbie
*





   
Email

Posts: 2
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #110 on: Sep 1st, 2002, 1:01am »

Oops... the last line shld read as,
 
"The leader keeps a count of the number of times he turns OFF (not on) the bulb and when it reaches 99, he announces."
 
===============================
In a world without doors or walls,
who cares for Windows or Gates.
Stand for Free as in FREEDOM
IP Logged
AlexH
Full Member
***





   
Email

Posts: 156
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #111 on: Sep 1st, 2002, 1:39pm »

Hi isu, welcome to the board. What you posted is a correct solution which we've dubbed the "single leader" model. A while back Paul had a really nice idea for doing things faster and lately we've been talking about where that idea takes us. The single leader model takes up over 10,000 days on average, and generally grows like m2 for m prisoners to finish, while these alternatives give times in the 3,500-4,500 range and grow like m(log m)2/(log log m) or m (log m)2
IP Logged
pa0pa0
Newbie
*





   


Posts: 16
not giving up on binary  
« Reply #112 on: Sep 7th, 2002, 8:31am »

Has anyone tried combining Salem's modification with the binary method?
 
(It doesn't seem feasible to combine it with the non-binary methods, since then the assistant counters can get stuck while incomplete.  But with the binary method, there are no incomplete counters.)
 
Thus: first 100 days as per Salem, after which either the light is still off (leading to victory on day 101) or it is on and the binary method starts at that point (with the polarity of the bulb reversed).  The leader is pre-determined during the prelude, and gets an initial count of (on average) about 12, but the assistant counters are determined dynamically.  The leader never releases any counts, but only sucks them up.
 
It would be nice if this brings the binary method back into contention.
IP Logged
AlexH
Full Member
***





   
Email

Posts: 156
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #113 on: Sep 7th, 2002, 10:58am »

Thats a good point, we could combine that idea with the binary dynamic idea, but there would be 2 problems.  
1) We'd have to pick a window much smaller than 100 days to be optimum-- I talked about this a while back but its even more the case if we're trying to apply it to the dynamic methods.  
2) Our gain will be very small. Let k be the number of visits before the first repeat. If k is much smaller than m (which it almost always will be since k averages O(sqrt(m)), then I'd estimate we'd gain about k*((log2k)-2) days. For m=100 if we spent 16 days on this stage (which I think is our optimal) then I estimate we'd have a net gain of about 17.3 days in expected completion times of the stages, but we'd get less benefit on the whole since this trick increases the variance of stage finishing times.  
 
Intuitively the problem is that while this trick does gain us a small reduction in the number of active participants in the next few stages, those small reductions are of very small benefit because the stages take time proportional to m * log (# active) instead of m * (# active) as it was in single leader case.  
 
It a good point and you're right it does work, but the gains are unfortunately very small.  
 
Edited:
I still agree with everything I said about the asymptotics, but the hard numbers were actually computed as if it were the 128 prisoner case rather than 100. On 100 you'd gain a bit more because you'd have a good chance passing the 96 threshold and saving some combines in the 5th stage. This still won't be close to catching the larger digit versions but it will be a bit better than just 17 days.
« Last Edit: Sep 8th, 2002, 2:51am by AlexH » IP Logged
wviljoen
Newbie
*





   


Posts: 1
100 prisoners & Light bulb solution  
« Reply #114 on: Sep 16th, 2002, 1:40am »

The essence of this problem lies in one word - Random! First of all it says explicitly that no one can see the light from their cells and second the warden will not have them meet in the common living room because then he needs to be shot for stupidity. Random is the key. If he means that he will select a person each day randomly then I assume he means he will go through the list like a the Random function on a CD player. It will play the whole playlist but in no particular order. This is simple, everyone that goes into the room leave the light off until such a time that a person goes in for the second time. He turns the light on and the next person that sees the light will make the claim. Therefore on the 102nd day they will have their freedom. However, if Random meant that the warden can select any person more than once without having another person selected at all, this is closer to true random - pretty much like the lotto draw and then there's no luck for the prisoners. In this scenario they are stuck and no binary and no statistics will save them because there is no solution.  
 
Regards
Qpin
IP Logged
S. Owen
Full Member
***





   


Gender: male
Posts: 221
Re: 100 prisoners & Light bulb solution  
« Reply #115 on: Sep 16th, 2002, 7:36am »

on Sep 16th, 2002, 1:40am, wviljoen wrote:
If he means that he will select a person each day randomly then I assume he means he will go through the list like a the Random function on a CD player. It will play the whole playlist but in no particular order. ... However, if Random meant that the warden can select any person more than once without having another person selected at all, this is closer to true random - pretty much like the lotto draw and then there's no luck for the prisoners. In this scenario they are stuck and no binary and no statistics will save them because there is no solution.

Yeah, the intended meaning is your "true random" interpretation, or else it's too easy. But even with truly random choices they can achieve their freedom with 100% certainty... see the last, oh, 100 posts or so!
IP Logged
S. Owen
Full Member
***





   


Gender: male
Posts: 221
Applications of 100 prisoners & lightbulb problem?  
« Reply #116 on: Sep 16th, 2002, 7:39am »

The analysis of this problem has gotten quite sophisticated here, far beyond the call of duty. I have to wonder: is this a disguised version of a "real life" problem? I suspect that it is related to Byzantine agreement problems in randomized algorithms, but haven't thought it through.
 
I'll see what I can come up with, but it would be nifty if this was all just relevant enough to produce a respectable paper on a known problem. Any ideas?
IP Logged
Alex Hartlaub
Guest

Email

Re: How to Solve 100 prisoners & Light bulb?  
« Reply #117 on: Sep 17th, 2002, 8:32am »

Can we get a actual answer from w.wu?  Roll Eyes
IP Logged
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #118 on: Oct 14th, 2002, 8:42pm »

on Sep 17th, 2002, 8:32am, Alex Hartlaub wrote:
Can we get a actual answer from w.wu?  Roll Eyes

 
I don't have the actual answer apparently! Shocked Prior to all the arguments in this terrific thread, the best answer I knew of was the leader solution combined with Salem's modification. I asked my algos professor last semester if this was optimal, but we couldn't figure out how to prove or disprove its optimality. I never thought of a stage-based algorithm, which apparently beats the leader solution by a mile.  
 
Following the same curiosity that S.Owen voiced, I'm trying to find out if this problem has already been studied extensively in the academic world, but perhaps under a different guise. Just got a book from the library about distributed algorithms -- algorithms for systems where there are multiple agents working toward some common goal. It would be most exciting if the world doesn't know about the stage based solution yet.
IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #119 on: Oct 18th, 2002, 4:53am »

Asked some more professors but they couldn't think of anything offhand, or are too busy doing far less interesting things to think about it. Perhaps it would be easier to find existing material on this riddle if we take a reverse-engineering approach and ask ourselves what real-world problems this riddle models. What kind of problem would require:
 
1. A 100% probability of success. (Many lives on the line?)
2. Multiple agents working toward a common goal.
3. Agents randomly take turns using a shared resource (the light bulb)
 
I can't think of many situations that require the first requisite ... in the real world I think we usually accept that a system can fail with some tiny probability. Then again, I've never been in the real world so I don't really know. Perhaps a good variant of this problem would be to design a slick algorithm that gets the prisoners out in a short time, given that we can tolerate a .99 probability of success (or some other high value close to 1). If we sacrifice a sliver of certainty, could we get the prisoners out in a thousand days or so? A solution to this variant might be also more practical for analogous real-world situations.
 
Let's say hypothetically that we find the optimal solution to the 100 prisoners problem or its variant. How do we prove that it's optimal? We could get an optimal solution and not even know that it's optimal.  
 
OK, I really should sleep now.
IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
thelonious
Newbie
*





   


Posts: 11
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #120 on: Oct 23rd, 2002, 8:40pm »

I think we are making some assumptions here.  And that's fine.  We should be sure and keep those in mind however.  It appears from the solutions here that we are assuming an even distribution random selection.  For which, there is probably a better term than what I just used.  But we seem to be saying, that, given a certain percent chance that the random selection process will have all prisoners selected at least once by a certain number of days, we proceed from there.  For example, in the solutions that work around 3500 days with this type of random selection, how do they perform when prisoner #1 is only selected to enter the living room on day 5000?  And only every 5000 days?  This is not probable given a decent random selection process, but if we assume a good random selection process, say, after 2000 days we know that all prisoners will have visited the room at least once, then we can say, after 2000 days someone can just make the assertion.
If we assume a random set where one single prisoner is never selected, then that's obviously ridiculous.  The riddle loses all meaning as the satisfying condition is never met.  But if we are assuming an even spread random selection algorithm, for which there is probably a better term than what I juse used, then we are guaranteeing that all prisoners would have been selected in X number of days.  So if we make this assumption, the optimal solution is back to someone making the assertion on day X.
So it seems that we are working on the assumption of a level density weighted random selection process, for which there is probably a better term that what I just used, and working from there to decide on stages that would most likely be successfully completed in a certain amount of time.  Which seems just a variant on assuming that all prisoners would have visited by day X.
So I think we are Schroedinger's cat chasing our own tail.  But it sure is fun.
Just thought I would throw in a few thoughts.
IP Logged
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #121 on: Oct 23rd, 2002, 10:49pm »

I think it's implicit that the random selection is uniformly distributed amongst the 100 prisoners, since no special distribution was specified. Regardless, I have modified the problem slightly so it says that the warden chooses a prisoner equally at random each day. (Choosing with replacement is also implicit since the chosen prisoners return to their cells afterwards.)
 
(regarding the wording you were looking for, here are some choices: uniform distribution, uniform probability mass function, equally at random, equiprobable, uniformly at random = u.a.r.)
 
(another good, common "term" is i.i.d. = independent and identically distributed. used to describe random variables.)
« Last Edit: Oct 24th, 2002, 11:04am by william wu » IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
Josh Johnson
Guest

Email

Re: How to Solve 100 prisoners & Light bulb?  
« Reply #122 on: Oct 25th, 2002, 2:17pm »

Okay, here is my contribution to the 'single leader' approach.  I read through all the posts and I don't think I've seen this up here anywhere yet.  The difficulty with this problem, as noted by several of you already, is the randomness used in selecting who goes into the room with the light.
 
The fastest way I can calculate the leader approach to work is if the leader is randomly selected every other day starting with the second day and the other 99 inmates are randomly selected to go (without repetition) every other day starting on the first day.  Keep in mind, the probability of this happening is almost zero, but not actually zero.  In other words, improbable but not impossible. The leader is only allowed to turn off the light and the inmates are only allowed to turn on the light.  Thus the following would occur (L=leader, Pn=Prisoner n):
 
P1,L,P2,L,P3,L....P99,L

 
If this is the case then the prisoners can be released in 198 days (when the leader turns off the light for the 99th time).
 
The second thing I wanted to post was my MATLAB script (minus comments to save space) to determine the effectiveness of the leader approach.  I have run this script about 5,000 times and found the minimum number of days to be 6,324.  This number, however, is based on the randomness of selecting which inmate enters the room and is definitely not the correct answer.  Comments are welcome (except on the coding style/efficiency; I'm an aerospace engineer, not a seasoned computer programmer).
 
clear all;
for n=1:1000
    NumPrisoners = 100;
    Prisoner = zeros(NumPrisoners,1);
    LeaderCount=0;
    Day = 1;
    LightStatus = 0;
    Chance = 0;
    while Chance == 0
   PrisonerSelected = fix(NumPrisoners*(rand(1)-.001))+1;
   if PrisonerSelected == 1 & LightStatus == 1  
  LeaderCount = LeaderCount + 1;
  LightStatus = 0;
  if LeaderCount == (NumPrisoners - 1)
      Chance = 1;
  end
   elseif PrisonerSelected ~= 1 & LightStatus == 0
  if Prisoner(PrisonerSelected) == 0
      LightStatus = 1;
      Prisoner(PrisonerSelected) = 1;
  end
   end
   Day = Day +1;  
    end
    Results(n)= Day;
end
min(Results)

 
Each run of this code does 1000 iterations of the puzzle.
 
-Josh
 
IP Logged
SWF
Uberpuzzler
*****





   


Posts: 879
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #123 on: Oct 28th, 2002, 9:52pm »

Unless Paul Hammond's calculation of the 7 stage binary method involves some tricks not documented here, I think the calculation giving 3500 days is incorrect.  Previously, both AlexH and J. Fingas estimated the 7 stage binary takes about 4500 days.  With some further optimization of the stages, I come up with around 4250 days for this method.
IP Logged
SWF
Uberpuzzler
*****





   


Posts: 879
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #124 on: Oct 28th, 2002, 9:59pm »

The method with the lowest mean number of days that I have found is 3536 days.  The technique is similar to the 2 stage methods discussed earlier, and the duration falls in the range estimated by AlexH.  I implemented a simulation of the details to accurately estimate the number of days.  This value for the mean number of days was obtained after simulation of over a million cases, and should be accurate to within a day.
 
Stage 0 involves defining who is responsible for counting.  One prisoner becomes the primary counter, and is given the task of collecting a certain number of counts, the primary count, in stage 1.  The secondary counters are responsible for collecting a number of counts in stage 1 that is not necessarily the same as the primary count.  In stage 2 the primary counter collects signals from the secondary counters who have succeeded in stage 1.  Stages 1 and 2 are repeated until the primary counter's count reaches 100.
 
Two different approaches both give 3536 days:  a primary count of 12, and eight secondary counters who count to 11; or a primary count of 10 with ten secondary counters who each count to 9.  Using a primary count of 10 and nine secondary counters who each count to 10 is only slightly worse.  The method of determining who is a counter in Stage 0, typically gives the primary counter one extra count over the rest and takes advantage of having the primary count be one greater than the secondary count.  Establishing counters in Stage 0 saves only about 70 days over starting with pre-established counters, but the problem is to find the minimum, so every day saved counts.  I think there is still some room for improvement.
 
There are a few tricky details in such things as dealing with cases when somebody is reponsible for acting as a counter twice, and ways of reducing the chances of this happening, especially in Stage 0.  I can go into the details if anybody is interested.
IP Logged
Pages: 1 ... 3 4 5 6 7  ...  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