Author |
Topic: 100 prisoners & a light bulb (Read 166679 times) |
|
thelonious
Newbie
Posts: 11
|
 |
Re: How to Solve 100 prisoners & Light bulb?
« Reply #125 on: Oct 29th, 2002, 8:46pm » |
|
Thanks for the info, william wu. The point I was making it that if we can assume an i.i.d. selection set, then the optimal solution would be to wait the number of days required for it to be guaranteed that everyone was selected once. If the case can be made that that guarantee can never be reached probability wise, then wouldn't that indicate that we didn't have a proper i.i.d.? If we do have a valid i.i.d. set, then don't the chances that there are any prisoners not selected yet have to become 0% well before 3000 days? Knowing that we have an i.i.d. set in a way puts a bias on our expected randomness. Or do it? I'm thinking along the lines of that somewhere in the definition of i.i.d. the case for non-selection after a certain number of selections is ruled out. But I know not.
If you can derrive this conclusion from the definition of an i.i.d. set, then any other solution becomes less than optimal. But I suppose a possible set could be constructed that causes the other solutions to work optimally.
|
| « Last Edit: Oct 29th, 2002, 8:51pm by thelonious » |
 IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #126 on: Oct 29th, 2002, 9:27pm » |
|
I'm not sure what you're trying to say. Firstly I think you mean u.a.r; in my previous post I just threw in i.i.d. as another common term that's good to know, but u.a.r doesn't mean the same thing as i.i.d.. Sorry that was probably confusing on my part. Uniformly At Random means that everytime the warden chooses an integer between 1 and 100 using his calculator's random number generator, each of those integers is equally likely to be picked. So the probability of picking any particular number is 1/100. These numbers are chosen with replacement, so if the number "13" is picked in the first iteration with probability 1/100, then in the second iteration, the probability of picking "13" is still 1/100. There is never a "guarantee" that everyone will be selected after so many days have passed. There is always a small yet nonzero probability that the warden's random number generator always misses some of the integers ranging from 1 to 100. So you can't just wait a certain amount of time and then make the assertion (although perhaps that's the simple algorithm most prisoners would come up with, unless they had a hacker or mad scientist in their bunch, or maybe someone from this forum  ). However, the light bulb gives us hope, because we can use it to record visits to the room, and eventually truly prove to ourselves that everyone has been in the central living room at some time. When we say that such and such algorithm being currently disputed takes about 3500 days before completion, that's an average running time; we can't get an exact running time because of the random prisoner choosing. An algorithm with average running time of 3500 days could still consumes 5,000,000 days for a particularly bad case.
Apologies if I misunderstood your post.
SWF: yes, we are interested 
|
| « Last Edit: Oct 29th, 2002, 9:29pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #127 on: Nov 1st, 2002, 6:36am » |
|
Here is more information on the method which gives a mean release time of 3535.6 days (based on simulating 11 million cases). Standard deviation is around 607 days, and median is 3370 days.
First the basic version will described, which takes an average of 3600 days and may not be much different from previous discussions here. A prisoner is designated the primary counter, and 8 other prisoners are designated as secondary counters. At the beginning everyone has a count of 1, call this countA. There is also a value assigned to each person for number of times this person is responsible for getting his count to 11 and signaling in stage 2, call this countB. The 8 secondary counters start with countB equal to 1, while everyone else, including the primary counter start with countB of 0. The primary counter also has the responsibility to collect 12 individual counts. The primary counter tracks an additional count, countC, which is number of individual counts collected. Primary counter needs this to distinguish from the counts collected in groups of 11 in Stage 2. The number of individual counts each person, except the primary counter, is required to collect is 11 times his value for countB, while the primary counter needs to collect 12 + 11*countB. Each prisoner has his own value for countA and countB, so maybe I should subscript them like countAi.
The first time through, Stage 1 is 2252 days long. If somebody is called in during this stage and the light is off, anybody whose value for countA (except for primary counter who compares countC) is greater than the number of individual counts he is assigned to collect must turn the light on and subtract 1 from his value for countA (and also from countC if this person is the primary counter). If somebody is called into the room in Stage 1 and the light is on, if his value for countA (countC for primary counter) is lower than the number of individual counts he is required to collect, he turns the light off and increases his value for countA by 1. When the primary counter collects an individual count in Stage 1, he also must increase his value for countC, and claims it is over if his value for countA is 100 (but that is extremely unlikely to occur the first time through Stage 1).
The first time through, Stage 2 is 1610 days long. If the light is on the first day of this stage, the prisoner called in that day must increase his count (as in Stage 1) by 1 and shut the light off, even if he has already collected his share of individual counts. The prisoner called the first day of stage 2 then behaves as if the light were off when he entered the room. When the light is off anyone other than the primary counter with countA >= 11 and countB >= 1 must turn the light on, subtract 11 from his value for countA and 1 from his value for countB. If the primary counter enters and the light is on, he increases his value of countA by 11, turns the bulb off and calls the guard if his value for countA equals 100.
Repeat Stages 1 and 2 with lengths of 302 and 358 days respectively until the primary counter collects 100 counts. Also, on the later passes through Stage 1, on the first day of the stage, if the light is on whoever is called that day increases his value of countA by 11. If that person is not the primary counter, he must also increase his value for countB by 1. Thus, he has picked up the responsibility to signal in Stage 2 from one of the former secondary counters, and somebody could become responsible for signalling more than once in Stage 2.
The above is for the primary and secondary counters named in advance, but an improvement of about 65 days can be obtained by establishing them in a Stage 0. By doing this the primary counter will typically start with a countA of 3, and secondary counters with countA=2. This improves over the basic method where they start with countA=1, but it runs the risk of having some prisoners have to count to 11 more than once (countB>1). This is running long, so I will give the details of Stage 0 some other time.
Due to the complexity of explaining this method just the prisoner organization meeting at the beginning could take 3536 days.
|
|
IP Logged |
|
|
|
-Tom-1
Newbie
Posts: 2
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #128 on: Nov 7th, 2002, 2:53am » |
|
ok well if u ignore everything at the top and read the last lines it says one night they meet somewhere, so where can 100 people meet? well of corse in the centeral living room so then all of them have been there - simple
|
|
IP Logged |
|
|
|
-Tom-1
Newbie
Posts: 2
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #130 on: Nov 7th, 2002, 6:41am » |
|
ok well i say thats answer
|
|
IP Logged |
|
|
|
bound_master
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #131 on: Nov 9th, 2002, 12:22am » |
|
Assuming hard obstacles to pass, such as
-the prisoners in the cells can't see the flickering light
-only one meeting occurs before the actually visitations to the living room.
I think the fastest way out of there (using the light bulb) would be:
-Break the light bulb into 99 pieces, whoever is the first one there...then whenever someone new enters the room for the first time, he/she takes a piece of broken glass, until none is left. 
Without using the light bulb:
-leave some kind of mark behind, such as Roman numeral markings on the wall (1-100, each representing a prisoner), or a piece of clothing if your visiting for the first time, or dismembered fingers, or even fingernails. Once 100 markings or items are left behind, then you know 100 have been there.
Of course this only works if the janitor doens't come by to clean the room. In that case, an assasination attempt can be done on the janitor with a sharp tooth shot through an empty cylinder (pen) that hits him in the neck and kills him instantly!
See how simply and quickly it can be done.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #132 on: Nov 10th, 2002, 7:54am » |
|
you could also unscrew the lightbulb, and then screw it back in 99 degrees, each next (new) prisoner unscrews 1 degree, when it falls everyones been there..
But prisons are notoriously paranoid abotu people getting to the lightbulbs, sinc ethey might kill themselves with the glass (or attack the guards)..
So it's not really an option after all..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #133 on: Nov 11th, 2002, 7:53pm » |
|
Here is the detail on Stage 0 that I mentioned would be forthcoming in my Nov 1, 2002 post. This defines the way the primary and secondary counters are established in the first 21 days. This may be somewhat boring, but is given to document the most efficient method so far. Everyone starts with countA set to 1 and countB to zero (see my earlier post for definitions).
In this stage I tried to reduce chance of somebody picking up double responsiblity for secondary counting (countB<2), but it can still happen. Also tried to assign counting duties in a way which gives the counters a head start by collecting individual counts from others. There is probably room for improvement here.
Day 1: This prisoner subtracts 1 from his value for countA.
Day 2: If this prisoner did not enter in Day 1, subtract 1 from countA and turn light on, otherwise leave light off.
Day 3: This prisoner is designated the primary counter. If light is on, turn it off, and if countA is 1, set it to 3 otherwise set it to 2. If the light was off when entering the room add one to countA (i.e. same prisoner was called all three days and countA becomes 1 again). Most likely countA for the primary counter will be 3 which is a pretty good start in collecting 12 individual counts.
The next pair of days is repeated for i=0 through 7:
Day 3+2*i+1: If light is on, turn it off, add 1 to countB (i.e. become a secondary counter). If light was off when entering, keep light off if countA is 0, otherwise subtract 1 from countA and turn light on.
Day 3+2*i+2: This day try to make assign a secondary counter, but postpone the responsiblity to next prisoner if today's prisoner is already a primary or secondary counter. If today's prisoner is already a primary or secondary counter then turn light on, and if light was already on add 1 to countA. If today's visitor is not a primary or secondary counter add one to countB (become a secondary counter), add 1 to countA if light is on, and turn light off.
Day 20: If light is on and today's prisoner is not a primary or secondary counter then add 1 to countB and turn light off.
Day 21: If light is on add 1 to countB, turn light off.
|
|
IP Logged |
|
|
|
luke's new shoes
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #134 on: Nov 12th, 2002, 3:27pm » |
|
is it possible there is more than one switch that controls the light?
if so, the on off possitions of the switches can be used to convey data to the other prisoners.
|
|
IP Logged |
|
|
|
Changer
Guest
|
|
A variation of the problem
« Reply #135 on: Dec 6th, 2002, 12:22pm » |
|
This question is a variation of one that I had read before with 23 prisoners and 2 switches. I found a link to one retelling of it on the IBM website, http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/
(choose July 2002)
On the original website where I had read this, some mathematics professor had offered up a proof of the solution which I can't remember but seemed correct. The solution given on the IBM website was essentially the counter method.
|
|
IP Logged |
|
|
|
Devarajan
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #136 on: Dec 22nd, 2002, 5:33pm » |
|
Hi all,
I have a simplest soln. for this problem..but i dont know whether that is the efficient way but i know this is perfectly right..here you go..
During the meeting,one person(calling him coordinator or counterer) decides that he will always switch of the light whenever he goes to the room and also start counting the no. of times he switched off.Every other person will switch on the light once and does nothing every other time..On the 100th time the co-ordinator switches off will be sure everybody reached this cell atleast once..
Hey guys, let me know if this soln. is convincing to you all..
Thanks,
Deva 
|
|
IP Logged |
|
|
|
SPAZ
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #137 on: Dec 31st, 2002, 10:50pm » |
|
one other solution is just when your in the room yell allowed and say" has anyone not been in yet?" once someone does this and no reply is given then your free...
all solutions with wait this many days and so forth are not 100% because it is possable that if random one person will never be picked for going in the room
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #138 on: Dec 31st, 2002, 11:25pm » |
|
Deva: That solution works but is suboptimal. It's a long thread, but if you read it from the beginning you'll see a discussion of it from a few months back. Now we're studying solutions that use multiple counters who merge their data over time.
SPAZ: I guess I'll have to add that the cells are soundproof.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Snyder8
Newbie
Gender:
Posts: 3
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #139 on: Jan 7th, 2003, 12:54pm » |
|
Ok, I'm not even going to attempt this riddle, instead I'll take a different route. I think I found out where the riddle came from, http://baranduin.us/fics/blissfulnights10.html . It appears to have originated in a Lord of The Rings book although I'm not 100% positive. I read the section with the riddle and Frodo never seems to figure it out, which leads me to believe that there is no answer and we are all wasting our time. I'm not sure if he could have wrote something that wasn't his original idea and without an answer provided in the book I think I'm going to steer clear of this riddle. I havent spent that much time researching the origin, so there's a good chance I may be wrong, just don't hold me to this. If anybody else finds anything about the origins of the riddle it might be helpful to solving the problem. Until then we might be searching for something that doesnt exist... If I find anything else I'll post it here... don't lose any sleep over this one, I'm skeptical of an answer... you should be too
But on a side note... this problem uses a candle instead of a lightbulb, which eliminates the switch.
|
| « Last Edit: Dec 21st, 2003, 11:29am by Icarus » |
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #140 on: Jan 7th, 2003, 1:51pm » |
|
Hahaha  So you were serious in that e-mail! I'm pretty sure it didn't come from LOTR. The author of the fanfiction phrases the riddle the way I did. I'm responsible for making up the storyline that says prisoners will be killed explicitly for their stupidity, and also introducing the MENSA aspect of story which is not present in the LOTR context. The puzzle might have originally come from Hungary, since apparently it was making the rounds of Hungarian mathematician parties last year according to an IBM research site.
|
| « Last Edit: Jan 7th, 2003, 1:52pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Felipe de Toro
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #141 on: Jan 13th, 2003, 5:50pm » |
|
(Sorry, my english is awfull. I'm from Chile).
The solution is very simple.
First think that there are only 5 prisoners (for simplyfication).
1 2 3 4 5
Prisoner number 4 (for example) will count the first visit of each other prisoner to the room of the light bulb.
If a prisoner (not number 4) goes to the light room and it is his first time and the light is OFF, he must turn it ON. This was his first time.
If a prisoner (not number 4) goes to the light room and it is his first time and the light is ON, he must leave it ON. In this case, he consider that this is NOT his first time. He will wait for another chance (with the light turned OFF).
If a prisoner (not number 4) goes to the room and it is not his first time, he must leave the light just as he found it.
If prisoner number 4 goes to the room, he look at the light. If it is ON, it means that another "new" prisoner (prisoner in first time) went to the room. If it is OFF, it means than from his last visit to the room, no other "new" prisoner went. If the light is ON he MUST turn it OFF, then another "new" prisoner can turn it ON. He is the only one that can turn OFF the light.
He count every "new" prisoner (when the light is ON) and when he find that the number is 4 (plus him=5), then he knows that every prisoner went to the light bulb room.
You can apply it for 10, 20 and even 100 prisoners.
Bye!
Felipe de Toro.
|
|
IP Logged |
|
|
|
Felipe_de_Toro
Newbie
Posts: 1
|
 |
Re: How to Solve 100 prisoners & Light bulb?
« Reply #142 on: Jan 13th, 2003, 6:47pm » |
|
Sorry, I'm very embarassed. My little brother, Juan Pablo, told me that this problem was unsolved here (he must learn a little of english), and I didn`t read all the messages in the forum before I sent my solution. I just posted in the forum he wanted. Nevertheless I will keep looking for a better solution.
Thanks.
Felipe de Toro
|
|
IP Logged |
|
|
|
rilgin
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #143 on: Jan 19th, 2003, 12:55am » |
|
I do not have the mathematical or statistical skills to evaluate the following method which is similar to the other ideas posed but may add additional efficiencies. It has some intuitive possiblities.
My wrinkle is a method to dynamically identify "counters" during a first state and increase the chances that everyone is counted during that period. I have used the first 100 days but math might specify a different period. My thoughts are not complete but I wanted to see what people here thought.
You divide the 100 days into the first 4 days then into groups of 3. In each grouping other than the first 4 days, the "second" prisoner will be the counter or he will pass the count to the "third" prisoner in the group as follows. The first four days are similar to the rest but you can save a day of efficiency with the counter being the "third" or "fourth" day.
Day One: Turns light on.
Day Two: If not the same as Day One, Prisoner toggles the Room light off.
Day Three (1st potential Counter): If the room light is
off, and Day Three is a new prisoner, he keeps room light off (this just tells Day 4 that the first three days were all new prisoners and that day 4 will be the counter). If there has been one or more duplicate prisoners, Day Three tells Day 4 that Day Three is the counter by turning light on.
Day 4 (2nd potential counter): Is told by Day Three if Day Three wants him to count (light off) OR that Day Three is keeping the count (light on). If Day 4 Is the counter, he knows that so far the count is 3. He then counts himself and leaves the light off for Day 5. If the Day 4 prisoner is not the counter but has been previously in the room (i.e. already counted), he also leaves the light off. On the other hand, if Day 4 is not the counter and has not been in the room (i.e. not counted yet), he leaves the light on for the first prisoner in the next group. This will pass responsiblity for future reporting to that prisoner.
********** Next Groups are in Threes **********
First Day: If light is off, he ignores previous grouping (no responsibility has been passed to him). If light is on, he knows that previous Day Prisoner was both new to Room AND needs to be counted. In other words, he has been passed a count of 1 to utilize now or to pass on later in another stage. He then reports to Second Day by leaving the light on to pass 1 or off to pass 0.
Day Two: If Light is on AND Day Two Prisoner is new, he leaves light on to pass information that the group count is 2 and that counting responsiblity has been passed to the Day Three Prisoner. If he can not pass 2, he keeps the counting responsiblity by turning light off.
Day Three: If light is on, he becomes the counter (adding himself in) and turns the light off. Note that he knows that his count starts at 2 plus his own status. If the light is off, he knows that he is not the counter and must tell the First Day Prisoner of the next group his status: "on" for you now have the responsibility for counting me or "off" for there is no information or responsibility to pass.
At the end of the 100 days, you will have 33 or 34 counters (depending on what you do the last day). You will still have some counters with only 1 (those First Day Prisoners who have been passed responsibilities and were not able to pass them on yet). One would expect that the longer you go on, the more chance you will be able to slip these in to the main count. The other counters will have variable counts. You will have may counters with 3, some with more (if they have been a counter a few times) and the rest with 2.
The intuitive benefits of this method is that you have eliminated a lot of prisoners from all further responsiblities (including counters with 0 counts). This may increase efficiencies against 8 or 10 fixed counters from cycles through the prisoners because prisoners can not report because the light is being used already.
Please let me know if you think this method has some promise in shaving some time off the optimum method.
Ben
|
|
IP Logged |
|
|
|
Phil
Newbie
Posts: 38
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #144 on: Jan 29th, 2003, 6:13pm » |
|
I can't compete with the solvers of this riddle figuring out optimum techniques, but I just thought I'd throw a monkey wrench into your calculations. The numbers would come down significantly if prisoners could transfer more than 1 bit of information, would it not?
The riddle says the men are taken out of the room at the end of the day. It does not say when they're put in the room, but if they could convince the jailer to give them a full day in the room, in right after midnight, out right before midnight, then you can pass information in the temperature of the bulb. The bulb could be left on, or off but hot, or off but warm, or off and cold. That's double the info, and I bet the extra info could be extremely useful.
The other solution would be to always leave the bulb off, but unscrew it slightly the first time you enter the room. If each person could accurately rotate it the same amount, you'd know exactly how many people had been in the room (100 fifteen-degree turns might completely room the bulb, for example). If not, then simply the amount it was unscrewed in broader, 90- or 180-degree terms could be an additional way to pass information.
|
|
IP Logged |
|
|
|
just some moron
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #145 on: Jan 31st, 2003, 9:16am » |
|
bah the best sollution would be to take off a shirt or a shoe or a sock if it's your first time in the room so when there's 100 of them you can tell the warden all 100 have been in the room the riddle never asked for how many days it would take so i don't know what's everyone doing ^_^
|
|
IP Logged |
|
|
|
steve z
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #146 on: Feb 9th, 2003, 7:26pm » |
|
It is obvious that just some moron's reply is the best. I thought of a similar one right off the bat. They all agree at the meeting for the first person to break the bulb into 100 pieces and put 99 in the corner of the cell. The one peice he takes with him- because it was his first time in the cell. This goes on until all the peices are gone. That and moron's solution are the quickest and most logical ways aside from putting marks on the wall for first timers. It is most likely that prisoners do not have the capacity to run 100-day cycle probabilities in their head, or organize a leader. Anyways, that is the solution, there is no other. If you think there is, e-mail me at szellers@umd.umich.edu. Peace.
|
|
IP Logged |
|
|
|
steve z
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #147 on: Feb 9th, 2003, 7:33pm » |
|
For clarification, I only read the first page of replies and didnt realize my exact reply above had already been posted, although I expected it to be since there were six pages already here. peace
|
|
IP Logged |
|
|
|
GRAND_ADMRL_THUORN
Newbie
THE DARK TOWER IS NEAR!
 
Gender:
Posts: 10
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #148 on: Feb 12th, 2003, 11:34am » |
|
theres nothing more that I hate, than a riddle that has no "DEFINATE" answer, but o-well, at least its forced us to think and that is always a GOOD thing. 
|
|
IP Logged |
|
|
|
john
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #149 on: Feb 12th, 2003, 2:05pm » |
|
I just thought of this, and I didn't feel like scanning through the 6 pages of previous posts to see if this has been suggested, but here goes:
Take the average life of a lightbulb and divide by 100. This number (x) is the number of hours that each prisoner should leave the lightbulb in the "on" position whenever they go to the living room, but ONLY THE FIRST TIME. After that, they don't touch the dang thing. As soon as a prisoner witnesses the bulb burned out, he/she can assume that all of the prisoners have been to the livingroom.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Notify of replies
Send Topic
Print