Author |
Topic: 100 prisoners & a light bulb (Read 166687 times) |
|
tim
Junior Member
Posts: 81
|
 |
Re: How to Solve 100 prisoners & Light bulb?
« Reply #50 on: Jul 29th, 2002, 8:46pm » |
|
No, it needs a stronger guarantee than that. For example, if one prisoner goes through once only, and it happens to be when the light is already on. The leader will never count that prisoner. In fact, the same prisoner could go through a million times with the light on (consecutively if necessary) and still not be counted.
You need a guarantee more along the lines that no prisoner will be scheduled to go to the living room only a finite number of times. This is true with probability 1 for any infinite random sequence, so isn't too restrictive.
|
|
 IP Logged |
|
|
|
S. Owen
Full Member
Gender: 
Posts: 221
|
|
Every prisoner will enter the room at some point
« Reply #51 on: Jul 29th, 2002, 8:55pm » |
|
Yes, I agree - this is given in the problem since the warden selects prisoners "at random", presumably meaning uniformly at random, blah blah blah. We don't have to worry that some prisoner will never make it in there, or can only make it in there a finite number of times.
|
|
IP Logged |
|
|
|
tim
Junior Member
Posts: 81
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #52 on: Jul 29th, 2002, 9:12pm » |
|
I'll just reiterate my earlier comment that to a mathematician, "probability 1" does not mean "always" 
|
|
IP Logged |
|
|
|
pa0pa0
Newbie
Posts: 16
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #53 on: Jul 30th, 2002, 10:43am » |
|
Salem's modification of the leader method is extremely nice.
But it might still be advisable to decide on the leader during the initial meeting, choosing the person who appears to be youngest and/or healthiest.
Loss of the leader before they get out causes certain disaster; loss of other prisoners only might cause disaster, depending on whether they die before or after they have been counted by the leader.
(Sadly, the leader won't be able to tell the difference.)
Are the prisoners allowed to ask for a computer during the initial meeting, to run some actuarial simulations? That would help them decide whether Salem's modification buys them a shorter expected time that outweighs the greater risk.
|
| « Last Edit: Jul 30th, 2002, 10:46am by pa0pa0 » |
IP Logged |
|
|
|
johnP
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #54 on: Jul 31st, 2002, 4:55am » |
|
Would someone please explain to me why this "leader theory" would work? If the group selects a leader, there's a chance that in a million years, the leader (or anyone else) won't even be picked ONCE. I thought the text asked for a solution where the prisoners can be sure to get out. This shouldn't even take too many years... "infinite time" is nice in theory (but no guarantee for the leader theory to work), but you can't apply infinite time to this exercise as a real-life problem. It's been said by some here in the forum that the leader theory "guarantees success". This is a random selection! Who knows? The same person might be picked a billion times in a row. And then a billion more times in a row. Et cetera.
|
|
IP Logged |
|
|
|
pa0pa0
Newbie
Posts: 16
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #55 on: Jul 31st, 2002, 8:48am » |
|
on Jul 31st, 2002, 4:55am, johnP wrote:| The same person might be picked a billion times in a row. And then a billion more times in a row. Et cetera. |
|
Please tell me exactly *how* many times in a row you are talking about. You haven't given a number, you've just given a vague indication ("et cetera") of what you mean. Well, of course, I *know* what you mean, but that's not the point. The point is, that you cannot specify any sequence of warders' choices that would give a basis for your conern, except by giving a *rule* (of the form, for example, "choose the same person every day"). But the warders are not allowed to use a rule! The riddle says that! (That's what "random" means).
So your concern is baseless. (There are, actually, questions about whether it is physically possible to generate a truly random infinite sequence. Better send the riddle back to the makers.)
|
|
IP Logged |
|
|
|
johnP
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #56 on: Aug 1st, 2002, 4:55am » |
|
Sure thing. With random selection, it's possible for the same person to be picked as many times in a row as possible. "Infinitely" many times. And I'm not talking about a "rule", I'm talking about possible outcomes of random selections. When you elect a leader, a person that has to picked a number of times (100 or whatever), the problem is that no matter how many times you make a random selection from the prisoners, you don't have a guarantee that any prisoner will be picked - not even once. So how can you base an escape plan on that? An escape plan with a 100% guarantee of success? That's not possible. If you presume that every person will be picked, and the leader will be picked 100 times etc etc, THAT'S when you're applying a rule to the selection process. Random means there are no guarantees for who gets selected, when they get selected, if they ever get selected at all. And if you take this as a serious problem, you'll even have to get the prisoners out before they all die - there's no such thing as "infinite time" in this case. In "infinite time", there's a HUGE chance of all of them getting selected a HUGE number of times, but you can't base a watertight solution on it. I'm not using a rule to prove the "leader theory" is wrong, I'm simply telling you why it's wrong (if I'm right  ).
|
|
IP Logged |
|
|
|
tim
Junior Member
Posts: 81
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #57 on: Aug 1st, 2002, 5:41pm » |
|
The leader method does have a 100% chance of success. It just isn't infalible. To a mathematician the terms are not synonymous.
The problem asked for a 100% chance of success, and that's the condition that is satisfied. It is not infallible, just 100% likely to succeed. There is 0% chance of failure, but failure is still possible.
This may be confusing to those uninitiated in the deeper mysteries of mathematics
|
|
IP Logged |
|
|
|
johnP
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #58 on: Aug 1st, 2002, 10:34pm » |
|
Well, if that's correct, I suppose you might be right. I just intuitively thought a 100% chance was a guarantee that something would happen, and a 0% chance meant something would never happen. Maybe the problem should have an "M" next to it, as in "requires mathematical knowledge" or whatever that M means?
|
|
IP Logged |
|
|
|
Luni_B
Newbie
Are you afraid to die or just to live?
Gender:
Posts: 4
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #59 on: Aug 1st, 2002, 11:41pm » |
|
100 Prisoners and a Light Bulb
i have the absolute optimal answer to this riddle...
the VERY first person selected asserts that all 100 have been to the living room, and everyone will be let go...reguardless of whether he chooses to turn the light on
because they all had to meet in the living room to make the plan...100 people don't fit in any of the 1 person cells, hence, the living room!
|
|
IP Logged |
|
|
|
Rhaokarr
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #60 on: Aug 2nd, 2002, 12:27am » |
|
To the 'They've all been in the living room once at the meeting' arguments: The question does not state that they were allowed to get together in the living room - they may have been assembled in an exercise yard, or perhaps a mess hall.
I think the spirit of the question is also reinforced by the use of the word 'eventually'.
|
|
IP Logged |
|
|
|
Charlie949
Newbie
Common sense is not so common...
Gender:
Posts: 2
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #61 on: Aug 2nd, 2002, 1:50pm » |
|
Without using any of the previous assumptions, I have come up with a couple of ideas:
1. I think that only one, predetermined person can be the prisoner to state that everyone has been to the room. It should be the first person to revisit the room, namely, prisoner X. He/she is determined by having the first prisoner turn on the light on Day 1 and having person X turn it off. He/she will then know how many people have been in exactly once. Let's say this number is 10 (i.e. X revisited the room on Day 11). The next person to turn it on will be a) somone who has never walked into the room when the light was on AND b) someone who has never turned on the light. The next time X walks in and sees the light on, he will know that at least one new person has walked in since he was there last. X turns off the light and we repeat this process. Unfortunately, this example would take a minimum of 90 visits by X (10 original prisoners, 89 others and X), but it is sure-fire.
2. I am fairly certain that there is no way for any two (or more) specific prisoners to share information. If X wants to tell Y something by leaving the light off, Y wouldn't know if X left it off or hasn't been in at all.
Forgive me if these ideas overlap someone else's.
|
|
IP Logged |
|
|
|
mook
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #62 on: Aug 2nd, 2002, 4:11pm » |
|
charlie- the problem your theory is that more than one person will assume he's the leader. The first one who enters twice will flick the switch off, and assume he's the leader(correctly). Now, say that the next prisoner has never been in the room before, he turns the light on. The next day, someone who has already been in the room enters for the second time finding the light on, he too will flick it off thinking he's the leader.
The leader theory does require that he is picked at least 99 times to have been in the room after a different person has turned the switch on(or off, it doesn't really matter which way the switch needs to be left by the leader- he can trun it on, and if a new person finds it on he'll turn it off, and only the leader turns it on, or the leader turns it off, and no else can), but it does seem to be the only theory that will eventually be 100% accurate. To shorten that time, i like the having the meeting after x amount days, but assuming the meeting has to be beforehand, I think you can do better than the 2nd day leader. You can say whoever's selected on the third day is the leader. The person on the second day will have an important task, however, he must leave the switch on if he is coming in for the first time, and off if he came in on both days. This way the 3rd day leader would have to be selected to go into the room a minimum of 98 times as opposed to 99.
|
|
IP Logged |
|
|
|
jmlyle
Newbie
Gender:
Posts: 31
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #63 on: Aug 2nd, 2002, 10:16pm » |
|
Tim wrote:
Quote:The problem asked for a 100% chance of success, and that's the condition that is satisfied. It is not infallible, just 100% likely to succeed. There is 0% chance of failure, but failure is still possible.
|
|
Not quite. Here's what the problem states about the assertion that all prisoners have been to the room:
Quote:| the assertion should only be made if the prisoner is 100% certain of its validity |
|
The requirements say nothing about the certainty that this situation will ever occur. And it says nothing about finding an answer with a 100% chance for success.
And johnP said:
Quote:| If you presume that every person will be picked, and the leader will be picked 100 times etc etc, THAT'S when you're applying a rule to the selection process. Random means there are no guarantees for who gets selected, when they get selected, if they ever get selected at all. |
|
Well, I grant you that it's possible that at least one person might never get picked, but it's extremely unlikely as time goes on (to put it mildly). But it doesn't really matter, because as long as at least one prisoner has never gone into the room, then the only options for everyone are to stay in prison or get shot.
|
|
IP Logged |
|
|
|
dan
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #64 on: Aug 3rd, 2002, 7:22am » |
|
charlie's solution works, but within the first 100 days once the light is turned off nobody else should be allowed to turn it on so that nobody else will think he is the "leader".
|
|
IP Logged |
|
|
|
mook
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #65 on: Aug 3rd, 2002, 7:43am » |
|
you say no one else is allowed to turn the switch, but still, the prisoners won't know who the leader is, so they won't know that they're the else.
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #66 on: Aug 4th, 2002, 9:49pm » |
|
"First person in twice is the leader", proposed earlier in the thread by Salem, does work correctly and is nearly as good as it gets as far as I know. We can save a few extra days by not having the leader finding session last 100 days, but rather have it go for 29 days. The chance that we get more than 29 people going in before the first repeat is so small that we're better off taking the 71 extra days than hoping for that long shot (in terms of getting the lowest expected time served). That modification saves us about 68 days, but we're still left with the same ballpark of 25 years. Scroll back up and read salem's description, he lays out the different cases pretty clearly if you have any doubts.
The probabilistic answers aren't what was asked for but they are good points since they would be far superior if the prisoners were willing to take some risk for the gain of freedom.
|
|
IP Logged |
|
|
|
tim
Junior Member
Posts: 81
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #67 on: Aug 4th, 2002, 10:48pm » |
|
jmlyle: Quote:| The requirements say nothing about the certainty that this situation will ever occur. And it says nothing about finding an answer with a 100% chance for success. |
|
Yes they do. The problem says "What plan should they agree on, so that eventually, someone will make a correct assertion?" (Emphasis mine)
Use of the word "will" indicates certainty of a future event. That is: given the strategy, there must be a 100% chance that its requirements for making an correct assertion are met.
Fortunately that holds for the proposed leader solutions. It is possible for no assertion to be made, but such an event has probability zero and hence does not break the problem's requirement.
|
|
IP Logged |
|
|
|
OMG
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #68 on: Aug 5th, 2002, 5:21pm » |
|
When to call the meeting?
There can be no meeting until all prisoners agree to it.
Solutuion #1 (If they are truely Mensa members)
When the last prisoner agrees to a meeting, then they can be freed.
Do not agree to meet until you have been to the room!
If you all are prisoners with me, then I am already dead meat!
Solution #2 (I am the only "leader" / Mensa member)
I will only agree to a meeting after waiting the optimum probability number of days. (I would figure them out, but I am not in prison; I have better things to do, and I leave the details of which to you Math wizards/Mensa members.) Then I would finally agree to a meeting, and ask each prisoner if he has been to the room.
The number should be small by this point, and as leader of this select squad sized outfit (who haven't yet been to the room) I would get a real mathmatician amongst us to solve this smaller problem, then some math genuis can determine that only the odd man should turn the light on. While my squad counts the days, and toggles the light, the rest of you prisoners should just wait to be saved by dividing the problem into a solvable number. The warden will do the "work" for us, as you all wait for me to solve it.
|
|
IP Logged |
|
|
|
Captain Cannibus
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #69 on: Aug 5th, 2002, 11:25pm » |
|
OMG,
how would the prisoners know not to agree to a meeting until having been in the living room if they haven't been to the meeting to talk about their plan yet? the prisoners don't know what any of the other prisoners are doing until the meeting.
|
|
IP Logged |
|
|
|
OMG
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #70 on: Aug 6th, 2002, 5:09am » |
|
Captain Cannibus wrote:
"how would the prisoners know not to agree to a meeting until having been in the living room if they haven't been to the meeting to talk about their plan yet? the prisoners don't know what any of the other prisoners are doing until the meeting."
Answer: It would be common sense for Mensa members.
Solution 1) If all the prisoners are really MENSA material, they would only make the "assertion" for the meeting (in the one room that will fit them all, BTW) if only they themselves been to the living room before; hopefully they can be 100% certain of this. I cannot prove that it is optimal, but it is foolproof. Must I alone must have the willpower to not meet until I have solved the entire riddle?
Solution 2) I am only one prisoner,
and I do not agree to meet until I am ready;
all the rest of you prisoners may do as you please, until I save you. It will take much longer, therefore it is not optimal.
|
|
IP Logged |
|
|
|
dabichon
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #71 on: Aug 6th, 2002, 10:09pm » |
|
This is a very simplistic solution.
Each prisioner will be asigned a number from 0 to 99.
On the x day, if it is the x prisioner who enters the room, he will turn on the light, so the next one knows he has been there.
Now, each prisioner is allowed to turn on the light if its his turn OR if he knows that prisioner has been there,
so if i knew prisioner 20 has been in the room, and the next cycle i happen to enter on day 20, i will turn the light on, even though i am prisioner 54.
Hey! most of these algorithms can be programmed with threads and all mighty powerfull "C".
Anyone?
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #72 on: Aug 7th, 2002, 6:58am » |
|
This is the answer I gave a while ago... while I like its elegance and egalitarianism because there is no leader, it ends up being much slower than the "leader" solutions posed above, especially with some of the suggested enhancements.
This process just takes a long time to get going, although once it does, info spreads very quickly. I did a little checking and the 100 prisoners will get out in about 260 years on average, compared to a matter of a decade or so for other solutions.
|
|
IP Logged |
|
|
|
Paul Hammond
Newbie
Posts: 29
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #73 on: Aug 7th, 2002, 10:42am » |
|
I have a solution which takes about 3900 days ( <11 years) on average, compared to ~10000 days ( >27 years) for the "leader" solution. It's similar, except there is more than one prisoner counting:
1 prisoner is designated Master Counter, 9 prisoners are designated Assistant Counters. Call the rest of the prisoners "drones". The light is initially switched off.
Stage 1 is similar to the "leader" solution. It lasts for 2600 days:
-The first time a drone enters the room and finds the light switched off, he switches the light on. After that, he doesn't touch the switch until the last day of Stage 1.
-If a Counter enters the room and the light is on AND he has not already counted up to 9, he adds one to his count and switches the light off. If he has already counted up to 9, or the light is off, he does nothing.
-On the last day of Stage 1, whoever visits ensures that the light is off before he leaves, unless the visitor is an Assistant Counter who has counted up to 9, in which case he ensures the light is on.
Stage 2 lasts for 2700 days. In this stage, the Master Counter counts the Assistant Counters who managed to count up to 9 in Stage 1. Call these ACs "complete", the other ACs are "incomplete":
-Drones and incomplete Assistant Counters do not touch the switch until the last day of Stage 2.
-If one of the complete Assistant Counters happens to be the person who entered the room on the last day of Stage 1, he does not touch the switch until the last day of Stage 2 (because he will have already left the light on).
-All other complete Assistant Counters switch the light on the first time they find it switched off during Stage 2. After that, they do not touch the switch until the last day of Stage 2.
-If the Master Counter enters the room during Stage 2 and the light is on, he adds one to his count of complete Assistant Counters (a separate tally to the one he used in Stage 1) and switches the light off. In other words, The Master Counter counts the "complete" ACs in a similar way to Stage 1. Once he knows that all Assistant Counters plus himself are complete, he announces to the Warden that all prisoners have visited the room.
-If they get to the last day of Stage 2 and the prisoners still haven't been freed, whoever visits the room that day ensures the light is switched off, all the Counters reset their counts to zero, and the entire process starts from scratch the next day.
You can adjust the number of Counters, the length of Stage 1, and the length of Stage 2, and perhaps get a better result. I just picked the values 10/2600/2700 by trial and error, they seem to work well.
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #74 on: Aug 7th, 2002, 12:37pm » |
|
Good idea Paul. I don't want to have to compute the exact expected time or optimal parameters of that method on paper but it does look like its a fair bit faster than the leader model.
I think you don't actually have to start from scratch if you get to the end of the second round with a failure. Just go back to stage one and everyone remembers what they did before, so that only drones who haven't flicked the switch and incomplete counters participate (it would probably be best to have shorter stage times as you go on). The one tweak you'd need for this that I can see would be that if the light was on at the end day of stage 1, and the person in the room wasn't an unfilled counter, then he would have to remember that fact and account for it by turning on the light 1 time (1 extra time if he was an unused drone) during the next stage 1.
It seems like as n grows you might be able to work this idea into something like an O(n (log n)^2) solution.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Notify of replies
Send Topic
Print