Author |
Topic: 100 prisoners & a lightbulb: Technical (Read 26507 times) |
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 2084
|
 |
100 prisoners & a lightbulb: Technical
« on: Mar 10th, 2009, 6:56am » |
 Quote  Modify
|
This thread is for technical discussion of the best known solutions to the "100 prisoners and a lightbulb" riddle. For general discussion and an overview of what is known (with links to the solutions), see this thread or, if you're very brave, the old thread which is one of the most popular on the board, but has grown so large and so technical that it's probably scaring people off.
Hippo, you have the floor. 
--SMQ
|
| « Last Edit: Mar 10th, 2009, 7:16am by SMQ » |
 IP Logged |
--SMQ
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a lightbulb: Technical
« Reply #1 on: Mar 10th, 2009, 8:13am » |
Quote Modify
|
 Have I scared people?
I have instaled C# myself and I am planning to implement "more general" strategy in it. ... I will publish it either here or more probably on n prisoners and k state switch forum.
As I am new to C# it will take much more than one day it should take to one familiar with it.
I have stopped the genetic experiments running more than a month. The gaps in knowledge are even in smallest numbers of prisoners, where ignoring first and omiting snowballs is best for 4 prisoners (the ternary top), and it was not tested with double binary top for 5 prisoners ... I suppose experimets will continue on version in C#.
I have incredibly small amount of accademic publications so may be ...
|
| « Last Edit: Mar 10th, 2009, 8:22am by Hippo » |
IP Logged |
|
|
|
River Phoenix
Junior Member
Gender:
Posts: 125
|
|
Re: 100 prisoners & a lightbulb: Technical
« Reply #2 on: Mar 24th, 2009, 7:58pm » |
Quote Modify
|
Can anybody supply a review of the known mathematical facts? E.g. probabilistic formulation, trivial lower bounds, information theoretic results, etc.
It would be highly significant, if possible, to make progress by diagonalization, counting arguments, or density/ramsey/ergodic theory.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a lightbulb: Technical
« Reply #3 on: Mar 25th, 2009, 6:36am » |
Quote Modify
|
For lower bound ... at least every prisoner must enter at least once.
For n prisoners where k not entered yet average time waiting for one of them is n/k.
This gives lower bound nHn.
Upper bounds whose can be easily calculated are for algorithms without phase switching.
... One counter with one snowball.
But they are beaten by so far known algorithms except for some small values of n.
Precise analysis of algorithms with phases requires space much bigger than the Universe.
BTW: I have not implemented gen parsing, mutations and snowballs yet, but it seems that binary scheme without snowballs, ignoring first beats one counter with snowball at least for n<=7.
In the following post brac37 incorporates to snowballs the idea the snowball fail the first possible fail night can be prevented by one intentional fail. I don't thing it will help, but I should think about it. Other proposals are special cases of general already discussed concepts (and there are nonoptimalities as badger selection is delayed what can result in doublebadge problem ...)
|
| « Last Edit: Apr 1st, 2009, 4:18pm by Hippo » |
IP Logged |
|
|
|
brac37
Newbie
Gender:
Posts: 23
|
|
Re: 100 prisoners & a lightbulb: Technical
« Reply #4 on: Apr 1st, 2009, 2:36pm » |
Quote Modify
|
Hello all,
In the second post of non-technical, one can read how I encountered the problem. Furthermore, you can read that I announced a message here. That will be this message. But what you read right now is only a beta version, since it will take more than a single moment to complete this message. You can start reading, but if you find something that is not clear/wrong or think that the presentation can be improved, you better send me a private message than posting here, for future consistency of this topic.
Before reading this message, read
http://www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBulb.pdf
unless you are convinced you know enough already.
A conceptual algorithm for dynamic counters
The purpose of this algorithm is to build concept. For that reason, it is a very dumb algorithm. The receipts of bulb messages in the algorithm will be formulated in the description of the sender. The reason of this will follow later.
The general idea is that in the first 47 days (47 is an arbitrary number for easy formulation), nine counters will be assigned and some counting will be done already. The problem of assigning a primary counter amongst the counters is ignored in this conceptual presentation. The counters gets different counting targets, but the formula presented here for these targets is a very stupid one (but easy for presentation). From day 48 and on, the algorithm continues as the multi-counter algorithm in the above link.
Here follows the description of the first 47 days. k is any nonnegative integer. In dark cyan, you can find remarks about tokens and badges. Ignore them if you do not know what they are (or just read them to understand what they are).
Day 1. The prisoner that is invited to the room does not need to be counted. So 99 prisoners must be counted. The bulb is set in an arbitrary position.
99 prisoners add one token each to their inventories.
Day 2+5k. The prisoner that is invited sends to his successor if he is invited the first time.
If the prisoner has a token, then he gives it to his successor.
Day 3+5k. The prisoner that is invited sends to his successor if at least one of the prisoners of the days 2+5k (predecessor) and 3+5k (himself) has been invited for the first time. His successor interprets a positive answer as exactly one instead of at least one. For that reason, the invited prisoner will forget that he has been invited to compensate, in case two prisoners of the days 2+5k and 3+5k has been invited for the first time.
If the prisoner has a token (one or two tokes), then he gives one token to his successor.
Day 4+5k. The prisoner that is invited sends to his successor if on both day 3+5k (predecessor) and day 4+5k (himself), a prisoner was invited for the first time. His successor interprets a negative answer as no one instead of at most one. For that reason, the invited prisoner will forget that he has been invited to compensate, in case exactly on one of the days 2+5k and 3+5k, a prisoner was invited for the first time.
If the prisoner has two tokens, then he gives both of them to his successor.
Day 5+5k. The prisoner of this day becomes a counter, except in case he was already a counter before he was invited. In that case, he orders his successor to become a counter by way of the bulb. If he becomes a counter, then his object will be to count 15-k of the 99 prisoners.
The prisoner adds one badge and k tokens to his inventory. If the prisoner had already a badge, then he passes the (just created) badge and k tokens to his successor.
Day 6+5k. The prisoner of this day becomes a counter if he has been ordered by his predecessor, except in case he was already a counter before he was ordered. In that case, he orders his successor to become a counter by way of the bulb. If he becomes a counter, then his object will be to count 15-k of the 99 prisoners.
If the prisoner received an order to become counter, but had already a badge, then he passes the (just received) badge and k tokens to his successor.
Day 7+5k. The prisoner of this day becomes a secondary counter if he has been ordered by his predecessor. If he becomes a counter, then his object will be to count 15-k of the 99 prisoners. Since 7+5k = 2+5(k+1), we are round now.
Improvements of the conceptual algorithm
God did not create the universe in six days. No, I am told that that is another translation error in the bible. God created the universe in six periods instead. This is also more in accordance with scientific research, but that is another discussion.
Here, we have a week of 5 days without a Sunday. But some days may be removed, merged, or blown up to a sequence of several days. From now on, we call the days of the above algorithm periods.
For instance, period 5, 6 and 7 will be one and the same day, because the period 5 prisoner will always become a new counter. If periods 5+5k, 6+5k and 7+5k are not merged to one day, then periods 5+5k and 7+5k remain one day, but period 6+5k becomes a sequence of zero or more days.
If period 9+5k in the concept becomes more than one day, then there will be a transfer of either zero or d+1 tokens to the successor on day d of this period. If the prisoner of day d has at least d+1 tokens after receiving the tokens of his predecessor, then he can get rid of d+1 tokens.
Day 8+5k and day 9+5k in the concept will become sequences of zero or more days, but it seems wise if at most one of both days will become a sequence of positive length.
I take a break now.
Passing additional tokes or anti-tokens along with badges.
Cheating by prisoners with badges.
|
| « Last Edit: Apr 2nd, 2009, 4:49pm by brac37 » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a lightbulb: Technical
« Reply #5 on: Apr 24th, 2009, 1:05am » |
Quote Modify
|
The C# implementation is not finished yet  , but the long simulation of genetic algorithm for 12 counters (with snowballs with first fail hooks and careful restarting, /\/// ordering of binary phases and observers stop) and I get average 3369.69 of all 7810569 simulations. The most spread gen had average under 3347.
|
| « Last Edit: Apr 24th, 2009, 1:12am by Hippo » |
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: 100 prisoners & a lightbulb: Technical
« Reply #6 on: Apr 30th, 2009, 2:28pm » |
Quote Modify
|
on Apr 1st, 2009, 2:36pm, brac37 wrote:
Hi,
You may be interested in an updated version of my small writeup that has been hiding at the following URL:
http://www.ocf.berkeley.edu/~wwu/articles/100prisonersLightBulb.pdf
This version has corrected typos, describes the binary tokens scheme more clearly, and includes technical content such as a proof that the binary tokens scheme has O(n (ln n)^2) runtime.
(Normally I would update the old URL, but apparently I cannot update the old URL at the moment because all SSH services are down at OCF, and it is unknown when they will be restored.)
Will
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a lightbulb: Technical
« Reply #7 on: May 2nd, 2009, 9:13am » |
Quote Modify
|
on Apr 30th, 2009, 2:28pm, william wu wrote:
Hi,
You may be interested in an updated version of my small writeup that has been hiding at the following URL:
http://www.ocf.berkeley.edu/~wwu/articles/100prisonersLightBulb.pdf
This version has corrected typos, describes the binary tokens scheme more clearly, and includes technical content such as a proof that the binary tokens scheme has O(n (ln n)^2) runtime.
(Normally I would update the old URL, but apparently I cannot update the old URL at the moment because all SSH services are down at OCF, and it is unknown when they will be restored.)
Will |
|
Hi,
I have not read the updated version thoroughly yet.
It does not seem to be difficult to bound binary phases not using observers stop.
But when the observers stop is taken into account the things became very very difficult to analyze.
This is why I have switched to simulations instead.
Behaviour for optimal so far found parameters of best so far described algorithms gives nearly  /2 n ln2 n so it seems the complexity of the problem would be  (n ln2 n) (with the multiplicative constant near /2).
Typo found:
Page 4: Stage II - Prisoners who did not see an ON bulb in stage I do nothing
There is problem with binary counting when n is not power of 2, I didn't see the required modification is in the article (I would mention two level scheme with non equal badges as well).
|
| « Last Edit: May 28th, 2009, 3:40pm by Hippo » |
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: 100 prisoners & a lightbulb: Technical
« Reply #8 on: May 28th, 2009, 3:29pm » |
Quote Modify
|
Hippo,
Thanks for the correction; I have updated the PDF with the fix.
I haven't had time to revisit the document lately. You are more than welcome to co-write something though if you like; if you want to use the same .tex file, send me an e-mail.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Mike_V
Junior Member
Gender:
Posts: 60
|
|
Re: 100 prisoners & a lightbulb: Technical
« Reply #9 on: Mar 2nd, 2010, 8:55am » |
Quote Modify
|
on Apr 30th, 2009, 2:28pm, william wu wrote:
Nice paper! Just thought I'd mention some potential problems I saw, in case you wanted to fix them.
On page 6:
- Prisoners who saw an ON bulb in Stage I do nothing.
I think you mean "who saw an OFF bulb". Since those are the ones prior to the counter being chosen. The ones who saw an ON bulb (afterward) were not counted.
On page 11:
On the last day of Stage II:
- If you are a drone:
* If light is ON, turn it OFF. Then in future invocations of Stage I, turn the
light ON q times.
I don't think this works. Since you won't have enough assistant counters to accumulate the extra q switches. Instead, you should have this drone turn the light ON 1 time in Stage II (also far faster).
Page 12:
* If the light is ON, add q to count. If the count equals n, declare victory.
Forgot to mention that he needs to turn it off if the count doesn't equal n.
Also, it'd be nice to have average run times for n=100 for each of these protocols.
- Mike
|
|
IP Logged |
Don't specify the unspecified.
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a lightbulb: Technical
« Reply #10 on: Mar 17th, 2010, 8:26am » |
Quote Modify
|
Oh yes, I don't remember the previous version exactly, but seems you negate the meaning of the ON/OFF during snowball (in 7th protocol). Which is incompatible with the 2nd phase according to standard protocol when counter turns OFF.
Starting snowball with ON and switching to OFF by selected counter is compatible with the "who saw ON in first phase does nothing" and with the classical counting in 2nd phase as well.
----------
To the protocol 8 ... the static assignment of assistant counters and the head counter are ineffective. Morever stage switching is much easier with dynamic counters. At the end of stage in the ON state prisoner "increments" the number of tokens in ending phase to be sent.
It's complicate to describe it as he is double drone (the and of first phase with active drone in it) and drone assistant when it have to sent one token in odd phase and one in even etc.
I would definitly not divide assistant token into q drone tokens.
More natural ... may be just for me ... describtion of the 8th protocol is following:
Each prisoner stars with (virtual) token, and goal.
Most of prisoner's goal is zero, but a "assistant counters" obtain nonzero goal and assistant token.
There is head counter (the only prisoner with nonzero assistant token goal (equal a)).
On odd phases:
in OFF state each prisoner having more tokens than goal states decrements his token count and switches light ON. Otherwise there is no change.
in ON state each prisoner having bigger goal than tokens increments his token count and switches light OFF. Otherwise there is no change.
On even phases: (similarly but with assistant tokens)
in OFF state
... having at least 2 more assistant tokens than is assistant goal decrements the number of assistant tokens and swithces light ON.
... having 1 more assistant token than assistant goal and goal equal to number of tokens ... decrements the number of assistant tokens and swithces light ON.
otherwise no change
in ON state
... having less assistant tokens than assistnt goal increments number of assistant tokens and switches state OFF
otherwise no change
Victory is declared by head counter when both his goal and assistant goal are equal to number of collected tokens and assistant tokens.
The scheme could work in case sum of goals is equal to number of tokens and the head counter assistant token goal is equal to number of assistant tokens.
There is no need to make all goals of equal size in this scheme. And actually only the differences tokens-goal, assistant tokens - assistant goal are important. I would rather use level 1, level 2 tokens in the describtion ... what could be easily generalised to more than 2 level scheme.
|
| « Last Edit: Mar 17th, 2010, 9:20am by Hippo » |
IP Logged |
|
|
|
rsreinhart
Newbie
Posts: 2
|
|
Re: 100 prisoners & a lightbulb: Technical
« Reply #11 on: Jan 4th, 2012, 4:55am » |
Quote Modify
|
I have a solution that I don't believe has been put forth yet. I read through many pages from various threads and didn't see what I think could be a more optimal solution. It is a modification of the binary and several other ideas already out there. I believe it could be a significant improvement in expected # of days until freedom.
I. Day 1-120
Assume light starts off.
All Prisoners start with a value of 1.
All prisoners that have never been in room before turn light on when finding it off and reduce their value by 1 to 0.
Any prisoner finding light on, turns it off and adds a value of 1 to his value. (Exception: on Day 2, prisoner will always add an extra 28 to his count (e.g. if he enters with light on, would have a count of 30. In the event he enters on both day 1 and 2, it would be 29).
At the end of 120 days, there will be a value distribution such as: 1 x 31, 14 x 3, 22 x 2, 3 x 1.
The light on can/should be carried over from Day 120 to Day 121 to start the next cycle. E.g. If the Day 120 person has a Value of 1 and enters with light off should turn light on and leave with Value 0, or if he enters with Value 0 and light on should leave light on and leave with Value 0.
II. Days 121+
There will be a 70 day cycle allowing the counts to be accumulated.
Days 1-10 = Value 1
Days 11-20 = Value 2
Days 21-30 = Value 4
Days 31-40 = Value 8
Days 41-50 = Value 16
Days 51-60 = Value 32
Days 61-70 = Value 64
Whenever someone enters a room, he can either pass along his count or accumulate the count already in the room.
Counts are signaled by the light being on during the respective period. If someone enters on day 37 with the light on then the room has a value of 8.
Counters will always try to put up or take loose counts that give them fewer pieces of binary number. E.g. a 9 will leave a 1 but not a 2. A 7 will accumulate a 1 or 2. (Going from 7 to 9 goes from 3 binary pieces to 2 (4+2+1 --> 8+1)
{e.g. On Day 2 of the 70-cycle, someone who has not previously entered the room (has a 1 value), turns light on. Day 3-5, 3 people with value 0 enter room, they ignore the light and leave remaining at Value 0. On Day 6 someone with a 1 count enters, he takes the 1 count in the room by turning off the light and he is now a 2 count. Day 6, someone with value 1 enters and turns light back on, and leaves as a value 0. Now on Day 10 (the last day of the 1’s value), if the light remains on, whoever enters the room adds a value 1 (even if he’s at 0) and turns light off to reset for the Day 11-20. However, if he would be leaving as a 2, instead he would leave light on and leave as a Value 0.}
{Day 11, someone with Value 1 enters, leaves light off and leaves as Value 1 still. Day 12, someone with Value 3 enters, turns light on and leaves as Value 1. Day 14 someone with value 1 enters, leaves without touching light or changing his value. Day 15, someone with Value 2 enters, turns light off and leaves as Value 4. On last day of the 2 values, Day 20, someone with Value 1 enters, turns light off and leaves as value 3, in order to prepare for Value 4 days.}
After Day 70, the 70 day cycle starts over again with 10 days at each binary value.
Once a prisoner has accumulated 128 Value, freedom is declared.
In this way, unlike other binary methods, there is no need to ever restart from the beginning, because each 70 day-round allows all binary values to be passed. And the person that started as a counter can pass his whole or partial count to someone who was a non-counter that enters the room 5 days later; there is no need for someone to be the next person in the room to transfer count.
The 100 prisoners as well as the light bulb all can store values where the bulb’s value is based on the day of the cycle it is lit.
The 70 day period is not-optimal, just seemed like a good starting point for analysis.
My guess is this could be significantly less than the current 3500 day models although I don’t know how to model this method.
I'm thinking 20-30 times through the 70 day cycle + the initial 120 days would be 1500-2100 day range.
Also as I stated before the 70 day period could be optimized with fewer days for some values and more for others or could change each time through weighing more heavily toward the higher binaries each time through.
Comments and analysis welcome.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: 100 prisoners & a lightbulb: Technical
« Reply #12 on: Jan 4th, 2012, 5:27am » |
Quote Modify
|
Now that's how you do a first post -- welcome to the forum! 
On the surface it's certainly an intriguing variation; let me break out my simulator and get back to you.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: 100 prisoners & a lightbulb: Technical
« Reply #13 on: Jan 4th, 2012, 8:23am » |
Quote Modify
|
My immediate, intuitive (ie probably wrong) reaction is that you'll lose a lot in the phase changes - time to victory can be counted in number of tokens merged - that is, sent and collected by someone with a matching bit. Every time someone intercepts a token because a phase ends rather than because they want it, you waste the initial transmission of that token.
A little more thought says that making the final count requires the last two prisoners with any values to both enter the room during the same 10 day period (in the right order unless they both have 64).
There's a 1/50 chance of either of them entering on any given day, and a 1/100 chance of the other entering on any other given day, with 45 possible choices of pairs of days, that's a 9/1000 chance of success in any given cycle once two prisoners each have a count of 64. If the final token is smaller, then it's a 9/2000 chance in cycles where one prisoner is only missing one binary token (actually, the chances are a little worse than that since you're over-counting those times when at least one of the two "live" prisoners visits more than once in the ten days, but the error is not large)
If you take the 9/1000 figure, that's roughly 111 cycles - 7770 days - just for the final transaction.
|
|
IP Logged |
|
|
|
rsreinhart
Newbie
Posts: 2
|
|
Re: 100 prisoners & a lightbulb: Technical
« Reply #14 on: Jan 5th, 2012, 4:47pm » |
Quote Modify
|
rmsgrey, I don't think that calculation is correct. If each day each prisoner has a 1/100 chance and there's 10 days per cycle, it would be a 1/10 chance for each of the two or 20% chance that one of the 2 'value=64' would be chosen during the 10 day period. The chance of the second one being chosen would be 1/99 x (depending on day of the first being chosen but assume 5 is the average day leaving 5 days for the second to be chosen) 5. Thus in any 70 day cycle it would be .20 x 5 / 99 or 1% chance. Avg would then be 3500 days for >50%.
This appears pretty high so it's nearly 10 years for the final phase. I do believe the initial accruing of binary blocks would be rather quick using this method. Assuming my calculations are correct, the last phase would take too long...obviously the 70 day cycle times can be adjusted.
I could easily eliminate this problem by removing the 64 bit days from the 70 day cycle and making them 60 day cycles. Then I can set every 20th cycle would only be 64 bit days for 120 days in a row. There's an extremely high chance that the two Value 64 bits would combine during those 120 days.
One time through the cycles would then be 120+60x19+120 =1380 days.
My initial idea included the idea that the cycle composition could change over time.
Suppose we did the following:
Cycle 1:
15 days for Value 1
14 days for Value 2
13 days for Value 4
12 days for Value 8
The cycles would adjust each time finally reaching the final distribution of days skewed toward high value blocks:
Cycle 20:
5 days for Value 1
6 days for Value 2
8 days for Value 4
10 days for Value 8
15 days for Value 16
15 days for Value 32
20 days for Value 64
You may be able to eliminate the lower value days and just repeat the entire cycle in case of failure.
What program are you guys using to model these type of problems? I would love to be able to tweak the assumptions myself.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 100 prisoners & a lightbulb: Technical
« Reply #15 on: Jan 5th, 2012, 11:04pm » |
Quote Modify
|
on Jan 5th, 2012, 4:47pm, rsreinhart wrote:| What program are you guys using to model these type of problems? I would love to be able to tweak the assumptions myself. |
|
Different programs we wrote ourselves. e.g. You could use monte carlo simulation, or what I like to do is keep track of all possible states and their probabilities (but that's only doable if the number of states is sufficiently limited).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: 100 prisoners & a lightbulb: Technical
« Reply #16 on: Jan 6th, 2012, 8:58am » |
Quote Modify
|
on Jan 5th, 2012, 4:47pm, rsreinhart wrote:| rmsgrey, I don't think that calculation is correct. If each day each prisoner has a 1/100 chance and there's 10 days per cycle, it would be a 1/10 chance for each of the two or 20% chance that one of the 2 'value=64' would be chosen during the 10 day period. The chance of the second one being chosen would be 1/99 x (depending on day of the first being chosen but assume 5 is the average day leaving 5 days for the second to be chosen) 5. Thus in any 70 day cycle it would be .20 x 5 / 99 or 1% chance. Avg would then be 3500 days for >50%. |
|
Your 1% approximate value is very close to my 9/1000 value - where we differ significantly is in how to convert the probability per iteration into an expected number of iterations for first success.
If you let the expected number of iterations for first success be E, and the probability of success in each iteration be 1/100 (independently), then the expected number of further iterations required after the first one fails is again E, making the total expected number of iterations if the first fails 1+E, while the expected number required if the first iteration succeeds is 1. Substituting into:
E = P(success) * E(success) + P(fail) * E(fail)
gives:
E= 1/100 * 1 + 99/100 * (1+E)
= 1 + 99E/100
100E = 100 + 99E
100E - 99E = 100
E = 100
not E=50 as you approximated...
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a lightbulb: Technical
« Reply #17 on: Feb 29th, 2012, 7:52am » |
Quote Modify
|
on Jan 4th, 2012, 4:55am, rsreinhart wrote:| I have a solution that I don't believe has been put forth yet. I read through many pages from various threads and didn't see what I think could be a more optimal solution. It is a modification of the binary and several other ideas already out there. I believe it could be a significant improvement in expected # of days until freedom. |
|
Sorry, I don't think there is a bright new idea. You have applied binary counting scheme.
Unfortunately your "guessed" parameters are far from optimal ones. ... Your "snowball" phase is normal binary counting. The phase lengths are too short.
These 28 tokens given at 2nd day are not optimal. Better solution is giving the extra bits in first phase switching to given binary level (to 4, to 8 and to 16) ... this saves one visit of counter on given level. My guess is around 4000-4200 days for average release time. [edit] ... this was too optimistic with phases of length 10 (Last phase requires 150 days in average)
[/edit]
I am sure the snowball prephases speeded the binary counting a lot and the observers stop method was crucial for making binary counting better than two level counting schemas.
What was surprising that binary counting with 3 counters in the top level were better than 2 binary counters on top (observers stop).
Nonetheles you made a huge step to understanding the problem ... Try to run simulation yourself (several tousand times) to gain better understanding of required phase lengths.
|
| « Last Edit: Jul 15th, 2016, 1:33pm by Hippo » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print