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

Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 3:17pm

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





   


Posts: 29
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #75 on: Aug 7th, 2002, 12:54pm »

on Aug 7th, 2002, 12:37pm, AlexH wrote:
I think you don't actually have to start from scratch if you get to the end of the second round with a failure. Just go back to stage one and everyone remembers what they did before, so that only drones who haven't flicked the switch and incomplete counters participate (it would probably be best to have shorter stage times as you go on).

 
Hmm... but there could be some drones who "signalled" in Stage 1, but don't know that they were counted.
IP Logged
AlexH
Full Member
***





   
Email

Posts: 156
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #76 on: Aug 7th, 2002, 1:08pm »

The drones can consider themselves counted if they ever sent a message. All messages must have been recieved except for that one that might waiting on the last day of stage 1. This is why we need to have the person who goes in on that day behave differently. If he isn't an unfilled counter (and thus able to count the message himself), then he takes on the extra duties of that 1 drone whose message was never counted because of the end of stage 1 (in addition to whatever other duties he performs). This actually applies to all stages (so that if the light was on at the end of stage 2, the person who saw it must turn it off and take on the additional role of filled counter in stage 2 the second time around).  
 
Edited to add: We might need slightly more than O(n (log n)^2) due to the way the probabilites work out, but not too much more. Divide the prisoners into one half drones, one half counters. At each new stage make half the counters into drones (and all old drones are completely inactive). The sum of expectation times for success in all stages is O(n (log n)^2) , but we may need to stretch the stages a bit more for each new stage we add in order to control the probability of failure. We can easily bound this stretch by log n giving us O(n (log n)^3), but I think a careful analysis could probably do better. In any case this method is asymptotically much better than the single leader model.
« Last Edit: Aug 7th, 2002, 1:28pm by AlexH » IP Logged
Paul Hammond
Newbie
*





   


Posts: 29
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #77 on: Aug 7th, 2002, 3:31pm »

"All messages must have been recieved except for that one that might waiting on the last day of stage 1"
 
You're right, I had overlooked that.
IP Logged
AlexH
Full Member
***





   
Email

Posts: 156
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #78 on: Aug 7th, 2002, 7:19pm »

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.  
 
If I get a chance later I'll type in a bit of explanation as to why we can achieve O(n (log n)^2) performance overall. The key is to look at the variance of expected time to finish a stage and then use that to show that the amount we have to extend each stage as we increase the number of stages is very small and winds up disappearing in the notation because the total extension to all earlier stages combined is about the same as the extra time needed to add one more stage.
 
I glossed over this problem because I first saw it in a similar version but where we specifically couldn't assume anything about the timing of visits (no 1/day rule).  Its a lot more interesting because of that change. We now have a solution which gives theta(n (log n)^2) expected performance, which is pretty close to the expected (n log n) time it takes for the statement to be true at all. Pretty darn cool  Grin
« Last Edit: Aug 7th, 2002, 7:47pm by AlexH » IP Logged
AlexH
Full Member
***





   
Email

Posts: 156
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #79 on: Aug 7th, 2002, 9:45pm »

There I was minding my own business and I started thinking about this darn problem  Roll Eyes
I wrote a bit of C++ code to describe the algorithm and it turns out the special last day stuff just folds in very nicely and makes it very clear whats happening. Here is the relevant part:
 

public:
      bool haveWeWonYet(){
            return (myCounter & (1 << numberOfStages));
      }
      // goToRoom returns new status of lightOn after prisoner has been to room
      bool goToRoom(unsigned stageBit,bool lightOn){
            if (lastDayInStage){
                  if lightOn
                        myCounter += stageBit;
                  return false;
            }
            if (myCounter & stageBit){
                  if (lightOn){
                        myCounter += stageBit;                              
                        return false;
                  }
                  else {
                        myCounter -= stageBit;
                        return true;
                  }
            }
            else  
                  return lightOn;
            
      }

 
