Author |
Topic: 100 prisoners & a light bulb (Read 167248 times) |
|
SMQ
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 2084
|
|
Re: 100 prisoners & a light bulb
« Reply #475 on: Sep 15th, 2005, 6:33pm » |
|
But with 100 prisoners all those 1%'s add up... based on around 8 million trials, I get the average number of days until all prisoners have been chosen as 518.65 --SMQ
|
|
IP Logged |
--SMQ
|
|
|
Guest
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #476 on: Sep 18th, 2005, 11:35am » |
|
Sorry, I haven't read all of the posts (so excuse me if I am repeating someone's arguments). All I can say is the 'leader' solution is absolutely fine, with one exception: The initial state of the light switch is unknown. Suppose the light switch is initially ON. The leader flips it OFF and raises his count by 1, thus being mistaken. If he counts 99 flips, he cannot be sure all of his 99 fellow prisoners entered the room (he can miss a person). He needs to count 199 flips, and prisoners must be allowed to turn the light on for the second time too. With that slight modification, it guarantees 100% success. This is the desired solution, since the problem clearly says that the prisoner who decides to make the statement wants to be 100% sure he is correct. Some can argue it can take infinite time, but the problem's conditions imply that everybody visiting the room can also take inifinite time, given that the warden picks the inmates randomly.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #477 on: Sep 18th, 2005, 11:42am » |
|
Guest, The first person in the room can simply initialise the bulb to an agreed upon initial state.
|
|
IP Logged |
|
|
|
Guest
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #478 on: Sep 18th, 2005, 11:44am » |
|
Sorry for double-posting, but I have noticed that Salem's solution has a major flaw: They decided that the first person who enters the room twice becomes the 'leader'... but how can a prisoner know that he is the first to visit the room twice? AND how do others know that he is the leader (from that moment)? This approach is wrong, since the prisoners cannot exchange information by any means. If they could have, the solution would have been reduced to this nonsense: "When a prisoner enters the room for the first time, he lets the others know, and the 100th prisoner can state with certainty that every prisoner has been in the room." Which is absurd, since the light switch becomes useless and the solution is trivial. The bottom line is: nice try, but they cannot exchange information. I am convinced the 'leader' solution above is the correct one.
|
|
IP Logged |
|
|
|
Guest
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #479 on: Sep 18th, 2005, 11:58am » |
|
mattian, what you mean is that the first day is devoted to initializing the light switch to OFF. Okay, I agree, but that is acceptable only if they can keep track of time. I also heard other variants of this problem, where the warden can summon a prisoner whenever he wants (meaning more than a prisoner per day, and also in non-regular time intervals). And what if they don't know what day it is? They cannot exchange info, they are in solitary confinement... I'd like to think that the 199 count 'leader' solution is more general and is time-independent. (N.b sorry for tripple posting, really really sorry)
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #480 on: Sep 18th, 2005, 12:04pm » |
|
No - what I mean is that the first prisoner (without having to dedicate his entire visit to initialising the bulb) can enter the room, initialise the bulb to the agreed upon state, and then, during the same visit, set the bulb's state according to the particular strategy.
|
« Last Edit: Sep 18th, 2005, 12:06pm by mattian » |
IP Logged |
|
|
|
Guest
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #481 on: Sep 18th, 2005, 12:36pm » |
|
Combine the first and second day into one, or don't, that's not my point. My point is that the 199 count solution is general and time-independent and doesn't require the problem to formulate conditions such as: - The warden must summon one and only one prisoner to his room, every day. All I'm saying this solution is more general. It is even a solution to the same problem, with more strict rules, like: - The warden can summon a prisoner to his room whenever he wants (as many prisoners as he wants per day, and in non-regular time-intervals too). Which implies he can decide not to summon prisoners at a certain day. And those rules only present more difficulties to time-dependant solutions, where prisoners have to count days.
|
|
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 #482 on: Sep 18th, 2005, 7:14pm » |
|
Yes, that is a solution to the more general problem. But as I just pointed out to thrillseeker a few days ago, the discussion in this thread is about the specific problem where the warden chooses exactly one prisoner a day, and the prisoners are able to keep track of days. Just about every solution in this thread (except the oft repeated trivial "leave a mark" and "the meeting was in the room" solutions) was given with these assumptions, and should only be interpreted in the presence of these assumptions. I.e., you have not spotted a major flaw in Salem's solution - you have just noted that it does not apply to situations other than the one Salem offered it for. The more specific problem addressed here is quite interesting in its own right. Because the prisoners are able to track days, they have the capacity to greatly reduce their expected release time over that available even under Salem's shortcut (refered to later in the thread as a "snowball round"). Paul Hammond suggested a means to cut Salem's time by nearly two-thirds. To read up on the ingenious solutions offered by Paul and by his successors, you can read through the thread, or else, read the summary I gave starting here. Note some of the numbers I gave were out-of-date even when I gave them, and there were some improvements since that summary, which you will have to find by reading onward. Mattian in particular has done much to improve our understanding of several of the schemes that I never incorporated. (Also, I fully admit that the summary is not easy reading - I had to do a lot of both condensing, and fleshing out concepts not fully explained when originally posted.) The situation wherein the prisoners are not picked once a day (or are not able to track days), and wherein they do not know the state of the bulb is also valid, but should not be mixed with this discussion. If you would like to explore it more, I strongly urge that you start a new thread. It has been partially addressed in the "100 prisoners and 2 light bulbs" thread, but as the name indicates, that thread also introduces a second bulb to the situation.
|
|
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 #483 on: Sep 18th, 2005, 7:28pm » |
|
on Sep 18th, 2005, 7:14pm, Icarus wrote:Mattian in particular has done much to improve our understanding of several of the schemes that I never incorporated. |
| Maybe I'll finish what I started with that one day when I'm not working 16-7.
|
|
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 #484 on: Sep 18th, 2005, 7:46pm » |
|
You will notice that I never updated my summary with your new values, like I said I would, either. So I am not about to scold you for not finishing your review!
|
|
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
|
|
|
Ed W
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #485 on: Sep 22nd, 2005, 8:57pm » |
|
ok people if this is crack pot please let me know, but if I was a prisoner in this situation this is what i would do. Forget the light switch that helps you none. You have to devise a plan that you can measure. so i propose this. First, if you can leave things in the room, just have a prisoner leave a shoe, shirt, or something accessable to all prisoners, once you have 100 shoes, shirts, or something else you would know all people have been in it at least once. Obviously if you already left a shoe dont leave another one. If this option is not available I would turn my attention to the light bulb. I would instruct the other inmates to use the light bulb as a measuring tool. Tell the inmates to start at a wall (North, South, East, or West), then unscrew the light bulb and place it flat on the floor against the wall. Then when the next person comes in have them move the bulb one full light bulb in front of the previous spot. Once you get far enough you should be able to measure how many 'bulbs' away the bulb is from the starting wall, once your 100 bulbs away from the starting point you've got it. Ok people, tell me what you think, I dont have a fancy math equation to tell how many days it will take but it seems that these two ideas would work. this is what i would do so its the best i got. e
|
|
IP Logged |
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: 100 prisoners & a light bulb
« Reply #486 on: Sep 22nd, 2005, 9:05pm » |
|
on Sep 22nd, 2005, 8:57pm, Ed W wrote:ok people if this is crack pot please let me know, <snip> e |
| Hi Ed, This answer is not "crack pot" as you call it, but it was proposed numerous times before. If you can find the time to read through it (rather long) thread, you will find many of this type of suggestions, and the general agreement among the forum regulars that it is more interesting to solve it "within the box" -- with the fancy math.
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
Edward Smith
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #487 on: Oct 16th, 2005, 5:44am » |
|
I don't think anyone has proposed a solution in n time. The puzzle page defines 'optimum' as least amount of days, not most number of prisoners. If each prisoner just claims that he is the 100'th, then on the 100th trial, one prisoner will go free. Voila, no? Edward
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7527
|
|
Re: 100 prisoners & a light bulb
« Reply #488 on: Oct 16th, 2005, 9:38am » |
|
Not really. The problem states: "The prisoner has the option of asserting the claim that all 100 prisoners have been to the living room. If this assertion is false (that is, some prisoners still haven't been to the living room), all 100 prisoners will be shot for their stupidity." There is only one chance, then the game is over. I understand this as meaning the claim must be made only with 100% certainty to be true. This being said, probabilistic solutions have been given in this thread.
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: 100 prisoners & a light bulb
« Reply #489 on: May 8th, 2006, 11:52am » |
|
The light bulb is a red herring. A perfectly acceptable solution (no secret signaling, no telepathy, no cheating, ...) exists that does not use the light bulb and that: 1) allows the prisoners to make their claim immediately after the 100th prisoner has visited the living room 2) reaches a degree of certainty that is as close to 100% one desires (provided one is willing to increase the amount of preparation). Will post the solution later... (no kiddin' don't want to spoil another - related - thread)
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
ctsio
Newbie
Posts: 1
|
|
Re: 100 prisoners & a light bulb
« Reply #490 on: May 28th, 2006, 3:13am » |
|
ok here is the best solution which I have come up with so far. On the first day, the first prisoner enters the room and turns on the light because it is his first time in the room. For every day which follows, if a prisoner enters the room and it is their first time in the room then they leave the light on. After a period of time eventually one prisoner will enter the cell for their second time. Call this person the LEADER. On the day that this happens the LEADER will know how many people have been in so far. E.g if the LEADER is found on day 50 then 49 people have been in the room for their first time. (I.e we don't include the LEADER twice ) From that day forth, if a person enters the room and has already been in there before they do nothing. If a person enters the room and the light is off and it is their first time in the room they turn it on. This signals to the LEADER that a new person has been in the room. If a person enters for the first time and the light is already on they do nothing because that means someone else is already signalling to the LEADER that they have been in the room for the first time. Basically the LEADER, every time they enter the cell, if the light is on then they add 1 to the tally and turn the light off. If the light is already off they do nothing. When the LEADER has counted to 100 then they are free.
|
|
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 #491 on: May 28th, 2006, 7:14am » |
|
So, what happens when prisoners A,B,C arrive in the sequence A,C,A,B,C Wouldn't C as well as A think they're leader? You could amend it by never switching on the light for the first 100 days (except by the first prisoner), this way there can be only one leader. (As there is guaranteed to be a double, or the last prisoner knows all have been there)
|
« Last Edit: May 28th, 2006, 7:23am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
alien
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #492 on: May 29th, 2006, 1:44pm » |
|
Lend me your ears because I don't have the answer.. I was thinking about this riddle past three days, and come up with nothing. Well, almost nothing. I remember a riddle about hats, where a group of people buried up to their necks had to guess what color their hat is, otherwise natives would cut their head off. A big part of the answer was odd and even numbers of hats. Being optimistic, maybe that could be applied to this riddle also. Alas prisoners are in soundproof cells, so the only form of communication is the bulb. But I still have a feeling that a bit more information could be passed without choosing the leader, if we consider odd and even, say, days. So prisoners that were already in the living room on odd days press the switch, and on even days don't touch it. And, say, those who are first time in the room press vice versa. Now this plan I just mentioned, doesn't mean anything, or at least I think it doesn't, but it is an example of how one could dare to play with this riddle in search of optimal plan. The idea with odd and even days pretty much revolves around a single day, whether it is odd or even, or a particular day. So on this day, let's say 1000th day, if light is on, that should mean that all 100 prisoners have been to the room. Otherwise they wait another 1000 days to see whether 2000th day is their lucky day. I thought about this, and pretty much quit. Oh well..
|
« Last Edit: May 29th, 2006, 5:15pm by alien » |
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 #493 on: May 29th, 2006, 5:01pm » |
|
A summary of the methods suggest at the time is available on page 16 starting here. I admit it is not easy reading, but it still beats the heck out of reading through the first 15 pages. It also puts most of the "in-the-box" solutions into a common idiom, which makes it easier to interpret new ones. Your solution seems to be a variant of the single solution that I did not put in that idiom. Of course, part of why I didn't bother to translate that one was that it was extremely long running.
|
|
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
|
|
|
SMQ
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 2084
|
|
Re: 100 prisoners & a light bulb
« Reply #494 on: May 30th, 2006, 8:34am » |
|
Also, the current leader (with an average runtime of 3460 days) is detailed in this post by Leonid Broukhis which refines this post of his which builds on this post of mine which describes a refinement of this post by gypo which is the last method described in Iacrus' summary. --SMQ
|
|
IP Logged |
--SMQ
|
|
|
Sjoerd_de_Vries
Newbie
Posts: 1
|
|
Re: 100 prisoners & a light bulb
« Reply #495 on: Jun 29th, 2006, 2:38am » |
|
Hello guys, I would like to present not a solution but two frameworks that provide a mechanism for the guaranteed optimal solution within those frameworks. I believe that all current solutions without pre-defined roles fit into those frameworks, except the idea of non-equal sized tokens. The first framework is about token transfer. A prisoner initially has one token. When a prisoner enters the room at day t, and the light is on, he receives an amount of tokens equal to the pre-defined quantity from the previous day, x(t-1). Then, if his current total of tokens is larger than the pre-defined quantity of today, x(t), he turns the light on and subtracts x(t) tokens from his inventory. However, he will not do this if his inventory contains more tokens than y(t). Therefore, a solution can be generalized to a set of x and y values for each day. It has been suggested before on this forum as a radically different solution, however most solutions are just a special case of this general scheme. A snowball stage can be easily coded into this scheme by incrementing x(t) by 1 each day while keeping y(t) to infinite, and in a later stage x(t) can be set to v and y(t) to v+1, where v is the amount of tokens that an assistant leader has to collect. The second framework is about the distributions of tokens. You can sort the number of token each prisoner has from high to low. The initial distrbution is 1, 1, 1, [ 1 ]97 (so 100 x 1), while the terminal distribution is 100, 0, 0, 0, [ 0 ]96 (1x 100 and 99 x 0). There are about 190 million of these distributions, and at any step the current state can be described as a 190 million x 2 matrix. The first element codes for the probability of that distribution to be present, while the second element codes for the probability that the light is on if that distribution occurs. Now, you can carefully keep track of this matrix and assess the effect of every operation. In addition, you could devise a scoring scheme for each distribution, being dependent on the inequality (the more unequal the distribution, the better), the probability of the light being on, and the amount of tokens that the light encodes (which is the same for every distribution). Once you have done this, you 1. don't need to simulate anymore; 2. can incrementally optimize your solution for every single day, independent of what happens on other days. So the only thing that needs to filled in is the scoring scheme, which would probably involve some kind of entropy; an information theorist (which I am not) should be able to provide it. My apologies for this very lengthy post.
|
« Last Edit: Jun 29th, 2006, 2:45am by Sjoerd_de_Vries » |
IP Logged |
|
|
|
alien
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #496 on: Sep 5th, 2006, 11:19am » |
|
Fellow riddlers. I have but an optimal solution, which works in one day. Little did we know, that one of the prisoners is Bruce Lee. So when they meat in the courtyard, to discuss the optimal solution, he applies his martial arts, and snaps all their necks. And since he is the only prisoner left, when the warden takes him to the central room with one bulb, he declares that all prisoners have been to the room, and takes the bulb with him as a souvenir.
|
« Last Edit: Sep 5th, 2006, 11:23am by alien » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 2084
|
|
Re: 100 prisoners & a light bulb
« Reply #497 on: Sep 5th, 2006, 11:43am » |
|
You know, of all of the "thinking out-of-the-box" solutions, I believe this is the first time selecting a leader by preemptively killing the other 99 prisoners has been suggested. --SMQ
|
|
IP Logged |
--SMQ
|
|
|
Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 100 prisoners & a light bulb
« Reply #498 on: Sep 8th, 2006, 6:17pm » |
|
Alas for Bruce, the warden demands that someone announce when all 100 prisoners have visited the room. And worse, the warden does not bring dead prisoners to the room, so all 100 will never visit. And worse yet, the prison has hired real guards, who know how to shoot their guns and are quite willing to do so, not hollywood guards who either abandon their guns in a show of machoistic idiocy, or stand around like imbeciles until he finishes off the closer guards. This means Bruce has no chance for escape.
|
|
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
|
|
|
flamingdragon
Uberpuzzler
Gender:
Posts: 671
|
|
Re: 100 prisoners & a light bulb
« Reply #499 on: Nov 15th, 2006, 4:34pm » |
|
Has an answer been found to this yet and what is it if there has been one? I don't want to read through 20 pages looking for the answer.
|
|
IP Logged |
"The fool doth think he is wise, yet the wise man knoweth himself to be a fool"
"He who commands the past, commands the future. He who commands the future, commands the past."
|
|
|
|