wu :: forums « wu :: forums - 100 prisoners & a light bulb » Welcome, Guest. Please Login or Register. Dec 4th, 2021, 1:59am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: Grimbal, towr, Icarus, Eigenray, SMQ, ThudnBlunder, william wu)    100 prisoners & a light bulb « Previous topic | Next topic »
 Pages: 1 ... 14 15 16 17 18  ...  25 Notify of replies Send Topic Print
 Author Topic: 100 prisoners & a light bulb  (Read 160967 times)
mattian
Senior Riddler

Gender:
Posts: 404
 Re: 100 prisoners & a light bulb   « Reply #375 on: Mar 20th, 2005, 6:50pm »

That's two for two!

Captain Caveman's scheme checks out in the model.

Based on 10000 iterations, A complete set of 100 CaptainCavemanPrisoners escaped after an average 10415.1657 days - which compares very nicely to the expectation of 10418.

Here is the definition of the CaptainCavemanPrisoner.  By the way, if anyone spots the trend (given that I haven't provided documentation yet) in the definitions of these prisoner models, feel free to write test code and send it to me so that I can plug it into the model.

CaptainCavemanPrisoner.java
`  /** Captain Caveman - Jul 24th, 2002, 2:46am    * Ok, here's 2 i snagged quickly from /. that I like.    *    * 1:  Designate 1 person to turn the light off.  Everyone else, on your    * first time in the room, IF THE LIGHT IS OFF, turn it on.  (Otherwise,    * leave it on.)  After the designated person turns it off 99 times (or    * 100, if he turns it off for himself...), he can demand their freedom.    *    * This works even if they can't see the bulb from their cells and is    * rather elegant.    */    package com.monahansen.prison;    public class CaptainCavemanPrisoner extends LeaderElectingPrisoner  {   public CaptainCavemanPrisoner(int id, int totalNumberOfPrisoners)   {    super(id, totalNumberOfPrisoners);      if (this.id == 0)    {     this.leader = true;    }    else    {     this.leader = false;    }   }     public boolean drawConclusion(IBooleanSwitch lightBulb, long currentDay)   {    boolean conclusion = false;      do    {     // initialise light bulb to off state on day 1     if (currentDay == 1)     {      lightBulb.setState(false);     }       // if the current prisoner is the leader (id=0), and the light is on, collect token and switch off light     if (this.leader)     {      if (lightBulb.getState() == true)      {       this.tokenBalance++;       lightBulb.setState(false);      }        // if the leader has all the tokens, then declare it.      if (this.tokenBalance == this.totalNumberOfPrisoners)      {       conclusion = true;      }        break;     }       // if current prisoner is not the leader, and the light is off, deposit token and switch on the light     if (this.tokenBalance == 1)     {      if (lightBulb.getState() == false)      {       this.tokenBalance--;       lightBulb.setState(true);      }      break;     }    } while (false);      return conclusion;   }  }  `
 « Last Edit: Mar 20th, 2005, 6:54pm by mattian » IP Logged
mattian
Senior Riddler

Gender:
Posts: 404
 Re: 100 prisoners & a light bulb   « Reply #376 on: Mar 20th, 2005, 8:10pm »

Well Icarus, your statement that SJBrown's scheme would take more than 280 years, was accurate.  In fact it would take longer even than 8000 years.

The simulation for 100 SJBrownPrisoners yielded a result of 2986741.59 after 100 iterations.  It will take over 10 hours to run 10000 iterations under this scheme, so 100 (which took 6.5 minutes) will have to do for now.

Update: An overnight simulation of 10000 iterations of 100 SJBrownPrisoners yielded a result of 3005483.0076.

SJBrownPrisoner.java
`  /** sjbrown - Jul 25th, 2002, 10:09pm    *    * I think I've found another solution.  (the only other two so far were    * the "Leader" solution and the one where it's off on the 101st (or    * 201st or 301st ...) day. )    *    * 100-day Months Pretend every month has 100 days.  Each prisoner is    * assigned a day of the month.  You only switch on the light if you're    * in the room on your day, otherwise you switch the light off.  If the    * light is on when you go in the room, you know prisoner d has been in    * the room.  When you've seen the light on on *every* day of the month,    * you know every prisoner has been in the room.    *    * badabing.DOT    */    package com.monahansen.prison;    public class SJBrownPrisoner extends RegisterKeepingPrisoner  {   public SJBrownPrisoner(int id, int totalNumberOfPrisoners)   {    super(id, totalNumberOfPrisoners);      register[id] = true;   }     public boolean drawConclusion(IBooleanSwitch lightBulb, long currentDay)   {    boolean conclusion = false;      do    {     // initialise light bulb to off state on day 1     if (currentDay == 1)     {      lightBulb.setState(false);     }       // if the light is on, mark yesterday's prisoner off in the register and reset the light to off     if (lightBulb.getState() == true)     {      this.register[(int)((currentDay - 1) % totalNumberOfPrisoners)] = true;      lightBulb.setState(false);     }       // if the register is full, then everyone has visited.     if (this.registerFull())     {      conclusion = true;      break;     }       // if today represents a prisoner that this prisoner can claim has visited, turn on the light     if (this.isKnownToHaveVisited((int)(currentDay % totalNumberOfPrisoners)))     {      lightBulb.setState(true);      break;     }      } while (false);      return conclusion;   }     public boolean isKnownToHaveVisited(int prisonerId)   {    boolean result = false;      if (this.id == prisonerId)    {     result = true;    }      return result;   }  }  `
 « Last Edit: Mar 21st, 2005, 3:17pm by mattian » IP Logged
mattian
Senior Riddler

Gender:
Posts: 404
 Re: 100 prisoners & a light bulb   « Reply #377 on: Mar 20th, 2005, 8:37pm »

Okay, S. Owen's scheme also looks pretty accurate.  The SOwenPrisoner simply extends the SJBrownPrisoner and checks his register to find a match rather than just looking at himself.

A sample run of 1000 iterations using 100 SOwenPrisoners yielded an average escape time of 91957.838 days (~250 years) and execution time was about 2 minutes.

Update: A 20 minute simulation of 10000 iterations of 100 SOwenPrisoners yielded a result of 91980.523 days.

SOwenPrisoner.java
`  /** S. Owen - Jul 26th, 2002, 10:11am    *    * I believe I have the answer. It does not assume things that probably    * aren't implied by the problem, like that the prisoners can see the    * light bulb from their cell, or that they can gather after the first    * day.    *    * The idea is that the prisoners will use the state of the light switch    * to (gradually) communicate information about who has been in the    * cell, from one day's prisoner to the next, until someone knows for    * sure that they've all been in there.    *    * The night before, they gather and assign themselves numbers from 0 to    * 99. They then agree on the following rules for what to do in the room:    *    * 1) Let D be the current day. If you know that prisoner # D(mod 100)    * has been in the room, leave the light on. If you do not know that,    * leave it off.    * 2) If the light was on when you came in, then you know that prisoner    * (D-1)(mod 100) has been in the room before - remember that.    *    * For example, if I am prisoner #59, and go in on day 845, and I see    * the light on, I know that #44 has been in there. Furthermore, if I    * know that #45 has been in somehow, then I leave the light on to    * spread that info to the next day's prisoner.    *    * This process only gets started when some prisoner X goes in on a day    * that is equal to X, modulo 100 (i.e., #33 goes in on day 433, and    * since he obviously knows that #33 has been in the room since he's    * there now,  he leaves the light on. If tomorrow, #78 walks in, now    * #78 knows that too).    *    * Eventually the info will spread enough so that someone knows for sure    * everyone has been in the room.    *    * I ran a little simulation, and with 100 prisoners, it takes them    * about 95,000 days on average to know they've all been in there    * (though on average they will all have visited after about 450 days).    */    package com.monahansen.prison;    public class SOwenPrisoner extends SJBrownPrisoner  {   public SOwenPrisoner(int id, int totalNumberOfPrisoners)   {    super(id, totalNumberOfPrisoners);   }     public boolean isKnownToHaveVisited(int prisonerId)   {    boolean result = false;      if (register[prisonerId])    {     result = true;    }      return result;   }  }    `
 « Last Edit: Mar 21st, 2005, 3:57pm by mattian » IP Logged
mattian
Senior Riddler

Gender:
Posts: 404
 Re: 100 prisoners & a light bulb   « Reply #378 on: Mar 21st, 2005, 5:19pm »

SalemPrisoner did not disappoint, coming in at 25.6 years (as expected).  10000 runs of 100 SalemPrisoners yielded a result of 9367.4935 days.

SalemPrisoner.java
`  /** Salem - Jul 28th, 2002, 9:49am    *    * Here is a modified solution which could cut down on the expected time    * it would take for the prisoners to get out.    *    * It is based on the "leader" idea, but you get a good jump start Smiley    *    * The first person to go in the room 2 times is the "leader".    * He turns on the light. If he goes in for the second time on day 65,    * then he knows 64 prisoners have been in the room.    * Nobody does anything else until the 100th day.    *    * Note: this first set of 100 days creates four groups of prisoners:    * Group A) inmates that entered the room for the first time and the    * light was off.    * Group B) inmates that entered the room for the first time and and the    * light was on    * Group C) inmates that did not enter the room    * Group D) the leader who entered the room twice and turned on the    * light.    * The person that gets picked on the 100th day has a special job. If    * they are from group A or group D, they turn off the light. If they    * are from group B or C, they leave the light on.    *    * After the first 100 days, the solution is just like the "leader"    * solution. Here is what each group does the next time they are    * selected:    *    * Group A) nothing, they have already been counted    * Group B) turn on the light the next time they enter the room and the    * light is off    * Group C) turn on the light the next time they enter the room and the    * light is off    * Group D) turn off the light if the light is on, decrement the number    * of people left to enter the room.    */      package com.monahansen.riddles.hundredprisoners.prisoners;    import com.monahansen.riddles.hundredprisoners.prison.IBooleanSwitch;    public class SalemPrisoner extends CaptainCavemanPrisoner  {   public SalemPrisoner(int id, int totalNumberOfPrisoners)   {    super(id, totalNumberOfPrisoners);   }     public void assessLeadership()   {    this.leader = false;   }     public boolean drawConclusion(IBooleanSwitch lightBulb, long currentDay)   {    boolean conclusion = false;      do    {       // initialise light bulb to off state on day 1     if ((currentDay == 1) || (currentDay == (this.totalNumberOfPrisoners + 1)))     {      lightBulb.setState(false);     }       // if the day is less than snowball duration, do snowball     if (currentDay <= this.totalNumberOfPrisoners)     {      // if the light is on during this period, just leave      if (lightBulb.getState() == true)      {       break;      }        // if you have not been before, remember that you've been here now, and leave      if (this.tokenBalance == 1)      {       this.tokenBalance = 0;       break;      }        // if you're here for the second time, become the leader and collect tokens for the number of days past      if (this.tokenBalance == 0)      {       this.leader = true;       this.tokenBalance = (int)((currentDay - 1) % this.totalNumberOfPrisoners);         //turn the light on to signal other prisoners that they're still active.       lightBulb.setState(true);       break;      }     }       conclusion = super.drawConclusion(lightBulb, currentDay);      } while (false);      return conclusion;   }  }  `
 « Last Edit: Mar 21st, 2005, 5:20pm by mattian » IP Logged
SWF
Uberpuzzler

Posts: 879
 Re: 100 prisoners & a light bulb   « Reply #379 on: Mar 21st, 2005, 7:30pm »

Some clarification to my recent post.  Based on rmsgrey's terminology, the beginning of the method I used to get 3536 days was not really "snowballing", maybe "dynamic allocation" is a better term. Also, in those runs not all of the prisoners doing the counting, count to the same number unless the number of counters evenly divides into 100.  The workload was distributed as evenly as possible: some count to n others to n-1.

The variation in number of days can be quite large. The single leader method has a standard deviation of around 1045 days, so over a million simulation runs would be required for an accuracy within a day. After thinking some more about it, when my simulations came up with 10391, that was probably inaccuracy from using just a couple thousand runs rather than a different method. That value was made while generating a large table of different conditions for use in identifying the most fruitful approach, so it was not an extensive run. I do see that the analytical solution for a single predefined leader with a total of N prisoners requires approximately,
N*(N-1+gamma+ln(N-1)) days
giving 10417 with n=100 (gamma = Euler's constant = 0.577...), or exact value can be found by adding up a series.

The method with a time of 3536 days had a standard deviation of 607 days.

A particular instance I was thinking of that should be further checked is the claim of around 3500 days for with 7 stage binary. I commented on it here.
 « Last Edit: Mar 21st, 2005, 9:14pm by SWF » IP Logged
Icarus
wu::riddles Moderator
Uberpuzzler

Boldly going where even angels fear to tread.

Gender:
Posts: 4863
 Re: 100 prisoners & a light bulb   « Reply #380 on: Mar 21st, 2005, 8:09pm »

on Mar 20th, 2005, 4:17pm, mattian wrote:
 Rather than wait 3x10^31 millenia for my computer to finish running a single iteration, I modified the problem for the BanderSnatchPrisoner.

Some people are so impatient! Thanks for giving some reasonably hard numbers to these early efforts. I'll have to update that history, but will wait to see what else you come up with before bothering to do so.

I hope to have my promised summary ready to post tomorrow. but it may take until Thursday - and even that is assuming nothing else comes up to distract me. (like last week) The big hold-up is that I am trying to translate all the schemes into a common idiom, and sometimes it can be difficult to do.
 IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
mattian
Senior Riddler

Gender:
Posts: 404
 Re: 100 prisoners & a light bulb   « Reply #381 on: Mar 21st, 2005, 9:31pm »

Icarus, I think your summary might help me out a bit.  Java's not very good at true multiple inheritence and these problems seem to be borrowing from each other in a less than tree-like fashion.  Perhaps with some established terms and conventions, I can rework the class hierarchy so that it behaves itself.

I will continue to post results as I implement the prisoner types - but I too have to find the time - it has only taken about 20 minutes to implement each prisoner... not including the time spent to rework the whole prisoner heirarchy each time (since I didn't sit down before hand and map that part out as perhaps I should have done).

Anyway I will try to get some further results up tomorrow.  And when I've finished these, I will drop the jar file here on the forum for public scrutiny.  If I can find the attachment button - I know I've used it for images before, but now I can't find it.  Oh well.

Later.
 IP Logged
Icarus
wu::riddles Moderator
Uberpuzzler

Boldly going where even angels fear to tread.

Gender:
Posts: 4863
 Re: 100 prisoners & a light bulb   « Reply #382 on: Mar 22nd, 2005, 7:36pm »

Okay, here is my promised summary. The numbers are sometimes out-of-date since mattian is reviewing them. I will try to update them sometime soon, but for now I want to get this posted.

As much as possible, I am going to translate the various schemes into a common idiom of what I call virtual items. So I will start off with general definitions and descriptions. Except for specifics of terminology, this will be familiar to anyone who has studied the various schemes. I have tried to stick to established terminologies when I can.:

A virtual item is a conceptual object prisoners may consider themselves as possessing, and which they pass by means of the light. Virtual items represent messages that the prisoners exchange. Three kinds of virtual items come into play in these schemes:

• markers are virtual items that can be copied. A prisoner who passes a marker also retains it in his own inventory.
• tokens are virtual items that cannot be copied. A prisoner who passes a token removes the token from his inventory.

Because tokens and markers represent messages, a separate type of token or marker is needed for each message that needs to be passed. In all the schemes thus far suggested, the various messages that need to be passed are each assigned a number k, and the corresponding items are called "items of type k". I will also use "level" for "type" when talking about tokens and badges. Badges also have a type, but in their case, the type indicates what task the prisoner is required to perform. I will also refer to an item of type k as an "item #k".

For example, in the Distribution Scheme, at the initial meeting each prisoner is assigned a number k and is "given" a marker of type k. The marker represents the message "Prisoner #k has visited the room" (which will be true by the time he can actually pass it).

When passing items, the receiving prisoner needs to know what kinds and types of items he is receiving. This is accomplished by breaking the passage of days into (almost) discreet blocks called stages. During each stage, rules tell the prisoners what kinds, types, and amounts of items they can pass and receive, and how the passage is accomplished. Stages come in two general kinds:

• Typical stages are assigned a type, just like items. During these stages, only markers or tokens of the same type can passed, and only one can be passed at a time. Badges are not passed. When a prisoner who is eligible to pass an item is in the room and the light is off, he signals the pass by turning on the light. When a prisoner who is eligible to receive the item enters the room and finds the light on, he adds the item to his inventory. If the item is a token, he also turns the light off.
• Atypical stages follow their own special rules, which differ from scheme to scheme. I will also call atypical stages rounds. (Not for any good reason, just because I've noticed a tendency to do so in my earlier posts, and am not going to bother fighting it! ) Badges can only be passed out at the initial meetings, or during atypical stages.

Stage End: The last prisoner to visit in each stage has to turn off the light if he finds it on, to prevent the first visitor in the next stage from receiving an erroneous signal. This means he must also pick up whatever items are available. Stage rules must always allow for this final-pick up. If the prisoner is unable to use the items directly, he must wait for another stage in which he can pass them on. Since the stage is ending, the prisoner is not able to pass any item, and thus the prisoner beginning the next stage is unable to receive any item. This inefficiency is overcome by letting the stages overlap by 1 day. During this overlap, the first half of the visit belongs to the ending stage, so the prisoner receives any items according to the ending stage's rules, but the second half belongs to the beginning stage, so the prisoner passes items according to its rules. The effect of this is to shorten the length of each stage by 1 day.

The stage length is the number of days the stage lasts. stage order determines when each stage starts and ends. Both are set during the initial meeting, as this is the only time all the prisoners can have the same knowledge. Each stage attempts to accomplish some task. Because of the probabilistic nature of the problem, there is no guarantee that any task will be accomplished in a finite amount of time. If there is only one task to be accomplished in the scheme, then only one stage is needed, and it can be infinite in length. Otherwise, stage lengths must be finite. In order to give the task enough time to be accomplished, and infinite number of stages must be assigned to the same task. If the first fails to accomplish what is needed, the process is continued when the next stage assigned to it comes around. Most commonly, a typical stage for each type of item will occur in a repeating sequence. Each such repetition of the sequence is called a cycle. Atypical stages may be distributed in and around the cycles, though most commonly they occur only at the beginning of the first cycle.
 IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
Icarus
wu::riddles Moderator
Uberpuzzler

Boldly going where even angels fear to tread.

Gender:
Posts: 4863
 Re: 100 prisoners & a light bulb   « Reply #383 on: Mar 22nd, 2005, 7:38pm »

All but one scheme fits the virtual item model. The sole exception is the Complete Cycle scheme (I could make it fit too, but the result is unnatural, and harder to understand than the straight explanation):

Complete Cycle Scheme: BanderSnatch
The days are broken into 100-day cycles. The first prisoner of each cycle turns the light off. No one turns the light on except on their second visit to the room in the cycle. If the prisoner on the last day of the cycle finds the light off, and has not visited before in this cycle himself, he declares that everyone has visited. Just as with stages in the virtual item methods, each cycle may overlap one day with its neighbors, giving an effective cycle-length of 99 days.

This scheme is easy to analyze mathematically. For N prisoners, there are N! ways they can be selected in a cycle without repeats, out of NN total combinations, so the probability of a successful cycle is N!/NN. The success or failure of each cycle is independent of all other cycles, so the expected number of cycles until release is NN/N!. The run-time (expected number of days until release) is (N-1)NN/N!. For N = 100, this is 1.0608 x 1044 days. (In my original number that I quoted in the history, I forgot about overlapping the cycles.)

------------------------------------------------------------------------ ---------------------

Distribution Schemes:

In distribution schemes, the prisoners are assigned numbers from 1 to N (for N prisoners), and for all k, prisoner k is given a marker of type k at the initial meeting. Cycles consist of stages of types 1 through N in order. There are no atypical stages.

Stage rules: During stage k, any prisoner having a marker of type k (initially, only prisoner k) may turn on the light. Everyone who visits during the stage and finds the light on adds marker #k to their inventory if they do not already have it. The last visitor of the stage turns off the light.

Victory is declared when one prisoner has all N markers in his inventory.

The only difference between the various Distribution schemes is stage length. Since the situation is symmetric with respect to the prisoners, within a cycle, all stages have the same length. But stage lengths in different cycles may differ. The schemes will be indicated by a sequence <s1, s2, ...>, where s1 is the common stage length for the first cycle, s2 is the stage length for the second cycle, etc. "..." means that the last stage length is repeated for all future cycles.

<1, ...> sjbrown, S. Owen: Run-time = 91980 days (~ 252 years), based on 10,000 runs.
<s, ...> Paul Hammond, rmsgrey: Run-time ~ 54,000 days for 40 <= s <= 150.
<s1, s2, ...> rmsgrey: Run-time ~ 53,000 days for 200 <= s1 <= 400 and 30 <= s2 <= 70.
<5, ...> mattian: Run-time ~ 50,000 days
(I am leary of this, since it seems at odds with rmsgrey's earlier values. Perhaps someone can double check all these values to see if they are correct.)
 « Last Edit: Aug 8th, 2006, 5:13pm by Icarus » IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
Icarus
wu::riddles Moderator
Uberpuzzler

Boldly going where even angels fear to tread.

Gender:
Posts: 4863
 Re: 100 prisoners & a light bulb   « Reply #384 on: Mar 22nd, 2005, 7:40pm »

Counting Schemes:

Unlike Distribution schemes, there are numerous variations to counting schemes. Instead of markers, counting schemes make use of tokens, and of badges to tell who collects the tokens. In counting schemes, every prisoner is given a token of level 1 (also called a simple token). Some prisoners may also be given extra simple tokens either at the initial meeting, or at later times in the scheme. The total number of simple tokens given out is called the target T, which may be greater than the number N of prisoners. The object of counting schemes is to collect all T simple tokens (or their equivalent) into the hands of a single prisoner. To facilitate movement of tokens, simple tokens are gathered together into groups, which are represented by the creation of higher level tokens. Each higher level token is assigned a fixed number of tokens of the next lower level. When a prisoner has collected this amount of the lower level token, he uses them to create the higher level token. For instance, in Paul Hammond's original scheme, there are 3 levels of tokens. Each token of level 2 is made from 10 simple tokens. Each level 3 token is made from 10 level 2 tokens. Every token has a value equal to the number of simple tokens it is made from. Level 1 tokens always have a value of 1. In Paul's scheme level 2 tokens have a value of 10, and level 3 tokens have a value of 100. Since only 100 tokens exist, only one level 3 token can be made, and it's creator declares victory upon doing so. For this reason, Paul's is a bi-level scheme: once the third level is reached, the scheme ends. A similar pattern is followed by all counting schemes. The highest level token of the scheme has as value the target T, and its creation signals victory, so it does not actually exist within the scheme. For any scheme, the worth of tokens will be expressed by a sequence in square brackets: [n1, n2, ..., nm]. ni is the number of level i tokens required to create a level i+1 token, and is called the level i multiplier. The scheme is called a m-level scheme, and the target is n1 * n2 * ... * nm. So Paul's scheme is represented by [10, 10], and has 100 as its target.

Typical stage rules: Counting schemes may have both typical and atypical stages. In a stage of type k, only level k tokens may be passed. Prisoners who can pass or receive a token are called active. Those who cannot are inactive. With two exceptions, the only people who can pick up a token in a typical stage are those with an unfilled badge of the same level, or the last visitor of the stage. Everyone who has a token of the right level and does not have an unfilled badge is able (and required) to pass a token if the light is off when they visit.

Badges: For stages of level k with leaders, badges of level k are distributed either at the initial meeting, or by special rules during the scheme. The number of level k badges is T divided by the value of a level k+1 token. For each badge, the prisoner holding it is required to collect nk tokens of level k. Immediately upon accomplishing this, he replaces the nk level k tokens with a single level k+1 token. The badge is then said to be "filled". If a prisoner has more than one level k badge, he must fill them separately.
The top level of a scheme can have only 1 badge. This badge is often called the crown. As a general rule, if someone gets a level k badge, it also acts a badge for all lower levels (this requires fewer token passes than giving the lower level badges to some one else). In particular, whoever gets the crown is a leader in all stages, and is sometimes called the "primary leader".

The two exceptions thus far proposed to the badges rule occur when the level multipler for the stage is 2, or else when it is 3 and the stage is the highest level (so there are only 3 tokens of that level to be collected). A stage with level multiplier 2 is called a binary stage. For a binary stage, anyone with a token of the right level is required to pass it at first opportunity, and only those with the same level token can pick it up. When they do, they combine their two tokens to create a token of the next level. In either case – passing or receiving, the prisoner no longer has a token of the right level, and becomes inactive. The top-level stage with multiplier 3 is called a final trinary stage. Only the prisoners possessing the 3 tokens for the level are active, and pass if and only if they have only one token in their possession. Once someone gathers 2 of the tokens, he receives only, until he picks up the third and declares victory.
 IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
Icarus
wu::riddles Moderator
Uberpuzzler

Boldly going where even angels fear to tread.

Gender:
Posts: 4863
 Re: 100 prisoners & a light bulb   « Reply #385 on: Mar 22nd, 2005, 7:41pm »

Typical stages occur in order of increasing levels within cycles. The length of each stage varies from level to level, and from cycle to cycle. The progression of stage lengths will be denoted by a sequence broken up into cycles: <(s11, s12, ..., s1k), (s21, ..., s2k'), ... >. Stage lengths for atypical stages will be denoted by a *. Typical stages in each cycle occur in increasing order of level. A "..." after the last cycle indicate that it is to be repeated indefinitely. For example, <20*, 24*, (2000, 1000, 500, 500), (300, 300, 300, 400), ...> indicates a 4-level scheme starting off with two atypical stages, one of length 20, followed by one of length 24. level 1 stage length is 2000 for the first cycle and 300 for all future cycles. Stages 2, 3, 4 go from 1000, 500, and 500 days respectively in the first cycle to 300, 300, and 400 for all future cycles.

A common atypical stage, called a snowball round can be applied to several schemes. The snowball round occurs at the beginning of the scheme and (for schemes with leaders) passes out a single badge. The prisoner on day 1 leaves his simple token by turning on the light. Later visitors leave their token by leaving the light on. The first prisoner to visit who is unable to leave a token (either because he has been in the room before and no longer has a token to leave, or because he is the last visitor of the stage, or because special rules of the scheme prevent him from doing so) turns off the light and picks up all the tokens left in the room. This number is determined by the day number. If he visits on day k, then he picks up k-1 tokens. In addition, he is also given a badge (usually, the crown). No one is allowed to turn on the light during the snowball round except the prisoner on day 1, so once the light is turned off, the rest of the round is inactive. The effect of the snowball round is transfer a large number of tokens to a single prisoner in just a few days. Unfortunately, it is only worthwhile when a large majority of the prisoners have tokens to leave, which is why it is only done at the start of the scheme.

Multi-badge versions of the snowball round figure significantly in the fastest schemes, and will be described when those schemes are discussed.

[100] <[infty]> Captain Caveman

Captain Caveman quotes this solution from a slash-dot site. The crown is given to a randomly chosen prisoner at the initial meeting. Only he can collect tokens. Everyone passes their token at the first oportunity (the first time they enter the room with the light off).
Its run-time is calculable mathematically: Assume a total of N prisoners. If k prisoners (including the leader) are still active at day D, each has a 1/k probability of being the first active prisoner to enter after this date. Assuming the light is off on day D, the leader's next visit is successful if and only if he is not the first active prisoner to visit after D. So, when k prisoners are active, he has a (k-1)/k probability of having a successful visit. Which means the expected number of visits before success is k/(k-1). Each successful pass reduces the number of active prisoner by 1. So expected number of visits the leader must make is the sum of the expected number of visits with k active prisoners from k=N down to k=2 (once k=1, victory is declared). Decreasing the index k by 1 gives:
expected # of visits = [sum]k=1N-1 (k+1)/k = N –1 + [sum] k=1N-1 1/k

Since there are N prisoners, visits come at an expected interval of N days, giving a run-time of N(N-1) + N[sum]k=1N-1 N/k.
For N=100, this gives 10417.74 days, or 28.52 years.

[100] <100*, [infty]> Salem

This scheme adds a 100 day snowball round. Run-time = 9367 days (25.6 years), based on 10,000 runs.

 « Last Edit: Aug 8th, 2006, 5:14pm by Icarus » IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
Icarus
wu::riddles Moderator
Uberpuzzler

Boldly going where even angels fear to tread.

Gender:
Posts: 4863
 Re: 100 prisoners & a light bulb   « Reply #386 on: Mar 22nd, 2005, 7:43pm »

[100] <29*, [infty]> AlexH

AlexH suggested cutting the snowball round to only 29 days. This results in a run-time of 9321 days, about 46 days shorter than Salem's, based on 10,000 runs.

[10, 10] <(2600, 2700), ...> Paul Hammond

Paul introduced the concept of Multi-stage schemes with this version. As a special rule, if a cycle fails, the next cycle starts over from scratch (everyone gets their original tokens & badges back). 9 badges (level 1) and 1 crown are passed out at the initial meeting.

Mattian (who has supplied most of the numbers above) gives a run-time of 3964 days (~10.8 years) based on 10,000 trials.
AlexH suggests that starting over is not necessary when a cycle fails, and decreasing stage lengths in later cycles. All later schemes incorporate these suggestions.

[10, 10] <(?, ?), (?, ?)...> SWF

SWF reports that he was able to get run-times slightly over 3600 days (9.9 years) with this variation, but does not report what stage lengths he used.

[ 2, 2, 2, 2, 2, 2, 2] <(774, 705, 639, 577, 520, 448, 375), (298, ..., 298), ...> AlexH

In AlexH's Binary Stages scheme, all stages are leaderless, and the target is 128. The extra 28 simple tokens are given to a single prisoner at the initial meeting (who immediately converts them into a token each of levels 3, 4, and 5). (Grimbal and mattian suggest instead having the level 3, level 4, and level 5 token appear in the room on the first day of their respective stages. By my calculations this should add about 9 days to the optimal run-time for a binary scheme over AlexH's method. I suggest having the extra tokens appear on day 2 of the first stage, and a rule be added that no can pass a token if he also possesses a higher level token – he can only receive. I have no estimates on my method at this time).

AlexH reports a run-time of ~ 4500 days
(SWF reports a run-time of 4250 days, but does not give stage lengths, or any other information.)

[ 2, 2, 2, 2, 2, 2, *]  (interweaving stages of length 1) pa0pa0

This is an odd scheme notable for introducing the "token" concept. The target is 100. All stages are leaderless until the single level 7 token (value=64) is constructed. It's constructor is then given the crown and searches for the remaining tokens – he only receives tokens from then on. Once he has collected the remaining tokens (of levels 3 and 6), he declares victory.

Stages in pa0pa0's method are all 1 day in length and are interweaved: If m is the highest exponent such that 2m divides the (day-count modulo 64), then the stage level is m.

While pa0pa0's method has some interesting ideas, it's most important contribution is in the lessons learned department: short stages are a bad idea, making it very hard to pass the higher level counters around. Jonathan_the_Red estimates a run-time of about 2500 years.

[ 2, 2, 2, 2, 2, 4]  <(550, 500, 424, 375, 350, 300), (150, ..., 150), ...> biwema

The crown for stage 6 is assigned in the initial meeting, and the extra 28 tokens are given to the leader. The other 5 stages are leaderless.
No run-time was ever given.

[3, 3, 2, 2, 3]  <(no stage lengths given)> biwema

Target =108. badges for stages 1 and 2 are assigned at the initial meeting. The extra tokens are given to 8 of the stage 1 leaders. The remaining stages are leaderless. No run-time was given.

[5, 5, 4]; [5, 4, 5]; [4, 5, 5]  (no stage lengths given) AlexH, biwema

AlexH hints that the [5, 5, 4] scheme should save about 330 days over the [10, 10] scheme. This would make it the record setter if true, but I don't think it is likely. biwema suggests that all three should perform about the same, but [5, 5, 4] should be slightly faster.

No run-times were given for any of these.

[12, 9] <(2252, 1610), (302, 358), ...>; [10, 11] (no stage lengths given) SWF

SWF reports a run-time of 3600 days for both these methods (stage lengths for the second are probably similar to, if not the same as, those for the first). In both cases, the extra tokens are given out at the initial meeting, 1 each to the secondary leaders (the leaders who did not receive the crown).
 « Last Edit: Aug 8th, 2006, 6:34pm by Icarus » IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
Icarus
wu::riddles Moderator
Uberpuzzler

Boldly going where even angels fear to tread.

Gender:
Posts: 4863
 Re: 100 prisoners & a light bulb   « Reply #387 on: Mar 22nd, 2005, 7:44pm »

[12, 9] <3*, 2* x 8, (2252, 1610), (302, 358), ...> ; [10, 11] <3*, 2* x 10, (???),...> SWF

(The "2* x 8" notation is a shorthand for saying that the 2* stage occurs 8 times.) These schemes are identical to the previous, except the badges and extra tokens are handed out during the atypical stages (one spare token for each badge other than the crown). The crown is handed out in the initial round of length 3. The level 1 badges and spare tokens are handed out 1 each per the length 2 rounds. The special rounds do not overlap with the surrounding stages.

During the crown round, the first visitor leaves his token, but does not touch the light. The 2nd visitor turns on the light if he is able leave another token. The third visitor receives the crown, and one token if the light is off, or two if the light is on. The visitor leaves the light off.

During the badge rounds, the first visitor passes a token in the normal fashion if he can. The second visitor picks up a badge, a spare token, and any token left from the previous visitor.

SWF reports equal performance again between the two schemes. Run-time = 3535.6 days (9.7 years), based on 11 million trials. Std Dev = 607 days, median = 3370 days.

rilgin offers a variation of SWF's badge allocation rounds that was never applied to any scheme, but may improve on SWF's. However before anyone attempted this, gypo proposed an even better idea.

[2, 2, 2, 16] <20*, 8*, 8*, 4*, 4*, 4*, 380+330, 330+300, 300+200, 1650, 500*, 300*, [infty]*> Rezyk

As one might guess for the stats above, Rezyk's scheme is convoluted. The first 20 days are given over to a straight snowball round, in which the crown is given. Since the target is 128, the 28 spare tokens  are also given to the leader (the recipient of the crown).

Following the initial snowball rounds, 5 more snowball rounds are held: the first two for 8 days each, and the rest for 4 days each. In these rounds, the leader is not allowed to pass a token (he can always receive them).

Next comes the typical stages for levels 1, 2, 3, and 4. The 3 binary stages are leaderless, but have special rules for the leader: Each is broken into 2 parts (lengths indicated by the + signs above). During the first part of each stage, the leader is not allowed to pass a token. During the 2nd part of the stages, he may pass a token only if he does not have any lower level tokens.

The level 4 stage is a straight-forward typical stage with only one leader.

Unlike every other multi-level scheme proposed,  Rezyk's does not have cycles. Instead, if the level 4 stage fails to result in victory, Rezyk proposes a process I call Devolution. Starting with the level 4 stage, and in all later stages, only the leader can ever receive a token.
At the start of the next stage, all prisoners with level 4 tokens break them back into two level 3 tokens. For the next 500 days, the leader tries to collect any that he does not already possess. If he fails to collect all of them, then another stage starts, and everyone with level 3 tokens splits them back into two level 2 tokens, and the leader tries to collect these for the next 300 days. Finally, if he still isn't successful, everyone possessing a level 2 token splits it into two level 1 tokens. The leader then attempts to collect all of them, with the stage lasting until he succeeds.

At first glance, Rezyk's scheme seems an unlikely candidate for speed, yet it beat all previous schemes, and to date has only been beaten by one other. This scheme is also notable in that Rezyk introduces the badges and crown terminology with it. He reports a run-time of 3532.0 days (9.7 years) based on 1 million trials. Std Dev = 752 days.
 « Last Edit: Mar 22nd, 2005, 7:55pm by Icarus » IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
Icarus
wu::riddles Moderator
Uberpuzzler

Boldly going where even angels fear to tread.

Gender:
Posts: 4863
 Re: 100 prisoners & a light bulb   « Reply #388 on: Mar 22nd, 2005, 7:45pm »

[10, 10] <4*x10, (2000, 1500), (300, 300), ...> gypo

gypo takes the standard [10, 10] scheme and adds 10 badge allocation rounds of 4 days each to the start. The key behind his method is that he allows leaders to borrow tokens to avoid picking up a second badge. The badge allocation rounds have the following rules:

Day 1) If the visitor has a token, he leaves it in the room (turning the light on). If he does not have a token, but does have a badge, then he borrows a token (leaving him with a negative token count) to leave in the room. If he has neither token nor badge, he receives a badge and leaves the light off.
Days 2 & 3) If the light is off, the prisoner does nothing. If the light is on, and the prisoner has a token or a badge, he leaves a token in the room (borrowing if needed) by leaving the light on. If he has neither token or badge, he turns off the light and picks up a badge and 1 fewer tokens than the stage-day count (1 token on day 2, 2 tokens on day 3).
Day 4) If the light is off, or if the light is on and the prisoner has a badge, he does nothing. If the light is on and prisoner does not have a badge, he turns the light off and picks up a badge and 3 tokens.
Day 5) (This day overlaps with the next stage, so it does not count towards stage length). If the light is on, the prisoner turns it off and picks up a badge and 3 tokens (even if he already has a badge). Otherwise, he does nothing.

The first badge allocated is the crown.

gypo says that the badge allocation rounds collect between 14 and 25 tokens from non-leaders before the typical stages even start. Run-time is 3489 days (9.55 years), based on 1 million trials. Std Dev = 664 days.
 « Last Edit: Mar 22nd, 2005, 7:55pm by Icarus » IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
Leo Broukhis
Senior Riddler

Gender:
Posts: 459
 Re: 100 prisoners & a light bulb   « Reply #389 on: Mar 22nd, 2005, 8:27pm »

on Mar 22nd, 2005, 7:45pm, Icarus wrote:
 Day 1) If the visitor has a token, he leaves it in the room (turning the light on). If he does not have a token, but does have a badge, then he borrows a token (leaving him with a negative token count) to leave in the room.