Everyone's counter starts at 1. If the number of prisoners isn't a power of 2, we can correct that just by adding in the leftover (2^m - #prisoners) into some prisoner's initial counter.  
 
Reading code snippets would be easier if tab characters took a bit more room within a tt tag. Is it possible to adjust the default for that at the server?  
 
It seems like it might be possible to do slightly better by using a digit size which grows (slowly) with n instead of a fixed digit size (in this case 2).  
 
edited to add:
The binary method is really pretty IMO, but upon reflection, I think we could get away with a digit around size log n and nudge our asypmptotic performance to O(n (log n)^2 / log log n)
« Last Edit: Aug 8th, 2002, 5:49am by AlexH » IP Logged
pa0pa0
Newbie
*





   


Posts: 16
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #80 on: Aug 8th, 2002, 7:10am »

The very nice "drone" solutions given here have made me start thinking about the problem in a different way.  How about this:
 
Each person starts with one (conceptual) token, and we set up
 
  (a) rules, by which people can transfer some or all of their tokens to each other, and
  (b) a policy, such that the tokens tend to accumulate in fewer hands.
 
Inherent in the rules will be the fact that a person can only transfer tokens by being in the room, so as soon as anyone gets 100 tokens, end of problem.
 
Each day is associated with a power of 2 as follows: take the day mod 64, and associate it with the largest  power of 2 by which it is divisible.  Thus, for example, all odd days are associated with 1, and day number 208 is associated with 16;  and the largest number associated with any day is 64.
 
Because of ascii limitations, we shall write 2eN for 2 to the power of N.  Thus, for example, 2e5 means 32.
 
Now, the rules are very simple:
 
    On a day associated with 2eN, the person in the room may,
    if he has at least 2eN tokens, transfer them all to the next
    person by leaving the light on;  if he chooses not to,  or if
    he doesn't have that many tokens,  he leaves the light off.
 
Next, we need a policy so that the tokens don't go aimlessly wandering from one person to another.
 
Definition: a person's collection of tokens is grouped into blocks of tokens such that each block is a power of 2, and each block is as large as possible.
 
Thus, for example, a person with 40 tokens has a block of 32 and a block of 8;  he doesn't have a block of 16, nor of 4, nor 2, nor 1.
 
Now, the policy is: transfer tokens if and only if you have them as a block.  Thus, a person with 40 tokens will decide to transfer 8 (if the day is correct), or 32 (if the day is correct), but no other number.
 
The effect of this policy is that, considering all the blocks in the system as a whole, the number of blocks never increases, and it decreases by 1 every time that a person receiving a block of tokens already happens to have a block of the same size (since he then automatically coalesces the two blocks into one twice as large).
 
To finish the problem off, we add that when any person acquires 51 or more tokens, he becomes the leader and never thereafter gives any tokens away, but only accumulates them.
IP Logged
Paul Hammond
Newbie
*





   


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

on Aug 7th, 2002, 7:19pm, AlexH wrote:

If I get a chance later I'll type in a bit of explanation as to why we can achieve O(n (log n)^2) performance overall.

 
Alex, I would be interested to see that.
 
(bear in mind that, while I understand your terminology, I am not a Computer Scientist, so if you could aim it at the "mathematically literate layman", that would be nice  Smiley )
IP Logged
Jonathan_the_Red
Junior Member
**





   
Email

Gender: male
Posts: 102
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #82 on: Aug 8th, 2002, 9:23am »

on Aug 8th, 2002, 7:10am, pa0pa0 wrote:
Definition: a person's collection of tokens is grouped into blocks of tokens such that each block is a power of 2, and each block is as large as possible.
 
Thus, for example, a person with 40 tokens has a block of 32 and a block of 8;  he doesn't have a block of 16, nor of 4, nor 2, nor 1.
 
Now, the policy is: transfer tokens if and only if you have them as a block.  Thus, a person with 40 tokens will decide to transfer 8 (if the day is correct), or 32 (if the day is correct), but no other number.

 
In other words, treat each prisoner's tokens as a binary number. Each day is associated with a single binary bit. If the prisoner's binary token count has that bit set, flip it to 0 and pass it to the next guy.
 
Quote:

To finish the problem off, we add that when any person acquires 51 or more tokens, he becomes the leader and never thereafter gives any tokens away, but only accumulates them.

 
I like this idea, and I think it has possibilities. Unfortunately, I ran some simulations, and it turns out that it has an average escape time of about 2,500 years. The problem is that larger blocks (especially blocks of 32) move very, very slowly. Maybe there's some way to improve it.
IP Logged

My arcade cabinet
Paul Hammond
Newbie
*





   


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

Perhaps you could use stages with this method too, because after a while there will probably be no 1-blocks left. So in Stage 2, the day-number scheme would go 2-4-2-8-2-4-2-16 etc. Stage 3 would assume that all the 2-blocks have disappeared, and so on.
IP Logged
AlexH
Full Member
***





   
Email

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

Only have a minute right now, but:
Paul-- I'll try to post that proof later today.
 
pa0pa0--Thats an interesting idea to explore but I think it has some fundamental problems. If I understand you, you're sending the same sorts of messages as in the binary stages solution but you're interleaving all the sending/receiving instead of breaking things into long stages where the same bit position is traded. Think about how long it takes to send the last few messages for any given bit position. For example lets say we're down to having the last 2 prisoners with 1 bits in position 1 and we need them to combine. These 2 bits only combine when one of the prisoners enters 1 day, and the other enters the next. Now which prisoner is holding these bits will shift around, but at each time there will be 2 prisoners with such bits and the odds of getting 1 after the other is 1 in (n choose 2) and it has to happen on a day with the right label, which is another 1 in (log n).  
IP Logged
AlexH
Full Member
***





   
Email

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

Here is the argument for the binary stages method being O(n(log n)^2). I think its not quite as good as a log n style digit size asymptotically,  but its a great deal prettier in terms of implementation. Its also fairly parsimonious about certain things which weren't asked for but which I find kind of interesting. If we were concerned about wearing out the light bulb with excessive switching then binary would be very good. It takes < 2n flicks if it succeeds in the first pass (and only slightly more if it doesn't) putting it about even with the leader model (while being much faster). We could also imagine that the light bulb (or whatever 1 bit item we use to communicate) is difficult to access. With the exception of the (log n) stage ending days, no prisoner actually has to go look at the switch other than times when he has to go flip it. So, if r is the number of rounds (i.e. full passes through all stages) in the algorithm then the necessary number of trips to see the bulb room is < 2n + (2r-1) log n. On to the proof ...
 
