Author |
Topic: 100 prisoners & a light bulb (Read 166732 times) |
|
Leo Broukhis
Senior Riddler
Gender: 
Posts: 459
|
 |
Re: 100 prisoners & a light bulb
« Reply #400 on: Mar 23rd, 2005, 11:23am » |
|
on Mar 23rd, 2005, 7:28am, SMQ wrote: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. |
|
Thanks. I've found a bug in my code related to stage lengths: it was going 2000, 1600, 2000, 300 by mistake. And I've found a little bug in your code: it overcounts by one day because the loop increments the day number before figuring out that a trial has been completed.
|
|
 IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: 100 prisoners & a light bulb
« Reply #401 on: Mar 23rd, 2005, 11:36am » |
|
on Mar 23rd, 2005, 11:23am, Leonid Broukhis wrote:
And I've found a little bug in your code: it overcounts by one day because the loop increments the day number before figuring out that a trial has been completed. |
|
Oops.  I used to have "if (complete) break;" after each possible completion point, but it seemed cleaner to move it to the loop condition...
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: 100 prisoners & a light bulb
« Reply #402 on: Mar 23rd, 2005, 5:22pm » |
|
I've changed gypo's badge values to 11, 10...10, 9 and got 3466.48 days (a new record?) over 1,000,000 trials using 2000, 1600, 300, 300 stage lengths. And this is because the average numbers of tokens needed to fill the badges at the end of the snowball rounds for this new scheme is, in order the badges are given out are now:
7.3 6.5 6.7 6.9 7.1 7.2 7.3 7.4 7.5 6.8
(max - min = 7.5 - 6.5 = 1.0), sum = 70.7
In the original gypo's scheme it was
6.3 6.5 6.7 6.9 7.1 7.2 7.3 7.4 7.5 7.8 (max - min = 7.8 - 6.3 = 1.5)
For comparison, SMQ's scheme gives 3471.67 days with average remaining counts
6.6 7 7.4 6.6 6.9 7 6.5 6.6 6.7 7
(max - min = 7.4 - 6.5 = 0.9), sum = 68.3.
With a little lesser disparity and two fewer tokens to collect, SMQ's scheme loses by 5.19 days because its snowball duration is
47 days, compared to gypo's 40 days.
Now it seems that there is a faster way to compare the two schemes by looking at the disparity of the remaining token counts and their total (to find out these numbers, one only needs to simulate the snowball rounds which is about 100 times faster than a full trial). If for scheme A both the remaining count disparity and the sum is greater than in scheme B for the same number of days in the snowball rounds, scheme A is definitely worse than scheme B.
This observation may help mattian in his sweep efforts.
|
| « Last Edit: Mar 23rd, 2005, 6:18pm by Leo Broukhis » |
IP Logged |
|
|
|
mattian
Senior Riddler
 
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #403 on: Mar 23rd, 2005, 5:32pm » |
|
Okay - Some more numbers:
After 10000 iterations 100 AlexHPrisoners escaped in an average time of 9321.4869 days; a marginal improvement over the SalemPrisoners by about 45 days.
I won't post AlexHPrisoner.java code here unless someone wants me to. The reason is that I'm rebuilding the interfaces so it's all going to be changing anyway.
Paul Hammond is next.
|
| « Last Edit: Mar 23rd, 2005, 5:39pm by mattian » |
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #404 on: Mar 23rd, 2005, 5:38pm » |
|
on Mar 23rd, 2005, 5:22pm, Leonid Broukhis wrote:| This observation may help mattian in his sweep efforts. |
|
Actually - another nice feature in the engine is that you can define different outcomes. For example, the 100 prisoners problem is looking for one outcome - that all prisoners have visited the room without question - but for the benefit of analysis it is sometimes useful to define intermediate outcomes which may be declared by the prisoners, such as the end of the snowball round, or whatever. This allows us to apply a sweep to the snowball round without having to run the rest of the simulation at all - as Leonid is describing.
P.S. I wish I didn't have a real job so that I could spend some quality time on this thing and post the libraries here for general consumption - for any other riddlers with real jobs they wish they didn't have.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #405 on: Mar 23rd, 2005, 7:12pm » |
|
PaulHammondPrisoners did nicely at 10000 iterations, they escaped after 3964.4215 days on average. Nice and close to the original claim.
|
|
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 #406 on: Mar 23rd, 2005, 8:14pm » |
|
on Mar 22nd, 2005, 8:29pm, mattian wrote:| Icarus, if this is the summary, I'd hate to see the full document. |
|
Sorry about that. I wanted something self-contained, so that when William gets the headers working again, I could link to it in the header, and help new readers to be able to get the meat out of this thread without having to chew through all the gristle. I also wanted to explain methods by a common approach as much as possible, because it makes understanding new schemes easier, and also makes it easier to compare the approaches different schemes make.
I tend to be wordy, but I pushed to get this out because it was taking away my time from other things. If I get up the gumption (don't count on it), I'll see if I can simply the thing. I may also make some formatting changes to improve readability. One problem I had was that I knew it would be too big for a single post (I didn't expect it to take so many though - the max post size on the new YaBB is really small for someone like me). So I composed the whole thing in a word processor, then cut and pasted to post the pieces. This meant I could preview while posting to see what things looked like.
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...
[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] |
|
I believe SMQ is talking about the leaderless trinary stage I described. No one can pick up a final-level token unless he also has one. So anyone who sees the light on and then off knows that somebody now has 2 final-level tokens. He also knows that this person will not be passing either token. So if he sees the light on a second time in the round, it has to be the 3rd token being passed, thus guaranteeing that all three have been formed, and everyone has visited.
It is a neat little accelerator for this special case. It might even be considered a special case of that hybrid scheme you and I have been wanting.
---------------------------------------
Excellent work to SMQ and Leonid for the increased times, and to mattian for all the values on the old schemes. I will try to update the summary with them soon.
|
|
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
|
|
|
Ronald Waclawski
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #407 on: Mar 23rd, 2005, 9:49pm » |
|
I think I finally got this one.
The Light is in the off position to begin with.
1 Prisoner is chosen as the leader.
The other 99 are instructed to Turn ON the light when they enter the room IF and ONLY IF
A: The light is off
B: They have never turned on the light before.
Whenever the Leader enters the room, if the Light is ON the leader turns it OFF.
After the leader turns OFF the light 99 times, he can assertain that the other 99 prisoners have been inside the room at one point or another, including himself.
I'm 99.9% sure this is the correct answer
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #408 on: Mar 23rd, 2005, 9:57pm » |
|
Ronald,
That is certainly one of them, but it will take your prisoners about 30 years to escape. It is possible to do it in just over a third of that time. Pay close attention to the posts on pages 19, 20 and 21 of this thread for some alternative solutions.
on Mar 23rd, 2005, 8:14pm, Icarus wrote:
Sorry about that...
...I tend to be wordy, ... |
|
I was only joking about it being long. It's really not bad if one considers that it's 20 pages and three years worth of posts.
I haven't submitted AlexH2Prisoner yet because his improvement on PaulHammondPrisoner is a little unclear. He says that an optimisation would be to have shorter cycles subsequent to the first but he doesn't provide any numbers. We can therefore not associate any fixed results with his optimisation. The best I can do is to have the AlexH2Prisoner do as AlexH suggests but keep all cycles the same length as the first.
Alternatively, I'd welcome some feedback as to how we should derive subsequent cycle durations in order to find a number we can confidently say corresponds with AlexH's second entry in Icarus' history of key contributions. We wouldn't want to give AlexH any more or any less credit than is due to him on account of his idea.
|
| « Last Edit: Mar 23rd, 2005, 10:04pm by mattian » |
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 #409 on: Mar 24th, 2005, 5:47pm » |
|
You will notice that for some time they didn't really bother to give the stage lengths they were using. This does indeed make it hard to reproduce their results. But you will note that they also did not quote any hard figures. They were trying to find the optimum stage lengths for the given scheme.
AlexH in particular was mostly just suggesting at this point, rather than creating a hard scheme. He noted that later repetitions of the stages could work as continuations of the original stage, rather than starting over as Paul Hammond originally suggested. With this change, it was also clear that there was no longer any reason for later stages to be the same length as the originals. So he also suggests shortening the stages. It was only later, after he suggested and played with the binary scheme, only to discover it's shortfall, that he returned to Paul's [10, 10] scheme and made attempts at it. But again, he was more interested in the theory and his O( ) estimates than actual values.
I would suggest that some sort of optimization scheme would be useful. Can we discover some general principles that apply to optimizing individual stages so that combined they result in an optimized total? AlexH and James Fingas were doing some of this at one point, but I am wondering if their methods were all that effective, since SWF was able to shave an additional 250 days off the best times they came up with for the leaderless binary scheme. Perhaps he might be willing to discuss his optimization techniques.
|
|
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 #410 on: Mar 24th, 2005, 6:19pm » |
|
Well I could run the AlexH2Prisoner through the sweep interface and establish desirable repeating cycle lengths, but it will take me some time to polish up the sweeper - I haven't had much time to work on it. I'm keen to get it working nicely, if you guys will be patient with me.
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: 100 prisoners & a light bulb
« Reply #411 on: Mar 24th, 2005, 8:43pm » |
|
I was able to bring the numbers down to around 3459-3460. I cannot quote a more accurate number because even the runs of one million tries with same parameters report averages that differ a lot, e.g. 3457.93, 3462.77, 3459.41. Therefore it is no surprise that graphing the million run averages will result in a seesaw, e.g.
varying the duration of the long token collection phase may yield
1958 3460.45
1959 3459.81
1960 3460.91
1961 3459.82
1962 3460.63
1963 3461.92
1964 3460.01
1965 3461.16
1966 3460.25
1967 3459.71
1968 3460.99
1969 3459.28 <--- minimum
1970 3460.09
1971 3460.82
1972 3460.86
1973 3460.19
1974 3459.65
1975 3461.44
1976 3459.8
1977 3462.03
1978 3461
1979 3461.91
The badge assignment parameters were:
days: 5, 4, 4, 4, 4, 4, 4, 4, 4, 3
cost: 12, 10, 10, 10, 10, 10, 10, 10, 9, 9
|
|
IP Logged |
|
|
|
Jim Harvey
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #412 on: Apr 24th, 2005, 8:19pm » |
|
I'm not sure if this was posted, but I don't feel like reading 17 pages of replies, but I think they should break the light bulb in the living room, and using your sense of touch, figure out how many people have visited.
You agree on a corner in which to set the pieces, such as the right hand corner from the door. Now the light bulb will be broken into seven pieces and lined up to touch the wall so you can use your hands to tell when you've come to the edge to make sure no one steps on the pieces.
Now they will be laid out to represent a binary system where if the glass feels convex over the floor, then it equals a 1, concave equals a 0. So if it's your first visit, you can go and see how many have visited before you, if it reads 1100011, that means 99 have visited, and you can go free, if not, increase the number by one.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: 100 prisoners & a light bulb
« Reply #413 on: Apr 25th, 2005, 8:38am » |
|
on Apr 24th, 2005, 8:19pm, Jim Harvey wrote:I'm not sure if this was posted, but I don't feel like reading 17 pages of replies, but I think they should break the light bulb in the living room, and using your sense of touch, figure out how many people have visited.
You agree on a corner in which to set the pieces, such as the right hand corner from the door. Now the light bulb will be broken into seven pieces and lined up to touch the wall so you can use your hands to tell when you've come to the edge to make sure no one steps on the pieces.
Now they will be laid out to represent a binary system where if the glass feels convex over the floor, then it equals a 1, concave equals a 0. So if it's your first visit, you can go and see how many have visited before you, if it reads 1100011, that means 99 have visited, and you can go free, if not, increase the number by one. |
|
Without re-reading the entire thread myself, I'm not certain, but I believe that that is a new variation. Previous "physical-token" solutions used 100 distinct tokens rather than minimising the number of tokens.
Yours is also the only "break the bulb" suggestion to take account of the lighting problem.
On the other hand, the main thrust of the thread so far has been to explore solutions when prisoners can only communicate by encoding one bit in the state of the switch. Yours is certainly the best "off-topic" solution so far, but it isn't really what thse who have contributed most to this thread have been looking for.
[e]typo spotted on re-read[/e]
|
| « Last Edit: Sep 8th, 2006, 5:13am by rmsgrey » |
IP Logged |
|
|
|
The.coG
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #414 on: Apr 26th, 2005, 9:41am » |
|
who wrote the riddle and wont they just tell the answer?
f**** hell im not going to be able to sleep!!
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: 100 prisoners & a light bulb
« Reply #415 on: Apr 26th, 2005, 10:36am » |
|
on Apr 26th, 2005, 9:41am, The.coG wrote:who wrote the riddle and wont they just tell the answer?
f**** hell im not going to be able to sleep!!
|
|
As far as I know, the "best" solution to this one is still unknown.
The simplest solution is for one guy to turn off the light whenever he can and everyone else to turn the light on once - the guy turning the light off keeps count
|
|
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 #416 on: Apr 26th, 2005, 4:37pm » |
|
on Apr 26th, 2005, 9:41am, The.coG wrote:who wrote the riddle and wont they just tell the answer?
f**** hell im not going to be able to sleep!!
|
|
You'll find a summary of the solutions provided up to that point here. The best time so far is the 3460 day (on average) solution provided by Leonid Broukhis earlier on this page.
William stated sometime back that when he posted this puzzle, his solution was the Single-leader-with-snowball-round approach that Simon suggested. Paul Hammond's multi-stage concept, which cut times by nearly two thirds, was a surprise to him.
|
|
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
|
|
|
Joshua Franco
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #417 on: May 1st, 2005, 9:05pm » |
|
I'm just laughing at the whole '~364-something' day scheme because, well, that light's gunna go out, and they'll all be screwed. I think the 'creator' wanted something out-of-the-box like the binary token solution above. I really like that one, and I love when problems can be as true to life as possible, and a bulb lasting more than 9 years with the frequency of use presented isn't that doable.
Now, don't take me as a party-pooper, I'm very interested in what the rest of you are doing, and I'd love to jump in, I'm just casting my vote for the one I mentioned. First: What's the snowball round?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: 100 prisoners & a light bulb
« Reply #418 on: May 2nd, 2005, 3:45am » |
|
It doesn't matter how long a bulb can last. It will get replaced. Or not. The important thing is whether the switch is up or down.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: 100 prisoners & a light bulb
« Reply #419 on: May 2nd, 2005, 7:29am » |
|
on May 1st, 2005, 9:05pm, Joshua Franco wrote:| First: What's the snowball round? |
|
Somewhere around Icarus' summaries, I posted a list of definitions.
A snowball round is a period of consecutive days where the light is left on as long as new people keep visiting - it has the potential to accumulate a fairly large count very quickly early in the process, but, since a repeat visit by any prisoner stops the count from accumulating, and the rest of the round is then dead, it's rather less useful later.
|
|
IP Logged |
|
|
|
paul schmitz
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #420 on: Jul 1st, 2005, 7:26pm » |
|
i just read all the posts and my hat is off to anyone who came up with a good solution. i'd like to see some theory regarding a proof to the most optimal solution.
|
|
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 #421 on: Jul 2nd, 2005, 8:21am » |
|
Then you will just have to learn to live with unsatisfied desire!
It is doubtful that even the extremely clever approaches that have been suggested here are optimal. And even given a good approach, it is highly unlikely that you could show no other means could do better.
|
|
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: 2873
|
|
Re: 100 prisoners & a light bulb
« Reply #422 on: Jul 3rd, 2005, 12:58pm » |
|
Though any significant progress towards an optimality proof would probably be worth the effort of producing. It's extremely unlikely that the techniques of such a proof would fail to illuminate other problems.
|
|
IP Logged |
|
|
|
David Medus
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #423 on: Jul 23rd, 2005, 2:33pm » |
|
This might have been thought of... not a math related answer and is kinda cheating but the rules said nothing about not doing this --> First prisoner breaks the bulb and picks up all but 99 pieces of the shattered glass, then all the prisoners that follow pick up only one piece of glass. When all but one piece of glass is gone that prisoner knows he is the last. i know this is cheating but we are talking about life and death here.
|
|
IP Logged |
|
|
|
Three Hands
Uberpuzzler
Gender:
Posts: 715
|
|
Re: 100 prisoners & a light bulb
« Reply #424 on: Jul 23rd, 2005, 5:33pm » |
|
Various methods along those lines have been suggested, and the "think outside the box" method is certainly not one to be ignored. However, this thread is still looking for a more maths-orientated solution - part of the reason you won't find me posting on here much.
Feel free to take a look through the development of this topic, as it does make for interesting reading over the ingenuity of various people, both for the mathematical problem-solving, which has been one of the sources of this thread's success and the more abstract reasoning, much more akin to the kind of solution you have offered.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Notify of replies
Send Topic
Print