Must read "potentially leaving him with a negative token count".
 IP Logged
mattian
Senior Riddler

Gender:
Posts: 404
 Re: 100 prisoners & a light bulb   « Reply #390 on: Mar 22nd, 2005, 8:29pm »

Icarus, if this is the summary, I'd hate to see the full document.

Oh wait - I suppose it lives in the 20 pages of this thread.

Wasn't at home tonight - so I haven't implemented any more prisoners yet.  Tomorrow I should have quite a bit of time - assuming I don't spend the whole night reading Icarus' summary - so I should be posting some more results then.

I also have to rework the class/interface hierarchy with some more foresight, but I won't let this slow the publishing of the numbers.
 IP Logged
mattian
Senior Riddler

Gender:
Posts: 404
 Re: 100 prisoners & a light bulb   « Reply #391 on: Mar 22nd, 2005, 8:49pm »

Just a side note on the simulation engine.  I have included an interface which defines a sweep, which can be applied to stage lengths, cycle lengths, initial token balances, or any other numeric quantity whose value has questionable impact on the outcome.  The idea is that by assigning a range of numbers to each of these properties, the simulation will perform a sweep across the full range given, and provide results (at a specified sweep increment and a specified number of iterations per sweep position), ultimately providing a range of results which has surprised me quite a bit so far.  When I was implementing my scheme a few days ago I was sweeping the stage lengths and was expecting the plotted results to look something like a concave parabola - but it was more like a a concave parabola added to a sin wave.

