Author |
Topic: 100 prisoners & a light bulb (Read 166669 times) |
|
Nasta
Newbie
 
Gender: 
Posts: 9
|
 |
Re: 100 prisoners & a light bulb
« Reply #450 on: Sep 6th, 2005, 11:07am » |
|
i don't think that anyone argues that just prisoner one and two will be lead there infinitely often, there's a probability of that happen, but like I said it is close to the probability of a fair coin going heads infinitely many times. but on the other hand, the problem does not guarantee that everyone goes just once in an unknown order, otherwise it would be just plain trivial. the one problem i see is that the system of the leader takes too long, because he must be lead in the center at least 99 times, so that he can be sure that everyone else has been there also. but as the chance of his being there is equal to anyone else being there also, it may take as much as 99 times for everyone to visit the center until it is done. it is pretty sure in this case that even if everyone goes in the center for the first 100 days, there is no way that he learns that. or is there?
|
|
 IP Logged |
|
|
|
mattian
Senior Riddler
 
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #451 on: Sep 6th, 2005, 11:12am » |
|
There is a possibility he might know after 100 days...
With a snowball round that by luck lasts 100 days, the leader (the first guy in) will walk in on day 101 and see the light still off - indicating that no one has been in the room twice. On day 101, he can declare their freedom.
|
|
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 #452 on: Sep 6th, 2005, 5:58pm » |
|
There is no disagreement from anyone here who understands the solutions that it is possible for the prisoners to know with complete certainty that everyone has visited.
I just don't believe that JohnP was claiming otherwise. My understanding of his comment was that he was refering to what Nasta calls "not exact with respect to time": that there is no guarantee that everyone will visit in any finite amount of time.
Yes, his comments can be interpreted in other ways (as can all of ours). But I choose to give JohnP the benefit of the doubt and interpret them in the fashion in which they are true, instead of interpreting them to be false, and telling him that he is wrong, even though a true interpretation exists.
This thread, and more generally this entire forum, is filled with poorly explained and incomplete posts that require considerable interpretation to make any sense of them. JohnP's post is clarity itself as compared to some others posted by well-respected members. Unless the poster is still around to defend or explain their post, I believe it is wise to assume a true interpretation for the post when one is possible.
|
| « Last Edit: Sep 6th, 2005, 6:04pm 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
|
|
|
thrillseeker
Newbie
Posts: 22
|
|
Re: 100 prisoners & a light bulb
« Reply #453 on: Sep 7th, 2005, 12:23am » |
|
try this solution...
A leader is choosen. His name is Jason.
Only Jason may turn the light on and he does so the first time that he enters the room and counts (1) for himself. Even if the light is on when he enters, he leaves it on and counts (1) for himself.
All other prisoners must turn the light off, but, they are allowed to do this only once.
Jason counts every time that he enters the room and turns the light on. He knows that a prisoner who has not had the opportunity to turn the light off, has turned the light off and is now able to be accounted for. (whether the prisoner has never been sent to the room or if the prisoner has been sent to the room and was not able to turn the light off because a prisoner who was sent in before him turned it off.)
Jason counts the number of times that he has turned the light on. When he reaches 100 including the first count for himself, he knows that all 100 prisoners have been in the room.
This count includes prisoners who went into the room before Jasons first visit because the prisoners are choosen one per day and equally. The riddle does not say that the warden will stop sending prisoners into the room after he has sent the 100th prisoner in.
Any problems with that?  
|
| « Last Edit: Sep 7th, 2005, 11:02pm by thrillseeker » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 100 prisoners & a light bulb
« Reply #454 on: Sep 7th, 2005, 1:55am » |
|
on Sep 7th, 2005, 12:23am, thrillseeker wrote:| Any problems with that? |
|
A minor one.
Not all prisoners can turn the light off on their first visit, because a previous prisoner may have already turned it off. So they should turn the light off if it is on and they've never switched it off before.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Nasta
Newbie
Gender:
Posts: 9
|
|
Re: 100 prisoners & a light bulb
« Reply #455 on: Sep 7th, 2005, 4:48am » |
|
let's look at the things backwards - to find the optimal time, i would guess that would be the time that all the prisoners have visited the central room. that process could take from 100 days to infinity, but as someone else has posted already a reasonable time would be 5 years. since the one leader approach is one of perfect information of one inmate, and it's average time is 27 years i would guess that the optimal time ranges from 5 to 27, of course the other methods lowered the time needed for a "perfect information" system to 9-10 years. so the question is - is there a possibility for a still better system to exist that gets closer to 5 years, or there exists some other (higher than 5 years)lower barrier that whatever system is chosen it could not get below it?
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
   
