Author |
Topic: 100 prisoners & a light bulb (Read 166685 times) |
|
Paul Hammond
Newbie
Posts: 29
|
 |
Re: 100 prisoners & a light bulb
« Reply #250 on: May 2nd, 2004, 7:21am » |
|
I guessed at 100-day initial cycles because a quick calculation suggests that it takes 69 days for there to be a better-than-even chance of that cycle's prisoner having entered the room. 30 days only gives a 0.26 probability. But maybe repeating shorter cycles would be better than my cautious 100 days?
|
|
 IP Logged |
|
|
|
Rezyk
Junior Member
Gender: 
Posts: 85
|
|
Re: 100 prisoners & a light bulb
« Reply #251 on: May 2nd, 2004, 9:08pm » |
|
Consider also adopting dynamic label assignments -- "Each prisoner starts with no label. Within the first period for label X, the first prisoner who enters with no label adopts label X."
This should vastly improve the productivity of all periods. Even up through the 80th period, each period is more likely than not to have the bulb on and information passed from the 3rd day onwards. You can also throw in a small accumulation jumpstart with this (analagous to Salem's leader selection) for further optimization.
Of course, there is the downside that you must account for the case of some prisoners never acquiring a label. For this, I think a "designated reset day" or perhaps a combination with token gathering would be well worthwhile.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2872
|
|
Re: 100 prisoners & a light bulb
« Reply #252 on: May 4th, 2004, 8:56am » |
|
Well, the results of computer simulation of the basic named-prisoner per period are in - running 100 days per period clocks in around 54,000 days for release (averaged over up to 10,000 runs). Any number of days per period from about 40 or so on up to something like 150 is still within 1% of that figure but 70 days per period seems to be marginally ahead (out of 10, 30, 40, 50, 60, 70, 80, 100, 120, 150 and 200).
Trying a two stage process, running for one great cycle (100 periods to get back to the original prisoner) of long period and then short periods thereafter, seems to knock around 1000 days off the expected time for cycles of length 200-400 followed by cycles of length 30-70. Simulations on small prisoner numbers (around 6-10) suggest that this improvement is accompanied by a much lower variance in release time.
Having developed my intuition further by simulating some 6 prisoner cases by hand, for large cycle times, the advantage lies in wasting fewer days waiting for someone to show up who can turn the light on - the disadvantage comes in having to wait much longer to spread information about a given prisoner if you miss out during a given great cycle. During the first great cycle, long periods are beneficial, but in subsequent cycles you generally want to spend as little time as possible waiting for a given prisoner to become active...
I've yet to try Icarus' badge-sharing suggestion or Rezyk's dynamic labelling (which I really should have thought of myself...).
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: 100 prisoners & a light bulb
« Reply #253 on: May 10th, 2004, 4:41am » |
|
Real life has prevented my making much progress, but looking at Rezyk's dynamic allocation system from a theoretical perspective: calculating the number of days required to give a 99% or better chance of allocation in each cycle gives values less than 100 up to about 90 assignments. The accumulated total by then is around 500 850 days. On the other hand, if there are 90 people out of the hundred, each known to have visited by the same number of people independently, you need each to be known by about 95 people to get the expected number of people knowing about all 90 up to one...
It looks very much like dynamic allocation gains relatively little - only thousands of days, not the tens of thousands needed to get into contention.
[e]Checked my figures overnight... I really should check my facts before I post  [/e]
|
| « Last Edit: May 11th, 2004, 2:42am by rmsgrey » |
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 #254 on: May 10th, 2004, 3:47pm » |
|
I've been too spaced out by a nasty cold to look into it much either, but all indications point to my bright idea being unfortunately rather dull.
|
|
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
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: 100 prisoners & a light bulb
« Reply #255 on: May 11th, 2004, 3:33am » |
|
I wouldn't give up all hope just yet - The badge sharing approach only needs 10 cycles per great cycle, and quick calculations show that if 75 prisoners share each badge independently, you expect around 6 (5904900/1048576) prisoners to have a complete set. Using gypo's stage 0, the badges are allocated in such a way that they can have a numbering assigned in advance, or you can adopt a dynamic badge-numbering system (first unnumbered full badge in during a cycle adopts that number. If the light remains off at the end of a cycle, the person in on the first day of the next cycle becomes responsible for collecting an anonymous badge later and numbering it for the missed cycle. After the numbering cycles, you have a stage where any unnumbered full badges are transmitted and collected by whoever wants a badge to number. On the first pass, you may want to skip this stage, and insert it after a repeated stage one (assuming that the reason no-one got 10 badges is that one or more aren't yet full). Once I figure out the numbers to get a good chance of 75 people sharing a given badge, I might run some simulations. If anyone else wants to try first, feel free.
OK, looking back at the stage timings for gypo's solution, there's a ball park of 1500 days for badge collection, meaning 150 days per cycle for the simple version, giving an expected number of prisoners sharing each badge around 35 (by some pretty wild estimation rather than sober calculation or simulation) giving between .15 and .2 expected prisoners sharing all ten badges...
Thinking around the problem a bit more, is a {10,10} solution optimal for a badge sharing second stage? If you have only 9, or even 8 badges (of two different types to account for 100 not dividing evenly), that will knock a cycle off the sharing stage (where you're not concerned about which type a badge is, only that it's full), and reduce the required length of each cycle (you need rather fewer prisoners sharing each badge to get the same expected number knowing all of them)
For that matter, with a dynamic badge assignment, and the associated higher starting counts for badge-holders, is it worth increasing the number of badges to 11 or 12?
Hopefully these questions may help open up the topic for further investigation, even if they don't lead anywhere in themselves...
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #256 on: Jul 1st, 2004, 1:53pm » |
|
I have read all posts and have run simulations of my own employing a strategy similar to the labelling concept suggested recently. Information transfer can take two forms:
1. The number of counted prisoners
2. A list of the prisoners who have visited.
In the the case of #1, only one prisoner at a time may hold information about another prisoner to avoid redundancy. In the case of #2, anyone may carry information about anyone else.
#1 has the advantage that information doesn't have to be too specific - the result is simply true (everyone's been there) or false (not everyone has been there). #2 is beneficial because it allows the first prisoner with all the information to request freedom at their first opportunity.
I read all the posts today for the first time - stupid, considering I could have benefitted from some of the work already done here - and approached the Method #2 slightly differently from S. Owen, and later Icarus, did. My first approach was to divide days into sets of 5 and assign a sequential number to each set. So days 0 through 4 would be set 0, days 5 through 9 would be set 1, etc. If any prisoner with Label X enters the room during Set X, he switches the light on. Any prisoner who enters the room after him but still within set X, adds X to his list of known prisoners. On the first day of every set, the prisoner entering the room, records Prisoner X on his list and switches the light off (unless of course he is Prisoner (X+1)). Any prisoner with information may impersonate prisoners whose numbers they have collected. For example:
P5 enters the room on day 16.
16 / 5 = 3 rem 1.
3 <> 5 so light remains off
P3 enters the room on day 17
17 / 5 = 3 rem 2
3 = 3 so light goes on
P41 enters the room on day 18
light is on so records "3"
light stays on
P59 enters the room on day 19
light is on so records "3"
light stays on
P7 enters the room on day 20
light is on so records "3"
light goes off (new set)
After 500 days, the sets start again from 0 but this time with P41, P59 and P7 able to represent P3 if they visit the room during set 3.
this yielded a result of about 50000 days. Not good enough. So I adopted a strategy for dynamically adjusting the duration of a set to allow more receivers to get a message and to allow a larger window per cycle for a given prisoner to visit the room during his set (with set = 5 days, odds are 5%). After some critical amount of knowledge is moving among the prisoner, the set duration can be reduced. This implies starting with larger sets in the beginning at the expense of considerable initial lag time but good recovery from the dynamic reduction of set duration. It turns out that as you increase the initial set duration value and reduce it over time, the principles cancel each other out and produce the same result - about 50000 days. It doesn't matter if the set duration follows a decaying exponential or a linear drop - the results are the same - EXCEPT of course where set duration approaches 1.
I am currently working on a new solution that achieves results in the region of about 10000 days - it employs a similar principle to that mentioned above combined with a suggestion made earlier with the trading of tokens. I will let you know how it goes. I think there's plenty of room for optimization.
If anyone is interested in the code for my initial testing, I'd be happy to share.
One other thing bothers me though: Read the next post.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
 |
Re: 100 prisoners & a light bulb
« Reply #257 on: Jul 1st, 2004, 2:15pm » |
|
Someone mentioned earlier in one of the posts that the initial state of the switch was relevant. I may have misinterpreted it but would like to point out that it is irrelevant because it can simply be set to whatever the first prisoner in deems appropriate.
However, another poster mentioned a similar problem posted on the IBM site. And Mr Wu who obviously followed the link quoted it by saying it might have originated in Hungary.
No one else responded to this post but I found it quite interesting. If the solution to this problem is as it is given on the IBM site, then it appears we are asymptotically approaching an optimimum with no hope of a revelation because the solution on the IBM site is trivial and was mentioned on the first page of this post. I have no complaint however, because I enjoy the challenge, but it's interesting to note the the IBM solution is the simplest of all the solutions mentioned here (the leader solution) - except for the creative and annoying leaving of markers or beating up the guards. For those of you who are interested the URL is :
http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/solutions/July2002.h tml
The key difference in this puzzle is that there are two switches, and every prisoner must toggle at least one switch. It turns out that this is the same as there being one switch with no such requirement. Also the IBM riddle clearly states that the interval between visits is not fixed which eliminates the possibility for synchronising information with days since the meeting.
Thus this thread has become a quest much like that to prove that the earth was not flat. I am hoping the quest continues as the does the Olympic 100 meter sprint to the extent that we're ultimately looking to shave off individual days from our iterative average.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #258 on: Jul 2nd, 2004, 7:08am » |
|
Hey Guys,
Me again. I know everyone has lost interest in this problem and decided that AlexH's optimization is as good as it gets. Well I don't believe we have reached an optimum solution yet. I cut 2000 days off my 10000 day solution which uses information transfer in packets and dynamic counters (anyone can be a counter and can pass on his accumulation of counts at any time). My current average is 8700 days. But I have only just started work on this solution and am certain that is far from being optimised. Anyone who is interested in helping me continue in the direction I'm going, please let me know and I'll give you my source code.
Here is a description of the solution as I have it right now:
Let Prisoners P each begin with a token count of 1, which I will represent like this : Pi[1] where i is the prisoner label or number.
The principle involves the trading of tokens via a register (the light switch). The number of tokens stored in a register is a function of the number of days since the meeting - this function has huge potential for optimisation. Currently the value (v) of a token is:
v(d) = 2 ^ [(d/c) % (floor(log Pn / log 2) + 1)]
where d is the number of days since the meeting, c is the period during which tokens have a particular value, Pn is the total number of prisoners. The log part of this function is actually log Pn with a base of 2, but without subscripts, I thought I'd be safe and express it this way.
The following policies are used to determine if tokens should be transferred or not:
1. A prisoner must collect tokens if it is the first day of a new cycle (ie. the first day of a new token value). This rule beats all other rules. Once the prisoner has collected the token from the previous cycle, he may commit to the register a token with the current token value according to the remaining rules.
2. A prisoner must commit a token to the register if his current balance is less than twice the current token value (assuming of course that he has a token of the current value).
3. A prisoner may not collect tokens if his balance is less than the current token value.
An example: (let R be the register such that R[4] represents Register balance of 4)
R[0]; // register is empty
c = 3; // cycle period is 3 days
Pn = 4; // number of prisoners is 4
V = 0 // current token value
d = 0; // day 0
V = 2 ^ 0 = 1;
P2[1] -> P2[0];
R[0] -> R[1];
d = 1;
V = 2 ^ 0 = 1;
P0[1] -> P0[2];
R[1] -> R[0];
d = 2;
V = 2 ^ 0 = 1;
P2[0] -> P2[0];
R[0] -> R[0];
d = 3;
V = 2 ^ 1 = 2;
P1[1] -> P1[1];
R[0] -> R[0];
d = 4;
V = 2 ^ 1 = 2;
P3[1] -> P3[1];
R[0] -> R[0];
d = 5;
V = 2 ^ 1 = 2;
P0[2] -> P0[0];
R[0] -> R[2];
d = 6;
V = 2 ^ 0 = 1;
P3[1] -> P3[3];
R[2] -> R[0];
d = 7;
V = 2 ^ 0 = 1;
P2[0] -> P2[0];
R[0] -> R[0];
d = 8;
V = 2 ^ 0 = 1;
P1[1] -> P1[0];
R[0] -> R[1];
d = 9;
V = 2 ^ 1 = 2;
P3[3] -> P3[4];
R[1] -> R[0];
end;
As I said before - there are optimisations that can be made and all are welcome. My only regret is that unlike my original strategy which involved the spread of information, I'm disappointed that the current count can't be shared among the prisoners because of redundancy. There may be a hybrid which incorporates certain prisoners keeping track of particular prisoners while other prisoner(s) keep count. But probably not. Let me know your thoughts.
|
|
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: 100 prisoners & a light bulb
« Reply #259 on: Jul 2nd, 2004, 7:02pm » |
|
I know how you feel about working on this alone- it always seems that only one person at a time cares about this problem. That is the way it was when I worked on this (and several of the other hard problems too).
I think the current best is Rezyk's method of around 3531 days, near the bottom of page 8.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #260 on: Jul 3rd, 2004, 12:50pm » |
|
SWF: I think I will beat that. I'm currently running at about 3700 - but I can make some optimizations I think. I will let you know how I do.
Matt.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: 100 prisoners & a light bulb
« Reply #261 on: Jul 3rd, 2004, 6:10pm » |
|
I think you can simplify the reasoning by separating what the prisonner sees on arrival and the state he leaves on leaving. You shouldn't think of the 4 cases (switch on, switch off, leave on, leave off). Just think of what happens from one day to the other.
Leaving the light on on day d is a message from one prisonner to the next one. Since the sender doesn't know who the receiver is and the receiver might be there for the first time, the meaning of the light on day d must be the same whoever sent it and whatever happened before.
In our case, leaving the light on means "I am giving you k token" where k is a function of n. For example, your v(d). Whoever sees the light on counts in the v(d-1) tokens and then decides to send or not send v(d) token, which might be the same value.
In the leader method, v(d) is always 1 and anybody who is not the leader will give away whatever token he has one by one. You don't wonder if you switched it on before or not. Just count any token in and leave the light on if you have any token to get rid off.
In the other method of trying to combine 2^k groups, then v(d) is always some 2^k, and the prisonner should send that value if that value can be send without breaking a bigger group.
In any case, an optimization is that when starting the whole process, the first values v(d) could be 1, 2, 3, 4, up to some value to be defined, considering that at that time, it is likely that prisonners are there for the first time, so you can "snowball" a few points until it becomes too likely that a prisonner returns.
If you add the 28 extra token to be distributed to get a nice 128 total, then you can give it to the first prisonner, and v(d) would then start with 29, 30, 31, ...
But maybe, instead of giving 28 token to the same person, it is better to distribute them in order to form bigger 2^k groups.
If you give all the 28 the token to the 1st person, you have 4 prisonners with 29, 1, 1, 1 token. That is 7 groups of 2^k (16+8+4+1, 1, 1, 1), while the arrangement (16, 8, 4, 4) has only 4 groups, which is a few steps forwards in the work of combining 2^k groups. Then of course, we need to figure how it combines with the inital 1, 2, 3, ... points.
OK, no solution, just some thoughts.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: 100 prisoners & a light bulb
« Reply #262 on: Jul 3rd, 2004, 6:20pm » |
|
PS: it is still interesting to have long runs of same token count values so that if a prisonner receives a 2^k group and it does not combine with one he has, or if he simply has none, he can immediately send it to the next prisonner, while if the token value changes too often, people might be stuck with a 2^k group he can not send further, and it might take a few days until a prisonner happens to have the right group available to be sent.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #263 on: Jul 3rd, 2004, 8:55pm » |
|
Hey Grimbal,
Thanks for the input. Actually - I had already done something similar to your suggestion. Since my last post with the example, I have made some optimizations which brought my number of 8700 days down to about 3700.
My approach thus far has been driven by trying to pass more than one bit of information at a time - initally by passing known prisoner labels around and relying knowledge propogation to get the message to everyone. But this has a disadvantage in that it still requires specific prisoners to be in the room at least once during a specific 10 day period every thousand days, for example, which is a tall order.
The new plan was to stay with knowledge propogation but to transfer less specific transaction between any (or almost any) two prisoners at any time. You are correct that having decently long enough periods during which transactions involving the same token value may take place is beneficial; mainly because it prevents non perfect powers of 2 from ending up in the hands of a single prisoner.
But getting back to your suggestions. What I changed in my approach was to give 4 tokens to the first prisoner in the period when token value is 4, 8 tokens to the first prisoner in the 8-token period, and 16 tokens to the first prisoner in the 16 token period. That allows these prisoners to trade tokens from day one which is an advantage. I also introduced the policiy you suggested which is: Don't trade tokens if you have zero tokens or if you have a token balance which doesn't equal the current token value.
What I have done now is to optimise the process is to choose value periods according to the number of expected prisoners with a token balance greater than zero who will need to trade in that period. For example during the first period, all 100 prisoners will need to be involved in a transaction (just one). During the second period, 50 prisoners will need to trade, during the third period 26 (with the extra 4 tokens to the first prisoner in that period), during the fourth period 14 (with the extra 8 tokens), in the fifth period 8 prisoners (with the extra 16 tokens), in the sixth round 4 prisoners and in the last round 2 prisoners. For each of these I calculated the average time needed for the required number of prisoners to transact at least once and used those numbers to choose my period lengths. I will submit the numbers in a few minutes as a separate post - I'm on the wrong machine right now.
Anyway, my current number is 3700 and I'm about to get to some optimizing. Once again, thanks for the input. It's always welcome.
Matt.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #264 on: Jul 3rd, 2004, 10:17pm » |
|
Okay these are my numbers for the cycles:
680 days for trading token value 1
610 days for trading token value 2
545 days for trading token value 4
485 days for trading token value 8
425 days for trading token value 16
360 days for trading token value 32
290 days for trading token value 64
These numbers were chosen in the following way:
Ultimately, I was looking for a number which would, on average, give the prisoners a 50% chance of freedom from the first great cycle. This means that the probabilities associated with each round have to yield a combined probability of 50% for the great cycle.
In other words, if the probability of completing each round without stragglers, is 89% (which it is) then in six cycles, the probability of success in the first round is (0.89 ^ 6) = 50%.
In 680 days, the prisoners have an 89% chance of completing all value 1 trading. In 610 days, the 50 remaining prisoners have an 89% chance of completing the round, etc.
This means that 50% of the time, the prisoners escape in under 3400 days, but the other 50% of the time they will not. If they are not successful in the first round, the second round adds substantial time onto the back which pushes the average time up. My results look something like this:
3352
2944
3323
5929 (this bastard affects my beautiful average so far)
3172
3098
6345 (and again)
2982
6083 (yet again)
These are numbers from a real sample I just ran. If you ignore all the high numbers, the low numbers are quite nice. So I'm looking for input again - I want to know how to change the strategy to minimize the second great cycle. I could increase the probability of success in the first round which can help to bring down the average, but that means adding more days to the first great cycle which would make it very difficult to compete with Ryzek's solution. The alternative is to establish a means for quickly picking up the stragglers in the second cycle. The first cycle, if it is not successful, is usually distributed in the following way (for example):
1 x 64
2 x 32
or
1 x 127
1 x 1
or
2 x 64
It's usually one transaction short of success and that can mean another 3000 days. I know there's a short cut to picking up the pieces but I wouldn't mind some input.
Matt.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #265 on: Jul 4th, 2004, 7:33am » |
|
Okay I found a mistake in my numbers. I am working with 7 cycles and I used probabilities based on 6 cycles. Each cycle therefore needs a 91% chance of success in order for the great cycle to be successful 52% of the time. The new numbers are therefore:
700 for cycle 1
630 for cycle 2
565 for cycle 3
500 for cycle 4
445 for cycle 5
380 for cycle 6
310 for cycle 7
(rounded to the nearest 5)
This increases the great cycle to 3530 which is very sad because this is higher than the current minimum. It might be worthwhile to give the first great cycle a better chance of success at the expense of days upfront in order to bring the average down. I should also note that results within a successful first great cycle will range between 3220 and 3530 whose average (3375) is still better than 3400 - but again, only if the first great cycle succeeds. hmm.
Perhaps I should rewind a little bit and choose a very slightly different approach.
Matt.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: 100 prisoners & a light bulb
« Reply #266 on: Jul 6th, 2004, 4:54am » |
|
If I remember correctly, somewhere in the first few pages of this thread were some posts analysing the best sizes of chunks to divide the counts into - I believe the conclusion was that the optimum was about equal between 10 groups of 10 (or 8 of 11 and 1 of 12) and a three stage 20 groups of 5 going to 4 of 25.
If you use fewer stages, then you can accept lower probabilities of success in each, which makes them more efficient for a given net probability.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #267 on: Jul 6th, 2004, 8:51am » |
|
Rms: It depends on the desired outcome. For example, if you're looking for 50 transactions in the first round, you will need a certain number of days to be able to expect a 91% chance of getting all 50. In this case it's about 700 days for 50 transactions (of the type that my solution uses). However, if you're looking for transactions such as those described in earlier solutions (and posts), then the optimal number for the first round will be different. Previous solutions made use of assigned counters who counted to 9, for example, and then provided complete counts to a master counter. My solution works differently - it has 50 dynamically assigned counters counting to 2 in the first round. The number of days required to achieve these two different outcomes will be different. Ultimately the solutions boil down to a similar number of total days - mine requiring higher numbers in the first great cycle (which is my current issue) while previous solutions had less stringent requirements, being able to fall back on subsequent great cycles and still achieve a result in reasonable time. I think the key to this problem - regardless of the method, is choosing the right numbers for the job - not as a general set, but as a specific group of numbers finely tuned to the specific solution which uses them.
Matt.
|
|
IP Logged |
|
|
|
Bitrot
Newbie
Posts: 5
|
|
Re: 100 prisoners & a light bulb
« Reply #268 on: Jul 20th, 2004, 3:15pm » |
|
What is wrong with my reasoning?
[A] Each prisoner can learn exactly 1 bit of information each time he is selected.
[B] The knowledge that everyone has been selected constitutes N bits of information.
[C] Each prisoner is selected on average once every N days.
[D] Therefore, at least N*N days are required, on average, before any prisoner can know that all prisoners have been selected.
[E] Therefore, no algorithm can have an average running time that is faster than O(n^2).
|
| « Last Edit: Jul 20th, 2004, 3:23pm by Bitrot » |
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: 100 prisoners & a light bulb
« Reply #269 on: Jul 20th, 2004, 3:28pm » |
|
on Jul 20th, 2004, 3:15pm, Bitrot wrote:What is wrong with my reasoning?
[A] Each prisoner can learn exactly 1 bit of information each time he is selected.
|
|
This is wrong. The amount of information can vary depending on the number of day a prisoner is selected.
Quote:
[B] The knowledge that everyone has visited constitutes N bits of information.
[C] Each prisoner is selected on average once every N days.
[D] Therefore, at least N*N days are required, on average, before any prisoner can know that all prisoners have been selected.
[E] Therefore, no algorithm can have an average running time that is faster than O(n^2). |
|
The O is right, but we're into reducing the constant in front of n2 now.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #270 on: Jul 20th, 2004, 5:27pm » |
|
Quote:What is wrong with my reasoning?
[A] Each prisoner can learn exactly 1 bit of information each time he is selected. |
|
Also, it is true that one bit of information is available to any prisoner who enters the switch room - but knowing how to interpret the information is another story. Receiving the bit of info is easy - translating it into something meaningful is the key.
|
|
IP Logged |
|
|
|
Bitrot
Newbie
Posts: 5
|
|
Re: 100 prisoners & a light bulb
« Reply #271 on: Jul 20th, 2004, 8:14pm » |
|
on Jul 20th, 2004, 3:28pm, Leonid Broukhis wrote:
This is wrong. The amount of information can vary depending on the number of day a prisoner is selected.
|
|
It's either on or off. That's one bit, regardless of when.
Quote:
The O is right, but we're into reducing the constant in front of n2 now. |
|
Ok, but I still haven't convinced myself that's it's possible to do with constant <1. I realize of course that it has been proven possible, by construction, many times over in this thread. But it seems like I have to read all 11 pages with all the theorizing, dead ends, and abortions therein, or else I won't understand the latest posts, which all rely on previously created vocabulary.
So: is there some simple method that will work every time and averages <10000 days for N=100 that you could explain to me?
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: 100 prisoners & a light bulb
« Reply #272 on: Jul 20th, 2004, 8:35pm » |
|
on Jul 20th, 2004, 8:14pm, Bitrot wrote:
It's either on or off. That's one bit, regardless of when.
|
|
To quote a joke without naming hair color of the characters:
- What is the probability that you will encounder a dinosaur in a convenience store?
- 50%. Either I will, or I won't.
You see, the amount of information depends not only on the number of possible states of a signal, but on the distribution of probabilities of such states as well. If, e.g. an algorithm requires to leave the light on on day 2 if the person visiting on tday 2 was not the one who visited on day 1, then whoever comes in on day 3 does not get much information from the light that is on, because it is to be expected with 99% probability. If the light is off, however, he gets -log2(1/100) = more that 6.5 bits of information.
Quote:
So: is there some simple method that will work every time and averages <10000 days for N=100 that you could explain to me?
|
|
See a post by Rezyk on Oct. 14, 2003. Is it simple enough?
|
|
IP Logged |
|
|
|
Bitrot
Newbie
Posts: 5
|
|
Re: 100 prisoners & a light bulb
« Reply #273 on: Jul 20th, 2004, 8:47pm » |
|
on Jul 20th, 2004, 8:35pm, Leonid Broukhis wrote:
To quote a joke without naming hair color of the characters:
- What is the probability that you will encounder a dinosaur in a convenience store?
- 50%. Either I will, or I won't.
You see, the amount of information depends not only on the number of possible states of a signal, but on the distribution of probabilities of such states as well. If, e.g. an algorithm requires to leave the light on on day 2 if the person visiting on tday 2 was not the one who visited on day 1, then whoever comes in on day 3 does not get much information from the light that is on, because it is to be expected with 99% probability. If the light is off, however, he gets -log2(1/100) = more that 6.5 bits of information.
|
|
Sure, but since we're talking about the average running time, we can't look at what will happen in 1% of the cases. Is it not true that the expected amount of information is limited to 1 bit?
Quote:
See a post by Rezyk on Oct. 14, 2003. Is it simple enough? |
|
I'll check it out before I go on arguing when I know I'm wrong.  Thanks.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #274 on: Jul 21st, 2004, 5:46am » |
|
Bitrot, Let me sum up my method: There are 100 prisoners so essentially 100 bits of information need to be communicated. If all 100 prisoners had to receive all the information I doubt it could be achieved in less than O(N^2). But because the responsiblity of counting the prisoners visits is ultimately left to one person, the O is reduced.
This reduction is possible with a form of compression. Initially, in the first phase, information is passed (rather sub-optimally) one bit at a time. But in the second phase - in less time than the first phase took - information is communicated two bits at a time; and then four bits at a time in the even shorter fourth phase and so on.
My solution calls these transfers "transactions" and the expected number of transactions in my solution is O(N) - 50 + 26 + 14 + 8 + 4 + 2 + 1 = 105 (for 100 prisoners). The extra 5 is due to adjustments for non-powers-of-two.
All that the solution requires is that the order of prisoner visits is favourable for these transactions to take place - and it turns out - in my solution - that the mean is about 2900 visits with a 6000 spike every now and then which pulls the average up to 3400 visits which is comparable to the other solutions mentioned (although with different distributions, I think).
|
| « Last Edit: Jul 21st, 2004, 5:49am by mattian » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Notify of replies
Send Topic
Print