Author |
Topic: 100 prisoners & a light bulb (Read 167253 times) |
|
myself
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #175 on: Jul 19th, 2003, 11:30pm » |
|
can somebody post the link to the original riddle? Or tell it again, but i cant seem to find it... //Added by the moderator: For those who are reading this thread for the first time, when "myself" posted this, the header above had not been added to the thread.//
|
« Last Edit: Sep 8th, 2003, 7:07pm by Icarus » |
IP Logged |
|
|
|
Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #176 on: Jul 20th, 2003, 11:33am » |
|
It's the fourth riddle on the Hard Riddles page.
|
« Last Edit: Jul 23rd, 2003, 7:21pm 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
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: 100 prisoners & a light bulb
« Reply #177 on: Sep 8th, 2003, 7:56am » |
|
Just to try and drive someone else crazy (misery loves company): I've been mulling over the setup for this problem and wondering how much computational power the prisoners collectively have. Obviously, individually they are capable of solving any solvable problem, so there has to be some means of preventing any one prisoner from starting with all relevant data (unless they then aren't allowed to be the ones who make the final declaration). The input to the system then has to be the order in which prisoners get taken to the room. Assuming appropriate coding on the input, what problems can be solved by the collective prisoners?
|
|
IP Logged |
|
|
|
zack smith
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #178 on: Sep 9th, 2003, 9:56pm » |
|
my guess is that the prisoners were numbered from 1-100 and they would carve there number into a wall for ever time they are in the room.
|
|
IP Logged |
|
|
|
Steve Burns
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #179 on: Sep 19th, 2003, 3:46am » |
|
Wow, 8 pages of posts... this is my first time on this site and this one really just smacked me after i read it... Now... This riddle really has nothing to do with days because, if the inmates are taken at random, then one person could go a few times before another goes at all. What needs to happen is that the inmate must toggle the switch if it is their first time in the living room. The start positions is off... so seeing it takes 2 toggles to turn a switch from on to off, when the light goes out for the 50th time, then the next prisoner can assert that all prisoners have been in the living room.... Anyone see any flaws with that? ... email me response at "zyth13@hotmail.com".... later all
|
|
IP Logged |
|
|
|
Steve Burns
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #180 on: Sep 19th, 2003, 4:28am » |
|
Sorry folks about the last post... i missed that the prisoners couldn't see the light..... my new idea... the first prisoner in should break the bulb into 100 pieces and take one... each following prisoner should take a piece of the shattered bulb until none are left... that is when the assertion can be made...
|
|
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 #181 on: Sep 19th, 2003, 3:50pm » |
|
Welcome to Wu's Forum, Mr. Burns! I do feel compelled to point out that you are only about the 20th or so person to suggest this. (There's a lot of stuff in those 8 pages.) There are plenty of other so-called "outside the box" solutions too. And while in any sort of real-world application, they are often preferable, in this case they actually bypass what makes the puzzle interesting: the challenge of finding the best "inside the box" solution.
|
|
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
|
|
|
kofman2155
Newbie
Posts: 3
|
|
Re: 100 prisoners & a light bulb
« Reply #182 on: Oct 8th, 2003, 8:05pm » |
|
I take it, no answer has been provided yet. Is there a point at which Mr. Wu provides us with one?
|
|
IP Logged |
|
|
|
Mike_V
Junior Member
Gender:
Posts: 60
|
|
Re: 100 prisoners & a light bulb
« Reply #183 on: Oct 8th, 2003, 8:35pm » |
|
Actually, several very good answers have been given in the 8 pages of this thread. Though I don't believe any have been proven to be optimal.
|
|
IP Logged |
Don't specify the unspecified.
|
|
|
Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 100 prisoners & a light bulb
« Reply #184 on: Oct 8th, 2003, 8:57pm » |
|
AN answer is to be found in the first few posts, but it is definitely not optimal. A variation was made of it which was essentially the answer that William had, but this too has been significantly bettered. If you will go ahead and read though the posts, you will see some very clever ideas for improving the outcome. However a proof of optimality does not seem likely to me. And no, William does not provide the answers to his puzzles. Those of us who haunt these forums on a regular basis would have it no other way. Nor do we provide the answers to the puzzles we post. The finding of the answer is, and should remain, the responsibility of the readers, not the poster (who should say so if he or she does not know the answer).
|
|
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
|
|
|
dimitre
Newbie
Posts: 5
|
|
Solution in 600d. Re: 100 prisoners & a light bulb
« Reply #185 on: Oct 14th, 2003, 5:03am » |
|
Hi, I have a solution which works in an average of 600 days. Is it good or bad? Will anybody be interested if I publish this solution and the program that demonstrates it? Cheers, Dimitre.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Solution in 600d. 100 prisoners & a light bulb
« Reply #186 on: Oct 14th, 2003, 5:16am » |
|
on Oct 14th, 2003, 5:03am, dimitre wrote: I have a solution which works in an average of 600 days. Is it good or bad? |
| That would be pretty good, since the more common solutions on average take at least a decade or two, and yours less than two years. Quote:Will anybody be interested if I publish this solution and the program that demonstrates it? |
| Please do, it'd be interesting to see a new approach..
|
« Last Edit: Oct 14th, 2003, 5:17am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
dimitre
Newbie
Posts: 5
|
|
Re: 100 prisoners & a light bulb
« Reply #187 on: Oct 14th, 2003, 7:04am » |
|
The solution is as follows: The time is divided in iterations. Every iteration is exactly 100 days. Every prisoner has two states: registered unregistered All prisoners are unregistered before any prisoner has visited the room. When a prisoner visits the room: If this is the first day of an iteration, he lights the bulb. If the bulb is lit and the prisoner is unregistered, he becomes registered. The prisoner also remembers the number of the iteration, at which he registered. If the light is on and the prisoner visits the room for a second time during the iteration in which he became registered, he turns off the light If this is the last day of the current iteration and the light is on and the prisoner is either unregistered or has been registered on a previous iteration, then he announces that all prisoners have already visited the room. The .Net C# project is in the attached PrRiddle.zip file. This is a console program, which runs the problem 1000 times and reports the average number of days that were needed for the liberation of the prisoners. Do enjoy. Dimitre.
|
|
IP Logged |
|
|
|
dimitre
Newbie
Posts: 5
|
|
Re: 100 prisoners & a light bulb
« Reply #188 on: Oct 14th, 2003, 7:15am » |
|
Ooopsss... I don't see the attached file... Sorry, here's just the .cs file: using System; using System.Collections; namespace PrRiddle { /// <summary> /// Summary description for Class1. /// </summary> class TestPrRiddle { /// <summary> /// The main entry point for the application. /// </summary> public static ArrayList unRegistered = new ArrayList(100); [STAThread] static void Main(string[] args) { bool theBulb = true; int iteration = 0; ushort day = 0; ArrayList thePrisoners = new ArrayList(100); for(int i = 0; i < 100; i++) { thePrisoners.Add(new Prisoner()); unRegistered.Add(thePrisoners[i]); } Random rand = new Random((int) DateTime.Now.Ticks); int numruns = 1000; int totalDays = 0; int iter; for( iter = 0; iter < numruns; iter++) { while(Prisoner.totalRegistered < 100) { iteration++; theBulb = true; for(day = 1; day <= 100; day++) { int next = rand.Next(0, 100); ((Prisoner)(thePrisoners[next])).visitRoom(theBulb,iteration, day); } } totalDays += (iteration - 1) * 100 + day; } Console.WriteLine("Average days: {0}", ((float)totalDays) / numruns); } } class Prisoner { public static int totalRegistered = 0; public static int totalUnRegistered = 100; bool registered = false; int iterRegistered = -1; public void visitRoom(bool theBulb, int iteration, ushort day) { if(theBulb && !registered) { totalRegistered++; totalUnRegistered--; registered = true; iterRegistered = iteration; TestPrRiddle.unRegistered.Remove(this); return; } //else if(registered && iterRegistered == iteration) theBulb = false; } } }
|
|
IP Logged |
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: 100 prisoners & a light bulb
« Reply #189 on: Oct 14th, 2003, 7:27am » |
|
Dimitre, Maybe I don't understand your solution, but let's examine the following (unlikely) case: Mark all prisoners with 1..100. BEGIN: all prisoners are unregistered. 1st Iteration: Prisoner #1 is called every single day (100 times) After 1st iteration: prisoner #1 registered; Prisoners 2..100 unregistered. 2nd iteration: Prisoner #1 called first 99 days. He tyrned on the light on the first day, and didn't turn it off as it wasn't second time during the iteration in which he became registered. Therefore, the light is on. Day 100 of 2nd iteration, prisoner #2 is called. It is the last day of the current iteration and the light is on and the prisoner is unregistered => he announces that all prisoners have already visited the room. Result: all prisoners die on the 200'th day
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: 100 prisoners & a light bulb
« Reply #190 on: Oct 14th, 2003, 7:40am » |
|
In addiition, I tried looking at your code. I'm not very fluent at C, but as far as I understand, each prisoner maintains a record of total number of registered and unregistered prisoners -- and the individual prisoner has no way of knowing that... Please forgive me if I didn't understand the code (quite likely).
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
dimitre
Newbie
Posts: 5
|
|
Re: 100 prisoners & a light bulb
« Reply #191 on: Oct 14th, 2003, 8:21am » |
|
You're absolutely right! My program shows that the prisoners will be unsuccessful from 3 to 7 times in one million. So, it seems at least not too risky as a strategy. I don't know the statistics, but probably flying on a plane or having a tooth pooled is much more dangerous. Certainly, I must think about an exact solution -- sorry I have been dealing with this problem just since two days. Cheers, Dimitre.
|
|
IP Logged |
|
|
|
dimitre
Newbie
Posts: 5
|
|
Re: 100 prisoners & a light bulb
« Reply #192 on: Oct 14th, 2003, 8:26am » |
|
on Oct 14th, 2003, 7:40am, BNC wrote:In addiition, I tried looking at your code. I'm not very fluent at C, but as far as I understand, each prisoner maintains a record of total number of registered and unregistered prisoners -- and the individual prisoner has no way of knowing that... Please forgive me if I didn't understand the code (quite likely). |
| No, this is OK. The number of registered prisoners is a static property (belongs to the whole class), not an individual property of any Prisoner. It is not used by any prisoner. The program itself finds out when all prisoners have registered. Of course, in real life the last prisoner will announce the event. As the program simulation showed, the chance of an eror is 3 to 7 in one million. Cheers, Dimitre.
|
|
IP Logged |
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: 100 prisoners & a light bulb
« Reply #193 on: Oct 14th, 2003, 9:37am » |
|
It is true that the risk of 3-7/1000000 is small, and in real life would probably be worth taking. Previous suggestions along this line included calculating a number of days after which the probability of fail is below a given threshold. However, the challenge in this riddle is to be 100% sure saving the prisoners at a minimal number of days.
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
Dimitre Novatchev
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #194 on: Oct 14th, 2003, 11:08am » |
|
on Oct 14th, 2003, 9:37am, BNC wrote:It is true that the risk of 3-7/1000000 is small, and in real life would probably be worth taking. Previous suggestions along this line included calculating a number of days after which the probability of fail is below a given threshold. However, the challenge in this riddle is to be 100% sure saving the prisoners at a minimal number of days. |
| While I am not arguing about this, a good solution to a statistical problem has to be statistical -- and this particular problem is a good proof of that. The exact solution (yes, I found it myself -- one "responsible" prisoner will count every new registration and such a registration will happen only once per iteration) bears no risk, but the people will have to stay in jail much longer (and the probability to die while staying there is higher than the probability to die if they implement the statistical solution). To put it in other words, a failure using my solution highly contradicts the condition that the choice of a prisoner is made in a truly random way. I also plan to improve my solution -- by studying the "failure data" I would probably be able to modify the solution to something like this: "Only report success if the iteration number is higher than 7" Something like this may significantly reduce even this tiny probability. Cheers, Dimitre.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: 100 prisoners & a light bulb
« Reply #195 on: Oct 14th, 2003, 12:21pm » |
|
Dimitre, Your code doesn't appear to work the way you say it does. Nowhere do I see a check on whether or not the light is on on the last day of the iteration. Instead, I see the check "while(Prisoner.totalRegistered < 100)", which, as BNC pointed out, is information no prisoner has. There are other strange things in the code as well. For totalDays, you add "totalDays += (iteration - 1) * 100 + day;", but there is no point in adding "day", because the for loop for the "day" variable will only end when day == 101. According to my analysis, your program randomly selects prisoners in "iterations" of 100 days, and after they've all visited the living room, quits at the end of the next iteration. So your program never fails, but it assumes prisoners have information they couldn't actually have. To fix your code, I would do the following: -replace "while(Prisoner.totalRegistered < 100)" with "while(theBulb == false)" -this would also necessitate replacing "bool theBulb = true;" with "bool theBulb = false;" -add two more 'tally' variables: numFailureRuns and totalFailedDays, to tally up the number of times out of numruns this method fails, and the total number of days that this takes. -when you tally up the days, use an if statement on Prisoner.totalRegistered to see if it failed or succeeded, and add the number of days used to either totalDays or totalFailedDays. -now you can calculate statistics for both success and failure separately, and also the probability of failure. That being said, fixing the program doesn't fix the underlying method. We are looking for a failure-proof method, and your is ultimately an opt-out method. If nobody shows up who will turn the light off, then you assume everybody is registered and nobody appeared twice. No opt-out method can work, because you're never guaranteed that the right person will show up when you need them to opt out.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Dimitre Novatchev
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #196 on: Oct 14th, 2003, 12:50pm » |
|
James, Indeed I have found some bugs, which I'm now in the process of fixing. Please, ignore my previous messages. As for finding an "optimal" exact solution, it will by definition be much longer than an optimal probabilistic one. Therefore, it seems unlikely to me that the "common" solution can be improved radically. Cheers, Dimitre.
|
|
IP Logged |
|
|
|
Rezyk
Junior Member
Gender:
Posts: 85
|
|
Re: 100 prisoners & a light bulb
« Reply #197 on: Oct 14th, 2003, 7:00pm » |
|
When coding/thinking about this problem, I found it useful to use this generalized parameterization of previously suggested optimizations: For each prisoner's visitation, he follows 4 steps: 1) If the bulb is on, lookup the previous day's passable items, add them to your inventory, and turn the bulb off. 2) Check if you have [winCondition] within your inventory. If so, assert that all prisoners have visited. 3) If the day includes a creation/destruction, modify your inventory appropriately. 4) Decide whether or not to pass some items to the next visitor, based on the day and contents of your inventory. If so, subtract the items from your inventory and turn the bulb on. I've made up some pseudocode for the next sections; hopefully it's not too illegible. Generally I list a number of days followed by the creation/destruction/decision/passing directives that apply within each of those days. As an example, here's what SWF's 10/28/2002 system might look like (if I interpreted it correctly): Code:Set each inventory to 1 token. Set winCondition to 100 tokens. first day: Pass 1 token. next day: Destroy 1 token. If tokens>0, pass 1 token. next day: Create 1 token and 1 crown. Pass nothing. Repeat 8 times { next day: If tokens>0 and badges==0, pass 1 token. next day: Create 1 badge. If badges>1, pass 1 badge. } next day: If badges>1, pass 1 badge. next day: Pass nothing. next 2252 days: If tokens>12*crowns+11*badges, pass 1 token. next 1610 days: if badges>0 and tokens>10 and crowns==0, pass 1 badge and 11 tokens. Repeat indefinitely { next 302 days: If tokens>12*crowns+11*badges, pass 1 token. next 358 days: If badges>0 and tokens>10 and crowns==0, pass 1 badge and 11 tokens. } |
| Estimated mean: 3535.6 days Standard deviation: 607 days based on a sample of 11 million runs Here's my new suggested system: Code:Set each inventory to 1 token. Set winCondition to 128 tokens. first day: Create 28 tokens and 1 crown. Pass 29 tokens and 1 crown. next day: If tokens==30, pass 30 tokens and 1 crown. next day: If tokens==31, pass 31 tokens and 1 crown. next day: If tokens==32, pass 32 tokens and 1 crown. next day: If tokens==33, pass 33 tokens and 1 crown. next day: If tokens==34, pass 34 tokens and 1 crown. next day: If tokens==35, pass 35 tokens and 1 crown. next day: If tokens==36, pass 36 tokens and 1 crown. next day: If tokens==37, pass 37 tokens and 1 crown. next day: If tokens==38, pass 38 tokens and 1 crown. next day: If tokens==39, pass 39 tokens and 1 crown. next day: If tokens==40, pass 40 tokens and 1 crown. next day: If tokens==41, pass 41 tokens and 1 crown. next day: If tokens==42, pass 42 tokens and 1 crown. next day: If tokens==43, pass 43 tokens and 1 crown. next day: If tokens==44, pass 44 tokens and 1 crown. next day: If tokens==45, pass 45 tokens and 1 crown. next day: If tokens==46, pass 46 tokens and 1 crown. next 2 days: If tokens==47, pass 47 tokens and 1 crown. Repeat 2 times: { next day: If tokens%8>=1 and crowns==0, pass 1 token. next day: If tokens%8>=2 and crowns==0, pass 2 tokens. next day: If tokens%8>=3 and crowns==0, pass 3 tokens. next day: If tokens%8>=4 and crowns==0, pass 4 tokens. next day: If tokens%8>=5 and crowns==0, pass 5 tokens. next day: If tokens%8>=6 and crowns==0, pass 6 tokens. next 2 days: If tokens%8==7 and crowns==0, pass 7 tokens. } Repeat 3 times: { next day: If tokens%4>=1 and crowns==0, pass 1 token. next day: If tokens%4>=2 and crowns==0, pass 2 tokens. next 2 days: If tokens%4==3 and crowns==0, pass 3 tokens. } next 380 days: If tokens%2==1 and crowns==0, pass 1 token. next 330 days: If tokens%2==1, pass 1 token. next 330 days: If tokens%4>=2 and crowns==0, pass 2 tokens. next 300 days: If tokens%4>=2 and (crowns==0 or tokens%4==2), pass 2 tokens. next 300 days: If tokens%8>=4 and crowns==0, pass 4 tokens. next 200 days: If tokens%8>=4 and (crowns==0 or tokens%8==4), pass 4 tokens. next 1650 days: If tokens>=8 and crowns==0, pass 8 tokens. next 500 days: If tokens>=4 and crowns==0, pass 4 tokens. next 300 days: If tokens>=2 and crowns==0, pass 2 tokens. Repeat indefinitely: { next day: If tokens>=1 and crowns==0, pass 1 token. } |
| Estimated mean: 3532.0 days Standard deviation: 752 days based on a sample of 1 million runs The gist of what happens: The first 20 days is just Salem's leader selection (with a small tweak at the end). Then there are 5 short cycles which attempt to consolidate tokens into groups of 8 and 4. These are just an optional optimization -- not sure how beneficial they really are. Next starts off as AlexH's binary stages: all the tokens are grouped into pairs, then these pairs are made into groups of 4, which are made into groups of 8. Note that the leader often hoards tokens against protocol, due to greed or wisdom. Then, for the next 1650 days, we switch to straight leader-collection of as many 8's as possible. 61% of all cases conclude during this stage with an average total of 3042 days. If no conclusion is made after 1650 days, we presume that one of the previous consolidation steps failed, and start backtracking to send all missed groups of 4 to the leader, breaking up any missed 8's as well. After a while, we presume that a smaller consolidation step failed and start looking for groups of 2, and then finally gather everything left as singles.
|
« Last Edit: Oct 14th, 2003, 7:05pm by Rezyk » |
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: 100 prisoners & a light bulb
« Reply #198 on: Oct 15th, 2003, 7:39pm » |
|
Well done, Rezyk. It is good to see some serious attempts at this problem. I tried out your method it works as advertised: after 750,000 tries got an average of 3531.5 days with SD of 751. There appears to be room for more improvement. For example extending to first stage to 48 tokens from 47 gave a mean of 3530.5, but that was for only 500,000 tries.
|
« Last Edit: Oct 15th, 2003, 7:41pm by SWF » |
IP Logged |
|
|
|
Rezyk
Junior Member
Gender:
Posts: 85
|
|
Re: 100 prisoners & a light bulb
« Reply #199 on: Oct 19th, 2003, 4:11pm » |
|
Thanks, SWF. You're right; there is definitely room for improvement. Most of the stage lengths have only been optimized to the best multiple of 30-100 days, as opposed to the best day. Is there a well-established method one could use for efficiently optimizing the stage lengths to get a local minimum? My clumsy manual guess-tweaking is rather slow/cumbersome.
|
|
IP Logged |
|
|
|
|