Gender:
Posts: 2872
|
|
Re: 100 prisoners & a light bulb
« Reply #456 on: Sep 7th, 2005, 5:09am » |
|
on Sep 7th, 2005, 12:23am, thrillseeker wrote:
Any problems with that? |
|
A fairly major one - on day 10, when Jason enters the room for the first time, he can't tell whether he's the second prisoner to visit, the 10th, or anything in between.
If he assumes he's the 10th, then there's a possibility his count will hit 100 early. If he doesn't, he may never hit 100.
If yu know the warden isn't going to repeat prisoners until he has to, then you don't need the bulb at all - the prisoner who enters on day 100 can claim freedom without any other data.
|
|
IP Logged |
|
|
|
thrillseeker
Newbie
Posts: 22
|
|
Re: 100 prisoners & a light bulb
« Reply #457 on: Sep 7th, 2005, 10:29pm » |
|
rmsgrey,
It does not matter that Jason does not know whether he is the 1st, 10th, 36th or whatever. The warden will continue to send prisoners into the room forever. So all Jason has to do is count the number or times that he turns the light on.
Actually, he need only count the number of times that he enters the room!! When he reaches 2, all prisoners have entered the room because he is sent in once every 100 days after his first trip in!! All prisoners are sent in one per day and equally!!
(I knew this riddle was flawed)
I suppose that since the riddle does'nt say that the warden will stop sending prisoners in after the 100th has entered, he will continue to send prisoners in forever, one a day and equally.
There is no way that any prisoner can know that the 100th day has arrived because the riddle does not state when the process will begin. If the process begins on the same day that they gather in the courtyard, any prisoner who is not sent into the room on that day will not know that that was the day that the whole thing began. Only the prisoners who were sent into the room on that day will know that is the starting day, and there is no certainty that one of those prisoners will enter on the 100th day and be able to make the claim.
On the other hand......the riddle does say that the prisoners will be sent in ONE PER DAY. So....on the day following their gathering in the courtyard, all of the prisoners could consider that day to be the first day even if its the 2nd. They would just count 100 days and whoever enters on that day makes the claim!
One problem with that though.....the cells have no windows and are soundproof. So there is now way for the prisoners to count days. They do not know when the sun rises or sets.
|
| « Last Edit: Sep 7th, 2005, 11:19pm by thrillseeker » |
IP Logged |
|
|
|
thrillseeker
Newbie
Posts: 22
|
|
Re: 100 prisoners & a light bulb
« Reply #458 on: Sep 7th, 2005, 10:39pm » |
|
Towr,
That is a good point. I should have stated my solution like this...
All other prisoners must turn the light off, but, they are allowed to do this only once.
|
| « Last Edit: Sep 7th, 2005, 10:49pm by thrillseeker » |
IP Logged |
|
|
|
Nasta
Newbie
Gender:
Posts: 9
|
|
Re: 100 prisoners & a light bulb
« Reply #459 on: Sep 8th, 2005, 1:14am » |
|
i don't think the problem is flawed - your interpretation seems to be though. the prisoners are selected equally at random, but that doesn't guarantee that once someone is chosen, he can't be chosen again! on the contrary - the probability of anyone being chosen any particular day is 1/100, this experiment is one of geometric distribution and it does not have memory; one prisoner may be selected on day one, on day two, after that on day 56, and another may not be selected until day 200...
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: 100 prisoners & a light bulb
« Reply #460 on: Sep 8th, 2005, 4:49am » |
|
on Sep 7th, 2005, 10:29pm, thrillseeker wrote:| There is no way that any prisoner can know that the 100th day has arrived because the riddle does not state when the process will begin. If the process begins on the same day that they gather in the courtyard, any prisoner who is not sent into the room on that day will not know that that was the day that the whole thing began. Only the prisoners who were sent into the room on that day will know that is the starting day, and there is no certainty that one of those prisoners will enter on the 100th day and be able to make the claim. |
|
OK, if you can't tell which day it is for some reason, then a lot of the more serious solutions proposed in this thread fall apart. Even so, if you can rely on the warden not repeating prisoners until he has to, then not knowing which day it is only delays release by one day. On day 101, a prisoner re-enters the room for the first time, and everyone is released.
If the warden can repeat prisoners any time he feels like it, then the ony way Jason can know how many prisoners have visited before him is by knowing that it's day 1, day 2, day 3 with agreed signals, or a specific later day under specific circumstances and with agreed signals. Other prisoners then have no way of knowing whether they're before or after Jason's first visit (apart from the guy on day 1)
|
|
IP Logged |
|
|
|
thrillseeker
Newbie
Posts: 22
|
|
Re: 100 prisoners & a light bulb
« Reply #461 on: Sep 8th, 2005, 9:29pm » |
|
on Sep 8th, 2005, 1:14am, Nasta wrote:| i don't think the problem is flawed - your interpretation seems to be though. the prisoners are selected equally at random, but that doesn't guarantee that once someone is chosen, he can't be chosen again! on the contrary - the probability of anyone being chosen any particular day is 1/100, this experiment is one of geometric distribution and it does not have memory; one prisoner may be selected on day one, on day two, after that on day 56, and another may not be selected until day 200... |
|
To me, equally means that the warden will pick one prisoner per day and not the same prisoner twice before all 100 have visited the room.
Is that not the only way to be equal?
I also assume that after the warden has sent in all 100 prisoners, he must use the same order that he used previously for all 100. If he does not, then a prisoner could be sent to the room twice before a prisoner who entered the room before him. If prisoner #2 is sent into the room twice before prisoner #1 is, then it is not equal.
To me, random means that there is no particular order to the way that he picks the prisoners. But, he must repeat this random order after all 100 have entered the room in order for his choices to remain equal.
You stated...."One prisoner may be selected on day one, on day two, after that on day 56, and another may not be selected until day 200..."
If that is true then there is no equality because one prisoner is sent to the room 3 timees before another is sent in once.
There is a problem with my solution however. The prisoners do not know that the warden is choosing them one per day, equally and at random. So Jason would not have any way of knowing that all 100 of the prisoners have been to the room after his first visit.
|
|
IP Logged |
|
|
|
thrillseeker
Newbie
Posts: 22
|
|
Re: 100 prisoners & a light bulb
« Reply #462 on: Sep 8th, 2005, 9:45pm » |
|
on Sep 8th, 2005, 4:49am, rmsgrey wrote:
OK, if you can't tell which day it is for some reason, then a lot of the more serious solutions proposed in this thread fall apart. Even so, if you can rely on the warden not repeating prisoners until he has to, then not knowing which day it is only delays release by one day. On day 101, a prisoner re-enters the room for the first time, and everyone is released.
If the warden can repeat prisoners any time he feels like it, then the ony way Jason can know how many prisoners have visited before him is by knowing that it's day 1, day 2, day 3 with agreed signals, or a specific later day under specific circumstances and with agreed signals. Other prisoners then have no way of knowing whether they're before or after Jason's first visit (apart from the guy on day 1) |
|
There is no way for the prisoner sent to the room on the 101st day to know that it is the 101st day. The prisoners do not know that the warden is sending them in one per day, equally at random. Also, the cells have no windows and are soundproof. The prisoners can not count days. They do not know when the sun sets or rises.
A prisoner is sent to the room and then back to his cell. He cannot count the days while he is in his cell. When he is sent in for the second time, 3 weeks, a month, 45 days could have passed and he would have no knowledge of this.
I have a new solution and I will propose it tomorrow. I need to think about it for a day to find a flaw.
|
|
IP Logged |
|
|
|
Nasta
Newbie
Gender:
Posts: 9
|
|
Re: 100 prisoners & a light bulb
« Reply #463 on: Sep 9th, 2005, 1:26am » |
|
equally at random means that every day every prisoner has an equal chance of being selected - 1/100 no matter if he has already been selected once or twice or 100 times...it's not a pseudo random like the function of a winamp...
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: 100 prisoners & a light bulb
« Reply #464 on: Sep 9th, 2005, 5:56am » |
|
on Sep 8th, 2005, 9:45pm, thrillseeker wrote:
There is no way for the prisoner sent to the room on the 101st day to know that it is the 101st day. The prisoners do not know that the warden is sending them in one per day, equally at random. Also, the cells have no windows and are soundproof. The prisoners can not count days. They do not know when the sun sets or rises.
A prisoner is sent to the room and then back to his cell. He cannot count the days while he is in his cell. When he is sent in for the second time, 3 weeks, a month, 45 days could have passed and he would have no knowledge of this. |
|
Do the prisoners know how often they get fed?
Yes, it's possible to come up with a means of incarceration that totally deprives a prisoner of any way of measuring the passage of time, but, most of the time, you only bother as part of a torture and interrogation regime rather than for simple containment.
If you can't tell what time it is, then the optimal solution is much easier to determine - as I said previously, most of the "heavy lifting" on this thread revolves around solutions where the day number is significant.
|
|
IP Logged |
|
|
|
thrillseeker
Newbie
Posts: 22
|
|
Re: 100 prisoners & a light bulb
« Reply #465 on: Sep 9th, 2005, 11:52pm » |
|
on Sep 9th, 2005, 5:56am, rmsgrey wrote:
Do the prisoners know how often they get fed?
Yes, it's possible to come up with a means of incarceration that totally deprives a prisoner of any way of measuring the passage of time, but, most of the time, you only bother as part of a torture and interrogation regime rather than for simple containment.
If you can't tell what time it is, then the optimal solution is much easier to determine - as I said previously, most of the "heavy lifting" on this thread revolves around solutions where the day number is significant. |
|
I do not think there is any need for the prisoners to know what # day it is. I admit that I had a misunderstanding of how the warden chooses prisoners based on a one per day, equally at random basis. I believe the solution I provided a couple days ago works fine. With that solution, all prisoners sent into the room before Jasons first visit and after Jasons first visit are accounted for.
The initial state of the bulb is off. Any prisoner sent into the room before Jasons first visit will find the light off. Prisoners are not allowed to turn the light on, so they leave it alone. Those prisoners will have to wait on a future day to enter the room and see if the light is on. If they find it on, they turn it off, and the light is left off untill Jason enters the room and turns it on. Jason counts the number of times he turns the light on. When he reaches 99, he adds one for himself and may then make the claim. There is no evidence that the warden will ever stop sending prisoners into the room, so its safe to say that all prisoners will make several trips into the room, and eventually they all will have a shot at turning the light off and being accounted for. I do not have the math skills to calculate how long that could take. 
|
| « Last Edit: Sep 10th, 2005, 12:00am by thrillseeker » |
IP Logged |
|
|
|
Nasta
Newbie
Gender:
Posts: 9
|
|
Re: 100 prisoners & a light bulb
« Reply #466 on: Sep 10th, 2005, 3:59am » |
|
that is the one leader approach - the avarage time is 27 years...the most optimal that are discussed are a lot better - 9-10 years, read the whole thread to see them...
|
|
IP Logged |
|
|
|
thrillseeker
Newbie
Posts: 22
|
|
Re: 100 prisoners & a light bulb
« Reply #467 on: Sep 10th, 2005, 8:45pm » |
|
on Sep 10th, 2005, 3:59am, Nasta wrote:| that is the one leader approach - the avarage time is 27 years...the most optimal that are discussed are a lot better - 9-10 years, read the whole thread to see them... |
|
Last night I found a fault with this solution. It does not say anywhere in the riddle that the prisoners are disclosed the initial state of the bulb. The riddle only tells you that the prisoners are allowed to toggle the bulb and make the claim that all have visited.
Can the prisoners afford to take a risk like that? Assuming that the initial state of the bulb is off? No, they cant. When Jason enters the room for the first time he will have no idea if anyone was sent in before him. Any prisoner sent in before Jason will not know if Jason has already visited.
The plan they have decided on assumes that the bulb is initally off. With that in mind, lets suppose that the bulbs initial state is on! (As far as the prisoners know, it very well could be.) Any prisoner that enters the room will assume that Jason has already been in because the light is on and only Jason is allowed to turn the light on. That prisoner will turn the light off and assume that he will be accounted for. Then, when Jason enters for the first time, he will assume that the original state of the bulb was off and nobody has toggled it yet. The prisoner who toggeled it before Jason entered will not be accounted for because he has already toggled it once and cannot toggle it again.
I consider this is a serious threat to all of the solutions that assume that the prisoners know the original state of the bulb. 
|
| « Last Edit: Sep 10th, 2005, 8:48pm by thrillseeker » |
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #468 on: Sep 10th, 2005, 8:56pm » |
|
The solutions in this thread have tackled that issue. It's quite simple as long as you know which day the selections will start. On the first day, the first prisoner entering the room, simply initialises the bulb to the agreed upon state - and then sets it according to the agreed upon strategy.
If on the other hand they do not know which day the selections are to start - and I don't believe this scenario has been covered in this thread - it can be a bit tricky. Unless, for example they know that selections will begin within some maximum period of time, in which case their escape time will be offset by that amount.
|
|
IP Logged |
|
|
|
thrillseeker
Newbie
Posts: 22
|
|
Re: 100 prisoners & a light bulb
« Reply #469 on: Sep 10th, 2005, 9:29pm » |
|
on Sep 10th, 2005, 8:56pm, mattian wrote:The solutions in this thread have tackled that issue. It's quite simple as long as you know which day the selections will start. On the first day, the first prisoner entering the room, simply initialises the bulb to the agreed upon state - and then sets it according to the agreed upon strategy.
If on the other hand they do not know which day the selections are to start - and I don't believe this scenario has been covered in this thread - it can be a bit tricky. Unless, for example they know that selections will begin within some maximum period of time, in which case their escape time will be offset by that amount. |
|
How does the first prisoner to enter the room know that he is the first prisoner to enter the room? He cant. How can any prisoner know when the first day is? They cant. The first day could be the same day that they are sent to the courtyard to discuss a plan. It could also be the following day. [b]"Before this whole procedure begins, the prisoners are allowed to get together in the courtyard to discuss a plan."[/b]
They do not know when the selections will start, the do not know that selections will begin within some maximum period of time.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #470 on: Sep 10th, 2005, 9:42pm » |
|
Well they MAY not know - it isn't specified in the problem statement. Or maybe it is - I haven't read it in a while.
|
| « Last Edit: Sep 10th, 2005, 9:44pm 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 #471 on: Sep 11th, 2005, 12:46pm » |
|
on Sep 10th, 2005, 9:29pm, thrillseeker wrote:| How does the first prisoner to enter the room know that he is the first prisoner to enter the room? He cant. How can any prisoner know when the first day is? They cant. The first day could be the same day that they are sent to the courtyard to discuss a plan. It could also be the following day. |
|
Though the problem does not explicitly say that the prisoners know when the process starts, and how much time is passing, it also says nothing to suggest otherwise, and the general assumption in this thread is that both are known to the prisoners.
If you would like to start a discussion on the situation where one or both is unknown to the prisoners, I suggest starting a new thread for it, rather than diluting this thread with differing cases. (Including discussions of multiple scenarios in a single thread invariably causes confusion as some readers will mistake which scenario applies to each post. I learned this the hard way when I innocently introduced a second interpretation into the "Greedy Pirates" thread.)
The problem with unknown starting times and time passage is discussed in the 2-light-bulb variant, but of course there the prisoners are given an additional resource to help deal with it.
|
|
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
|
|
|
Nasta
Newbie
Gender:
Posts: 9
|
|
Re: 100 prisoners & a light bulb
« Reply #472 on: Sep 15th, 2005, 7:45am » |
|
any progess with the optimal numbers of counters, number and length of cycles?
or ways to prove that optimality exists?
|
|
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 #473 on: Sep 15th, 2005, 3:18pm » |
|
on Sep 15th, 2005, 7:45am, Nasta wrote:| any progess with ... ways to prove that optimality exists? |
|
It is highly likely that an optimal solution exists. And if we take the average time for solutions to be rounded to the nearest whole day, then existance is guaranteed.
Proving that particular solution was optimal is another matter. I'm not sure how you could do that.
The best I can see is to find lower bounds for the average solution time that apply to all solution methods. If you can find a method whose average time is also a proven lower bound, then obviously that solution is optimal.
So far, the highest lower bound I know of is the expected time before all 100 prisoners have visited the room (a value I do not know yet). They cannot learn that they have all visited before they have all visited. But this value is probably much smaller than the optimal average release time.
|
|
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 #474 on: Sep 15th, 2005, 3:42pm » |
|
The odds that any given prisoner will not have been selected at least once after 450 days are about 1%.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Notify of replies
Send Topic
Print