The interface isn't really very versatile yet, but I think it will be a valuable tool in identifying the underlying properties of the schemes.  Coming soon - so don't touch that dial.
 « Last Edit: Mar 23rd, 2005, 7:10am by mattian » IP Logged
Leo Broukhis
Senior Riddler

Gender:
Posts: 459
 Re: 100 prisoners & a light bulb   « Reply #392 on: Mar 22nd, 2005, 11:41pm »

on Mar 19th, 2005, 6:41am, SMQ wrote:
 Sticking with 10 badgers for the moment (one of whom is also the crowner), I found the following series of badge sizes (used in gypo's stage 0) result in an average runtime (over 10,000,000 trials) of 3426:   1st cycle 6 days long, one badge of size 12 awarded (and also the crown) 2nd & 3rd cycles 5 days long, two badges of size 11 awarded 4th - 6th cycles 5 days long, three badges of size 10 awarded 7th - 10th cycles 4 days long, four badges of size 9 awarded.   This solution still uses gypo's stage lengths (2000, 1600, 300, 300, ...) which seem to be close to optimum for 10 badges.

Using the gypo's algorithm as described by Icarus I cannot reproduce his numbers (I get close to 3650), and using these numbers I get close to 3600.

In my implementation I have checks to ensure that the number of outstanding tokens + the sum of costs of ready badges + the cost of the light if it is on is equal to 100, i.e. that no stray tokens appear that can speed things up.  Could you post the program you're using?
 IP Logged
SMQ
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 2084
 Re: 100 prisoners & a light bulb   « Reply #393 on: Mar 23rd, 2005, 7:28am »

In preparing my code for publication I did find one error: it wasn't counting stage 0 days toward the total.  So my tweek to gypo's approach runs in 3473 rather than 3426 as I reported.  Still slightly better (16 days), but not quite as dramatic--oh well.  Anyways, here's the code (in C++; frand(n) returns a random integer evenly distributed over 0 to n-1):

Code:

(edited to change vaiable names to more closely match Icarus' summary)
 « Last Edit: Mar 23rd, 2005, 8:45am by SMQ » IP Logged

--SMQ

SMQ
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 2084
 Re: 100 prisoners & a light bulb   « Reply #394 on: Mar 23rd, 2005, 7:29am »

Code:

(edited to change vaiable names to more closely match Icarus' summary)
 « Last Edit: Mar 23rd, 2005, 8:48am by SMQ » IP Logged

--SMQ

rmsgrey
Uberpuzzler

Gender:
Posts: 2844
 Re: 100 prisoners & a light bulb   « Reply #395 on: Mar 23rd, 2005, 8:50am »

on Mar 22nd, 2005, 8:27pm, Leonid Broukhis wrote:
 Must read "potentially leaving him with a negative token count".

"If he does not have a token..."

If he doesn't have a token, borrowing one is unlikely to leave him non-negative.
 IP Logged
SMQ
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 2084
 Re: 100 prisoners & a light bulb   « Reply #396 on: Mar 23rd, 2005, 9:04am »

A side note: as I've been playing around with various numbers of badges and stages trying to improve on my tweek to gypo's opening to [10,10], it occurred to me that in a final trinary stage, it can be very beneficial for the inactive prisoners to act as observers.

If *anyone* ever sees the light on, then off, then on again they know all three final-stage prisoners have visited the room and can immediately declare victory without waiting for the final item to be picked up.

The same principle can actually be applied to any final stage, but the benefit to stages with >3 items declines rapidly as the chance that any prisoner will have been in a position to observe all drop-offs and pick-ups becomes vanishingly small.  Let N be the number of active prisoners, O be the probable number of observers who witnessed every drop-off and pick-up, and D be the probable number of days saved (all for 100 prisoners):

N   O    D

3   17   94
4   10   90
5   2    50
6   <1   0
(see edit below)

As, if I understood right, rmsgrey pointed out below, if the final leader is already holding one or more items no observer will ever see a full count, which severely limits the utility when applied to anything other than a trinary round, so don't expect to see a 90 50-day savings in a round of four unless you can ensure the leader never starts out with an item...[/edit]

But if the leader doesn't start out with a token my probabilities are too high, and if he is supposed to (as I assumed when calculating the probabilities) but a previous round failed an observer could claim false victory--let's try that again...

N   O    D

3   17   94
4   2    50
5   <1   0

[/edit]

--SMQ
(edited again to ref. rmsgrey below)
(edited yet again to update probabilities)
 « Last Edit: Mar 23rd, 2005, 10:08am by SMQ » IP Logged

--SMQ

rmsgrey
Uberpuzzler

Gender:
Posts: 2844
 Re: 100 prisoners & a light bulb   « Reply #397 on: Mar 23rd, 2005, 9:21am »

on Mar 23rd, 2005, 9:04am, SMQ wrote:
 A side note: as I've been playing around with various numbers of badges and stages trying to improve on my tweek to gypo's opening to [10,10], it occurred to me that in a final trinary stage, it can be very beneficial for the inactive prisoners to act as observers.   If *anyone* ever sees the light on, then off, then on again they know all three final-stage prisoners have visited the room and can immediately declare victory without waiting for the final item to be picked up.   The same principle can actually be applied to any final stage, but the benefit to stages with >3 items declines rapidly as the chance that any prisoner will have been in a position to observe all drop-offs and pick-ups becomes vanishingly small.   --SMQ

That only works if people only collect tokens if their badges are filled - with most final stages, you can never find out what the leader's status is by watching the lights...

[e]
It also requires the rules for the trinary stage to be clear on what happens if previous stages were unsuccessful - if there are two (k-1)-tokens and two k-tokens out there, do people with (k-1)-tokens collect passing k-tokens or not? I'd suggest not.
[/e]
 « Last Edit: Mar 23rd, 2005, 9:25am by rmsgrey » IP Logged
SMQ
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 2084
 Re: 100 prisoners & a light bulb   « Reply #398 on: Mar 23rd, 2005, 9:53am »

on Mar 23rd, 2005, 9:21am, rmsgrey wrote:
 That only works if people only collect tokens if their badges are filled - with most final stages, you can never find out what the leader's status is by watching the lights...

Hmm, not sure I followed that.  I can see where, if the final leader has already collected one or more tokens/filled-badges/whatever-it-is-the-final-leader-is-collecting (as is likely in most final stages >3) then no observer will ever see a full count.  It should always work for a final trinary, though, so long as the three tokens start out in unique prisoners' inventories (and if one prisoner already holds two, observers can't shorten the round anyway).  Right??

--SMQ
 IP Logged

--SMQ

Leo Broukhis
Senior Riddler

Gender:
Posts: 459
 Re: 100 prisoners & a light bulb   « Reply #399 on: Mar 23rd, 2005, 10:06am »

on Mar 23rd, 2005, 8:50am, rmsgrey wrote:
 "If he does not have a token..."   If he doesn't have a token, borrowing one is unlikely to leave him non-negative.

Oops. Between your and gypo's description, I got the combined rule "if he has a token or a badge, he leaves a token" in my head.
 IP Logged
 Pages: 1 ... 14 15 16 17 18  ...  25 Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »