Author |
Topic: 100 prisoners & a light bulb (Read 167700 times) |
|
oddesyus (Michael)
Guest
|
|
Addition to Oddesyus's magnificant answer
« Reply #226 on: Apr 1st, 2004, 7:33pm » |
|
This answer is acceptable because it is dependant on the state (of cleanliness) of the bulb. A simpler, more cynical answer: Select the biggest prisoner have him remove the lightbulb, break it to the point of sharpness and attack the guard in the dark. Steal the guards keyes and free all the prisoners
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: 100 prisoners & a light bulb
« Reply #227 on: Apr 2nd, 2004, 5:27am » |
|
A) How do you get 99 distinct spots on a lightbulb in the first place? B) On Day 51, the prisoner enters to find a bulb with 99 distinct spots of blood... C) On Day 51, the prisoner finds the bulb covered in insects...
|
|
IP Logged |
|
|
|
Oddesyus (michael)
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #228 on: Apr 2nd, 2004, 10:57am » |
|
first of all, a drop of blood is very small. A prisoner can easily apply it with some hairs or a fingernail clipping Where do you get 51 days? It takes more than 51 days for 99 visits to occur The bulb will not be covored in insects. If all the rooms are perfectly sealed, there will be no way any bugs can get in. Also the prisoner can bake the blood (so insects cnnot get at it) by turning on the light for a couple of seconds
|
|
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 #229 on: Apr 2nd, 2004, 3:23pm » |
|
There have been many far less painful means of leaving markers in the room suggested. How does this add anything that they don't have? The comment in the header does not proclaim that marker solutions are invalid, just that they have already been discussed. So unless you have something truly original to offer (another means of leaving markers is not original), what is the point of repeating ideas someone else has already said? What those tracking this thread are interested in is an improvement on the algorithms for handling the problem "in the box".
|
|
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
|
|
|
Oddessyus (Michael)
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #230 on: Apr 3rd, 2004, 6:23pm » |
|
Well I guess that this riddle has already been slolved many times and nobody should bother writing in this thread any more and we should close the discussion THIS IS THE END OF THE THREAD DO NOT ADD MORE BECAUSE YOU WILL BE SUPERFLUOUS FOR ALL ETERNTIRY (or until you find something constructive to do)
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: 100 prisoners & a light bulb
« Reply #231 on: Apr 4th, 2004, 9:26am » |
|
Actually, I'd be very surprised if the current "best" solution turns out to actually be optimal. Any improvements are still welcome, and an optimality proof would be met with cries of rapture.
|
|
IP Logged |
|
|
|
Olly
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #232 on: Apr 19th, 2004, 7:11am » |
|
Not read whole thread, so may well have been mentioned already.... But, as they are allowed to meet each evening to formulate a plan, surely they just have to ask each other "Has anyone NOT been in the room yet?" Once they establish that, then an assertion can be made. Nothing to do with the light...
|
|
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 #233 on: Apr 19th, 2004, 7:28am » |
|
on Apr 19th, 2004, 7:11am, Olly wrote:But, as they are allowed to meet each evening to formulate a plan, surely they just have to ask each other "Has anyone NOT been in the room yet?" |
| They are allowed to meet up once, and that's also before the game begins..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: 100 prisoners & a light bulb
« Reply #234 on: Apr 19th, 2004, 7:33am » |
|
on Apr 19th, 2004, 7:11am, Olly wrote:But, as they are allowed to meet each evening to formulate a plan, ... |
| They're only allowed to meet once before the whole procedure begins.
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
alien
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #235 on: Apr 24th, 2004, 10:23am » |
|
if one of the prisoners was, say, 50 times consecutively in the central living room, no switching on-off of the bulb could transfere this fact to the next prisoner.
|
|
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 #236 on: Apr 24th, 2004, 1:59pm » |
|
He doesn't need to communicate that he was there 50 times. Only that he was there at least once. Several workable approaches have been suggested in this thread. To start you off, I wll give the simplest (and also least efficient, with - if I recall correctly - a 270 year expected time before release). This is called here the "Leader Solution": One guy is elected to be the leader. Only he can turn the light on. Everyone else turns the light off only the first time they see it on. Otherwise they leave it alone. When the leader has entered 99 times and found the light off (other than the first day, if he was the chosen prisoner), he announces that everyone has visited the room and they are all released: an amazing collection of 300 year old men kept alive by their own dogged determination! If you read through the thread, you will find several really clever improvements on this, including one that gives an expected time until release of 11 years.
|
|
IP Logged |
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? " - Anonymous
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: 100 prisoners & a light bulb
« Reply #237 on: Apr 24th, 2004, 9:17pm » |
|
Checking the thread, a figure of ~10,000 days (~27 years) is mentioned (without proof) for the simple leader method. I haven't bothered to check the entire thread properly, but a quick "Find" failed to turn up "270" being given as a number of years for any solution. The current best solution claims an expected duration of around 9.5 years (based on simulations) has some scope for fine tuning (though probably still giving expectation around 9.5 years)
|
|
IP Logged |
|
|
|
alien
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #238 on: Apr 27th, 2004, 3:10am » |
|
I have a small improvement for the "Leader Solution" which speeds up twice the counting of the leader. The leader is elected not in the courtyard but after the whole procedure begins. Let me explain: the first two prisoners live the ligfht off. The 3rd prisoner toggles it on, and he is then the leader.
|
|
IP Logged |
|
|
|
rmsgrey2
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #239 on: Apr 27th, 2004, 5:34am » |
|
The modification as you describe it won't work. If different prisoners enter on the first two days, then the prisoner entering on the third day is either the third prisoner to enter (and starts accumulation with a count of 3/100) or one of the first two repeating (and starts accumulation with a count of 2/100). If the same prisoner enters on all three days, things are still OK (start with 1/100) but if the same prisoner enters on each of the first two days but a second enters on the third, then he starts counting with a false count of 3/100... The simple way to salvage this is to have the prisoner on the second day turn the light on if they are the first prisoner repeating. That way, whoever enters on the third day knows exactly what's going on. There are other possible schemes for selecting the leader dynamically, for example, the first person to enter the room for the second time during the first 30 days turns the bulb on and becomes leader, and no-one else does anything for the rest of the 30 days. On day 31, if the bulb is still off, the prisoner entering knows that 30 different prisoners entered the room in the first 30 days, and becomes leader. Anyone who entered the room during the first 30 days and found the bulb off knows they've been counted, while anyone who hasn't been counted turns the light off at the first opportunity after day 30 (and then counts as counted). If you read the thread, there are more complex methods suggested for schemes involving multiple leader types.
|
|
IP Logged |
|
|
|
alien
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #240 on: Apr 27th, 2004, 8:24am » |
|
Quote:at the end of the day the prisoner is returned to his cell. |
|
|
|
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 #241 on: Apr 27th, 2004, 8:45am » |
|
yes, so? He can still be brought back into the interogation room again the next day.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 100 prisoners & a light bulb
« Reply #242 on: Apr 27th, 2004, 4:14pm » |
|
This is a step towards the "modified leader solution" (which can also be found in the thread). To go the rest of the way to it: How can you maximize the number of people who get counted before the leader is selected? The modified leader solution is a large improvement on the leader solution, but better results are still possible.
|
|
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
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: 100 prisoners & a light bulb
« Reply #243 on: Apr 27th, 2004, 5:19pm » |
|
Was there an attempt to solve this puzzle definitively for less than 100 prisoners? For 2 prisoners it is trivial (3 days average wait), for three - the 3-day dynamic leader selection looks like the optimal solution ([approx] 9.167 days average wait according to my simulations); for four - the 3-day dynamic selection works slightly better than the 4-day selection, giving [approx] 16.08 days, etc.
|
|
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 #244 on: Apr 27th, 2004, 8:52pm » |
|
Several people discussed solutions for 2, 3, 4 prisoners on some of the earlier pages.
|
|
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
|
|
|
Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 100 prisoners & a light bulb
« Reply #245 on: May 1st, 2004, 7:52am » |
|
I have been considering this puzzle lately. The most successful schemes all work to set a particular person to know that everyone has been to the room. The big time killer for these schemes is that the messages must be delivered to this person, so you must wait for a long time for the conditions to be just right for him to receive them. The point of the token-based solutions is for others to assemble the individual messages into mass-messages that can be passed at one time. But still the situation must wait on the opertunity to deliver the right message to the right person. I have been wondering if it might be possible to improve on this by allowing multiple copies of the messages to exist, and have multiple people able to recieve them, thus greatly increasing the odds of reception. To give an example, here is a scheme which suffers from the opposite problem as the token-based schemes do: it is extremely difficult to deliver the original message/tokens, so it is slow-starting, but once they are all delivered, should very quickly move to a win-condition. (I am not sure whether this has been suggested before or not. Clearly, it is very inefficient.) Everyone maintains a list of numbers from 0 to 99, representing prisoners that are known to have visited the room. A the starting meeting they are each assigned a number, which is the only number in their list at that point. The days are counted modulo 100, and if they visit the room on a day matching a number in their list, they turn the light on (or leave it on). If they visit the room and find the light on, they add the number of the previous day to their list. As soon as some prisoner has all 100 numbers in his list, he declares everyone has visited. The great flaw with this scheme is that it takes a long time for each person to publisize their own visits to the room, since they can only do so 1 time out of 100. But after a while knowledge of their visit disseminates throughout most of the prisoners, as everyone who knows of it repeats the message to someone else at every opportunity. What I am wondering is if some version of this idea can be combined with a token-based scheme to improve times. With token-based schemes, only one copy of each token/badge/crown can exist, and the struggle is to pass those tokens to a single person. In the scheme above, every message (token) is duplicated instead of simply passed, and everyone collects them. Because messages are duplicated, each must be unique in content, so that the receiver knows whether or not this is a message he has received before. Perhaps some mixture would help: a first stage wherein badges are created as outlined in the token-based schemes, but in the second stage, each badge is uniquely identified, and copied rather than passed. Everyone may collect them and the first to collect all of the badges declares freedom.
|
|
IP Logged |
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? " - Anonymous
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: 100 prisoners & a light bulb
« Reply #246 on: May 1st, 2004, 2:36pm » |
|
Srowen suggested the method of labelling the prisoners from 1 to 100 and the light being on on day n+1 meaning that prisoner n(mod 100) is known (by the person in on day n) to have been in. If I've counted correctly, it's reply #28 (near the top of page 2). He reports a simulated expected escape time around 95,000 days. In my post at the very bottom of page 9 I gave brief summaries of the categories of serious solution that have been proposed during the thread. As far as I know (having just re-read most of the thread), no-one has seriously explored a more general information copying strategy.
|
|
IP Logged |
|
|
|
Paul Hammond
Newbie
Posts: 29
|
|
Re: 100 prisoners & a light bulb
« Reply #247 on: May 1st, 2004, 2:39pm » |
|
on May 1st, 2004, 7:52am, Icarus wrote:I am not sure whether this has been suggested before or not. Clearly, it is very inefficient. <snip> The great flaw with this scheme is that it takes a long time for each person to publisize their own visits to the room, since they can only do so 1 time out of 100. But after a while knowledge of their visit disseminates throughout most of the prisoners, as everyone who knows of it repeats the message to someone else at every opportunity. |
| That method was in fact proposed by S. Owen on page 2. He estimated that it would take 95,000 visits for 100 prisoners. It seems to me that you could improve the method's appallingly slow start as follows: At first, proceed in periods of, say, 100 days (light is off at the start of each period). In period 0, if prisoner 0 visits he turns the light on, and then every subsequent visitor in the period knows that he has visited. Same for period 1, period 2 etc. After 100 periods, you reduce the period length substantially - perhaps even down to 1 day as in S. Owen's method. Of course, 100 x 100 = 10,000, so the first phase alone would be no quicker than the best method found so far, but this speed-up technique might be useful in combination with the token-accumulation method, as you propose.
|
|
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 #248 on: May 1st, 2004, 8:14pm » |
|
on May 1st, 2004, 2:36pm, rmsgrey wrote:As far as I know (having just re-read most of the thread), no-one has seriously explored a more general information copying strategy. |
| I, too, was rereading the thread, but had forgotten the details of Srowen's first solution while trying to comprehend all the later schemes. I knew the day labeling part came from some early proposal, but couldn't remember if "everybody collects" came with it. But indeed, the scheme I outlined is exactly Srowen's, and he deserves all due credit. Paul - That is a definite improvement to Srowen's scheme. It might be interesting to see if maybe a shorter interval length could reduce the expected time of this approach to at least beat that of the single leader approach. Alas, I lack the programming capacities of other contributors. Right now I am having a hard time thinking about these. This is why I decided to post now without trying to come up with a complete workable scheme.
|
|
IP Logged |
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? " - Anonymous
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: 100 prisoners & a light bulb
« Reply #249 on: May 2nd, 2004, 6:13am » |
|
Intuitively (ie quite possibly completely wrong) having shorter cycles than 100 days (My feeling is 10-30 days) for the initial stages would be better. I've been meaning to pick up on programming again, so I might throw something together to get some actual data. I wouldn't hold your breath though...
|
|
IP Logged |
|
|
|
|