Assorted basic facts I'll use:  
Variance (or mean) of the sum of independent variables is sum of variances (or means).
Geometric distribution with probability p has mean 1/p and variance (1-p)/p^2.  
Sum of harmonic series H(n) =(approx) ln n  
Sum of series of 1/i^2 (I'll call that H_2(n)) converges to pi^2/6.  
For p in [0,1]: (1-p)^n >= 1 - np
Less than 1/k^2 of a distribution can be > mean + k * (deviation)
ln and log_2 are off by a constant factor so I won't be distinguishing between them.
 
In stage i we start with a = n / 2^i  active prisoners (prisoners with stageBit = 1) --- I only really need that a<=n which is obvious. Every time an active prisoner is selected by the warden, he flips his bit and becomes inactive for the rest of the phase. Each reduction in the number of active prisoners is an independent geometric distribution with p=(a/n) where a is the current number of active prisoners.Observe that the sum of means is nH(a) and the sum of variances is < H_2(a) * n^2, so these are the mean/variance of success of the stage as a whole. Lets say we want at least a 1-1/2log n chance of success for the stage. We can ensure this by waiting (mean) + sqrt(2log n) * deviation < n log n + sqrt(2log n) * n * pi/sqrt(6). This is O(n log n). If we have log n stages, then the odds that all will succeed are at least (1-1/(2log n))^(log n) > 1 - (log n)/(2log n) = 1 - 1/2 = .5 and the total time needed is O(n (log n)^2). Since each pass through all the stages wins with p>.5, we average < 2 passes and the total expected time for success is O(n (log n)^2).
 
Here is the code snippet from my working test model. There is a little extra complexity on stage ending days, but overall its very simple. On 100 prisoners it takes about 4500 with my arbitrarily chosen stage length parameters. On 256 it takes 14800 or so on average and on 4 it takes about 20. Better parameters might improve those times by a bit (probably not more than 10 percent or so). In practice # days is  c(n) * n (ln n)^2 where c(4)<3 and drops as you increase problem size with c(128)<2. I think c drops to something like 1.5 asymptotically with current parameters.
 

      bool prisonerToRoom(int prisoner, bool lightOn){
            currentDay++;
            if (currentDay == stageCutoffs[currentStage]){
            
                  
                  if (lightOn) { // prisoner must absorb unreceived message
                        myCounter[prisoner] += stageBit;
                  }
                  stageCompleted(); // stageBit changes here
 
                  // commence the next stage  
                  if (myCounter[prisoner] & stageBit){
                        myCounter[prisoner] -= stageBit;
                        return true;
                  }
                  else  
                        return false;
            }
            else if (myCounter[prisoner] & stageBit){
                  if (lightOn){
                        myCounter[prisoner] += stageBit;                              
                        return false;
                  }
                  else {
                        myCounter[prisoner] -= stageBit;
                        return true;
                  }
            }
            else  
                  return lightOn;      
      }
 

Edit: corrected a typo.
« Last Edit: Dec 7th, 2002, 3:03pm by william wu » IP Logged
Ilia Denotkine
Guest

Email

Re: How to Solve 100 prisoners & Light bulb?  
« Reply #86 on: Aug 9th, 2002, 2:00pm »

well, my idea is this:
 
the first prisoner breaks the light bulb and puts all the fragments in one pile, but one in an other one. the next visitor (unless he has been in the room before) puts an other fragment in the second pile. When someone sees that there is exactly 100 fragments in the second pile, they can all be set free.
 
I guess my idea could make the most optimal solution Grin.  
 
 
Only my brother said that if the guardians of the prison see the light bulb broken, they will replace the light bulb AND the prisoners (or kill them) Lips Sealed.
 
By the way, who would want some bright prisonersfreeHuh
IP Logged
Don Rowe
Guest

Email

Re: How to Solve 100 prisoners & Light bulb?  
« Reply #87 on: Aug 9th, 2002, 3:31pm »

I think you do it like this, although the question is a bit ambiguous:  Assume that the order the prisoners go into the room is the same each day.  Therefore the instructions to each prisoner are, if you enter the room on the first day, toggle the light, and remember whether it was on or off when you entered, which constitutes the first bit (lsb) in your prisoner order number.  The next day, only toggle the light if the light was on when you entered on the previous day, and remember whether the light was on when you entered, which is the next bit in your number.  Keep going all week, and each prisoner will have a number.  One prisoner's number will be 100 (110000b), and he's the guy.  One caveat - the light will still be on at the end of some days, and if it isn't reset, the prisoners whill have to figure out and remember which, and flip their numbering bits accordingly.
IP Logged
AlexH
Full Member
***





   
Email

Posts: 156
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #88 on: Aug 10th, 2002, 12:02am »

Don I think you might have misread the problem. Only one prisoner goes in each day, and he is selected at random so there is no pattern to the order in which the prisoners enter the room.
IP Logged
Paul Hammond
Newbie
*





   


Posts: 29
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #89 on: Aug 10th, 2002, 12:32am »

Thanks for posting that explanation, btw. I totally agree with you about the elegance of the binary method, it's really nice. Would almost be a shame to use a larger digit size even if it is faster; it gets messy then.
IP Logged
AlexH
Full Member
***





   
Email

Posts: 156
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #90 on: Aug 10th, 2002, 8:34pm »

Sadly, the universe doesn't seem to reward beauty in this case. The approx log n digit solution does beat the binary solution, giving O(n (log n)2/log log n) and winning out even in practice. For 100 prisoners its a close run thing between [5,5,4] vs [10,10]. I don't have a full simulation for the variable digit but I do have a statistical analysis simulation (which you need as part of the simulation anyway since you need to know how long to make the stages). [5,5,4] saves about 330 some days in sum of expectations vs [10,10], but it has to pay for the extra stage in terms of buying greater error tolerance and in gaining less from an early victory in the final stage. Until I have a full simulation, (assuming I get the time to make one  Undecided) I won't know if it wins or not but they will be very close, and both a bit faster than binary.
 
As n grows you can see the advantage of the log n digit solution kick in. For example with 4096 =(approx) e8.3 prisoners using [8,8,8,8] beats binary by about a factor of 2, and also beats [16,16,16] by a factor of 1.7 or so.
IP Logged
Jeremiah Smith
Full Member
***



Beep!

   


Posts: 172
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #91 on: Aug 12th, 2002, 11:18pm »

You're all wrong. What the prisoners need to do is start a riot during their meeting in the living room, overpower the guards, and escape that way.
 
Sometimes, it's best to think outside the box.
IP Logged
Dave Lockwood
Guest

Email

Re: How to Solve 100 prisoners & Light bulb?  
« Reply #92 on: Aug 14th, 2002, 4:16am »

I have a solution - the catch being it would take rather a long time to carry out (but then that's implied in the question - if the warden only picks prisoners at random, then it could take forever before all 100 prisoners have been to the room).
   
The solution is split into two phases - the first 100 days, and then the rest of time (!!!) The reason for this will hopefully be evident in the explanation.
   
The light is initially off.  
First  100 days:  
Everyone follows the same set of instructions:  
The first time you enter the room, do not toggle the switch. In the exceedingly unlikely event that it is day 100 and the light is off - go tell the warden it's party time!
If you enter the room a second time (during the 100 days) - switch the light on if it is off. If it is already on, do nothing.  
Once the light is on, no one switches it off during the rest of the 100 days.  
Therefore, only  one person  switches the light on during the 100 days - this person is now "The Counter" and is the only one who can eventually assert that all 100 prisoners have been in the room. On  day "n" when The Counter switches on the light, The Counter knows for certain that (n-1) prisoners have been to the room (1 prisoner per day, no repeat visits by anyone up until today).  
If it is day 100, switch off the light.  
   
Rest of time:  
If you entered the room during the first 100 days and the light was off: Do nothing - you've already been counted.  
If you entered the room during the first 100 days  only when  the light was on, or if you didn't enter the room during the first 100 days:  The next time you enter the room when the light is off, switch it on. On all subsequent visits, do nothing. 
If you are The Counter and you enter the room when the light is on, switch it off and add 1 to your prisoner count. When the prisoner count reaches 100 - go tell the warden it's party time!
   
After day 100, The Counter is effectively counting the other prisoners one at a time so that he  is certain that  his tally of 100 is correct.
Before day 100 - this is an attempt to optimise the selection of The Counter as the person with the most useful information ( i.e. starting with a count greater than 1).
IP Logged
AlexH
Full Member
***





   
Email

Posts: 156
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #93 on: Aug 14th, 2002, 4:31am »

That the modified leader solution first proposed in this thread by Salem. On 100 prisoners randomly selected it will take 9000 or so days on average. The slightly more involved methods discussed more recently will cut that to somewhere in the ballpark of 3500.
IP Logged
biwema
Newbie
*





10470799 10470799    


Posts: 5
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #94 on: Aug 19th, 2002, 7:50am »

Hi everybody,
 
The leader solution seems to be quite a good approach. When we have 10 leaders, which count up to ten each, they have to visit the room at least for ten times in the first stage. The same happens at stage 2, where the master leader has to visit the living room at least 9 times.
Using [4,5,5] the situation gets a bit better, but not much. The main disadvantage of this solution is, that we have to repeat all three stages, if the first round is not successful (for example, if stage 1 is chosen too short).
 
My Idea is to use a binary approach with 6 stages, where the counters are not predefined, yet.
During the first stage everyone toggles the light, when he enters the room the first time. So we have finally 50 people, who counted up to 2. During the first 70 or so days, this works much faster than the case where the counters are already defined because the light is switched almost every day.
 
During stage 2, everyone, who turned the light off, switches the light during that stage. Everyone, who turned the light on during stage 1, does nothing.
 
Border effect: If after stage 1 the light is on, the first person of stage 2 turns the light of and remembers to toggle it next time the stage 1 is active. If that person has not been to the living room yet, he leaves the light on instead (that means, that he turns off the light like in stage 2, becoming a leader and switches the light on again to be counted as stage 2 member).
So, the border effects of all stages are counted by some people even if they are not counters any more.
 
In stage 6, chunks of 32 are combined to a piece of 64. This person, who has the 64 chunk, tries to find the remaining 32 piece by switching it off during stage 6. Besides that, he also tries to switch of a 4 chunk in stage 3. After having found both of them (the order does not matter), he declares that everyone has been to the living room.
 
The length of the different stages need to be defined during the meeting, we cannot do that later. I haven’t run any simulation, but I recommend a length of 300 to 400 days per stage during the first round of 6 stages.
 
For the following rounds, I think 100 to 200 would be appropriate. They cannot be much shorter, otherwise it is not very likely that the chunks merge. In that case the border effect carry bits just move from one person to another. If everything goes optimal, it would take 2550 days (at 350 days during round 1, 150 days after).
Unsuccessful stages add 900 days in that case.
 
It would be interesting to see the expectation of some simulation results when varying the stage length of round 1 around [250, 300, 350, 400, 450] and the following rounds [75, 100, 150, 200].
Is it possible to reach a value below 3000 or even 2500 days?
 
Any ideas?  
IP Logged
Paul Hammond
Newbie
*





   


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

Quote:
This person, who has the 64 chunk, tries to find the remaining 32 piece by switching it off during stage 6. Besides that, he also tries to switch of a 4 chunk in stage 3.

But how will the person know, during stage 3, that he is going to be the person who gets the 64-chunk in stage 6? He will have to get to 64 first, and then wait for the next stage 3, which defeats the object of reducing the binary method to 6 stages.
IP Logged
AlexH
Full Member
***





   
Email

Posts: 156
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #96 on: Aug 19th, 2002, 12:05pm »

Biwema, did you read this thread? I proposed the binary method you're referring to back on the 7th. As it turns out the actual optimal algorithm (as far as I know) is one where the "digit" size of the counters grows as log of the number of prisoners. That method achieves O(n* (log n)2/log log n), while binary only achieves O(n*(log n)2). For the binary algorithm it makes the most sense to have the stages grow shorter in the first round as the expected number of messages to be sent is reduced, and then have relatively short stages in all future rounds. The way you defined the stages so that you have 6 stages instead of 7 was a bit too loose. The person who gets to hold the 64 won't know he is the person who gets to hold the 64 until the final stage, which means he didn't know to pick up an extra 4 in the 3rd round. So you have to have determined by the 3rd round at the latest who will eventually pick up the 64. This means at a minimum he will have to behave differently in the 3rd,4th,5th,6th rounds and you pay a price for that in terms of the time to finish of those rounds. This is essentially using a [2,2,2,2,2,3] solution with a slight twist of the extra 4 from round 3.  
 
As for 3000 days no I don't think its possible. Typical times for the binary method in my simulation were 4500 days. A small amount could be shaved by parameter tuning, but much less than 1500 days. The sum of expected times for success for the 7 stages of binary is 2309 days, but there is also a lot of time lost either lengthening the initial stages or going through more rounds of short stages in order to get completion.  
 
I didn't implement a full variable digit solution but from looking at expectations and deviations I believe binary is slower than either the 3 digit [5,5,4] or 2 digit [10,10], which are both somewhere in the 3300-3800 ballpark.  
 
Edited to add: Paul snuck in on me  Tongue that will teach me to be so longwinded.
« Last Edit: Aug 19th, 2002, 12:06pm by AlexH » IP Logged
AlexH
Full Member
***





   
Email

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

For reference here is the statistical data for the 7 stage binary.
 

Round 0   mean: 518.737752   deviation: 125.821704
Round 1   mean: 449.920534   deviation: 125.703647
Round 2   mean: 385.441972   deviation: 125.246098
Round 3   mean: 325.156233   deviation: 124.236879
Round 4   mean: 271.785714   deviation: 122.484427
Round 5   mean: 208.333333   deviation: 118.438920
Round 6   mean: 150.000000   deviation: 111.130554
sum of Means: 2309.375537   deviations: 853.062228
IP Logged
biwema
Newbie
*





10470799 10470799    


Posts: 5
Re: How to Solve 100 prisoners & Light bulb?  
« Reply #98 on: Aug 20th, 2002, 5:53am »

Yes, AlexH, I have read the post from Aug 7th. Actually it gave me the idea of my variation. I agree that [4,5,5] algorithm is a bit faster because of the smaller number of stages. Nevertheless, I still prefer the binary solution because of the dynamic assignment of the counters.
If we use 25 counters who count up to 4 each (including themselves), a person can only be counted, when a counter (and they are more rare) comes to the room. Therefore that stage takes much longer (but I agree that there are fewer stages).
When we use the binary approach, a person becomes a counter if the light is on and not otherwise. So, at the beginning of the stage almost every day someone is counted.
 
As Paul and Alex have noticed correctly, the master counter can get the 4 chunk only in the second round because he didn’t know before, that he will become the master counter. I try to live with that.
So, we have several possibilities:
One approach is to make stage 1 and 2 a bit shorter, that it is very probable that at least 96 people are counted, but not necessarily 100 (that shifts the expected value quite a bit). In the second round these people can be collected.
The other approach is to start the second round with stage 3.
 
Now, Alex computed some expected stage lengths that we can tune the length of the different stages. They need to be chosen quite carefully because the penalty is 900 or more if not everyone visits the room in the first round.
 
Quote:
Round 0   mean: 518.737752   deviation: 125.821704  
Round 1   mean: 449.920534   deviation: 125.703647  
Round 2   mean: 385.441972   deviation: 125.246098  
Round 3   mean: 325.156233   deviation: 124.236879  
Round 4   mean: 271.785714   deviation: 122.484427  
Round 5   mean: 208.333333   deviation: 118.438920  
Round 6   mean: 150.000000   deviation: 111.130554  
sum of Means: 2309.375537   deviations: 853.062228

 
In that case I suggest these stage lengths:
Round1: [550,500,424,375,350,300] sum 2500
Round2: [150,150,150,150,150,150]
 
In round1/stage1&2 550 and is more than the mean and therefore quite probable that everyone is counted. If not, it is not a problem either because we need one round later, only. The remaining stages are then used to combine the 24 4-chunks to one 96. Stage 6 needs to be a little bit lucky that one counter can find the other two 32 chunks. It is like a combination of round 5 and 6 in Alex’s table. First we have to wait until 2 of the three 32 chunks enter the living room, then the second of them has to wait until the other one has been to the room as well (150 days).
In round 2 we can collect the last 4-chunk (if necessary) and announce it. If one 32 chunk is still missing, the master counter has to wait another 600 days.
IP Logged
AlexH
Full Member
***





   
Email

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

Ok. Sorry for being a bit snippy there but I got the impression that binary stages with dynamically chosen counters was what you were calling your idea, rather than just the modification to 6 stages instead of 7.  
 
In regards to the 6 stage idea I think you have a problem. In my estimation the best way to reduce to 6 stages would be to identify a special player in advance who is in charge of collecting the extra 4 and the 32s. The method you propose which always requires a second round is almost certainly slower than the original 7 stage method. Also your stages are going to be too short IMO, especially the 150 for later rounds.  
 
For reference here are the formulas from my binary simulator. For the first round:

meanEstimate[i] + (.7 + .5 * sqrt(stages)) * sqrt(varianceEstimate[i])

For later rounds:

meanEstimate[stages-1] + (.5 * sqrt(stages)) * sqrt(varianceEstimate[stages-1])

the "stages-1" stage is always a 2 player round in my simulation, so thats shorthand for expected time and variance for 2 players to talk.
meanEstimate and sqrt(varianceEstimate) are the values I posted above. I'll see if I can do a test run with your numbers to compare total time.
IP Logged
Pages: 1 2 3 4 5 6  ...  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