wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> 100 prisoners and no lightbulb
        
(Message started by: kenny on Jan 14^th, 2003, 8:15am)

Title: 100 prisoners and no lightbulb
Post by kenny on Jan 14^th, 2003, 8:15am

Same situation as "100 prisoners and a light bulb puzzle", exept...

The light-bulb burns out on day 3. The prisoner look to the guard, who says "tough luck".

The prisoners know that, while this is a very well-kept prison, it is still a prison, and that the probability that any given prisoner will die from disease/rats/etc. on any given day is 1/1 million.

On what day should a prisoner claim that all 100 prisoners have been in the living room?

On what day should such a claim have been made if the light-bulb were still working?

-- Ken

Title: Re: 100 prisoners and no lightbulb
Post by redPEPPER on Jan 14^th, 2003, 9:22am

Is this a joke? Or is this just an unpolished riddle? :P

If it's the former:
Ha ha!

If it's the latter:
What does the death probability brings to the riddle? Shall we assume that, if a prisoner dies before going to the room, they're all toast? Or do they only have to be sure that at a given time, every surviving prisoner has been to the room?

This made me think that you don't really need the bulb, you could use the position of the switch (up or down). But this has to be decided previously. In this situation, it came as a surprise, so the prisoners are pretty much toast, as they cant' gather a second time to adapt their strategy.

Unless the last prisoner comes to the room, tries to work the switch, looks at the guard, and the guard says "For the 100th time: tough luck!!"

Title: Re: 100 prisoners and no lightbulb
Post by kenny on Jan 14^th, 2003, 9:49am

It's no joke; it's a different puzzle.

And, rather than "bulb burned out", put in "the switch broke". Thus, the bulb/switch offer no information.

And assume that any prisoner who dies is taken out via the living room.

I could explain how the probability of death is relevant, but that'd be a very big hint.

-- Ken

Title: Re: 100 prisoners and no lightbulb
Post by James Fingas on Jan 14^th, 2003, 9:59am

Kenny,

Is the idea here to maximize the expected number of prisoners that will escape alive? If so, I think I can see where you're coming from...

Title: Re: 100 prisoners and no lightbulb
Post by Chronos on Jan 20^th, 2003, 2:36pm

I can think of two logical interpretations for the prisoners' motives. One, a prisoner might try to maximize the number of prisoners who escape alive. Two, each prisoner might try to maximize the probability that he, himself, will escape alive. I think that these might turn out to yield the same answer, but then again, each prisoner has information about his own condition which he does not have about any other prisoner, and that might change the answer.

Also, is the condition for release "All prisoners have been in the room", or "All surviving prisoners have been in the room"? This can definitely make a difference. Suppose, for instance, that Bob gets called in for the first time on day 99, and is also called in every day for the next 500 days. At this point, the most likely explanation is that everyone else has died, and he, as the only surviving prisoner, knows he's been in the room, so if it's just survivors that count, he should demand freedom. On the other hand, if all 100 need to have passed through the room, then someone has definitely not been called in, and he has to take the chance that that person is still alive, and wait, because it's the only chance he's got.

Title: Re: 100 prisoners and no lightbulb
Post by PaulH on Aug 12^th, 2003, 5:22pm

Icarus linking to this puzzle prompted me to look at it again.

I'm getting an answer of 1330 days for the first question.
Let p₁ be the probability that all prisoners have visited the room on a particular day. The prisoner who visits that day can expect to return in 100 days time, on average, after which time there will be a higher probability, p₂, that all prisoners have visited. In the meantime he will have a 0.999999¹⁰⁰ probability of surviving. So if p₂ x 0.999999¹⁰⁰ is less than p₁, a prisoner is better off making the claim. By my calculations that happens at day 1330, but that is only an estimate because calculating p₁ and p₂ is tricky.

Title: Re: 100 prisoners and no lightbulb
Post by turtler7 on Aug 20^th, 2003, 6:06am

Kenny said all dead prisioners are taken out through the living room. So all prisioners count. Either they are surviving and must or if they die their corpse goes through. Would this make it posible for 2 prisioners to pass through in one day? Since one is taken there then one dies? It should just lower the number of days by 1/1,000 of the standard answer. since its 1/a million that die and theres 100 of them...

Title: Re: 100 prisoners and no lightbulb
Post by Mistel on Jul 4^th, 2005, 1:02am

This riddle is impossible. You can use probability, but what if everybody is alive after 10 years, but only 1 guy has gone in? Unlikely, but possible that the same guy is chosen like 3500 times. However... There is a solution I just thought of. Lets say that each guy is chosen 3 times (3 is a random number) before the last guy is called. Each time a guy goes in the room, he leaves the light off. When a guy is repeated, after each of his repeats (two times lets say) he leaves the light on. So the next guy (assuming that no guy is called twice in a row) assumes that the number of days minus 1 is the number of guys that have been in the room. But then again he couldn't tell anybody else this... Something about the position of the switch like halfway? Well almost there. Hmm... Maybe if everybody (their cells) was lined up in a straight line of cells, then the first guy could look over at each cell while he was waking by and if the prisoner had a thumb up, he had been to the room. This would take years though.

This riddle has no solution. It was congened by an idiot who wanted to fool people or by the smartest man in the world, who became smart after getting terminal cancer 10 years ago. There is no 100% solution. 99.99999999% yes, but no 100%. According to probability, it would be like 3 years. According to every possible outcome, it could take 100 years and everybody could die.

Title: Re: 100 prisoners and no lightbulb
Post by Grimbal on Jul 4^th, 2005, 4:08am

Hey! where has my post gone? Grrr. Here it is again:

One dramatic twist is that if it is the same prisonner who entered the first 3 days, it will probably postpone the optimal day for 2 days. That means that he can expect someone will call 2 days early, but he has no way to let the others know!

In fact, it is true for every prisonner. The optimal days is different for each, because a prisonner knows whether he was in. The only unknown is who among the 99 others was in during the days where he was not. So, from the point of view of one prisonner, the optimal day depends on the number of times he was in. The less he was in, the more it is probable that all other were. So, it is the one who was chosen the less often will be the first to believe the day has come and make a call for a release.

Now, since it is always the most optimistic who will end up doing the call, there is probably a bias towards an earlier call. This should probably be taken into account. Somehow.

And as Chronos mentionned, the fact to be taken in more often can also hint at some deaths among others, which means it would rather move day D to an earlier day. This needs to be also taken into account.

Not easy.

This being said, a mortality rate of 1/1Mo per day is quite low. It means an average lifespan of a million days or 2700 years. Maybe they need it.

Title: Re: 100 prisoners and no lightbulb
Post by River_Phoenix on Jul 5^th, 2005, 7:29am

Do all the prisoners realize that the bulb burned out? Or are they just going in every day and seeing the light off?

Anyway, if we are maximizing total survival rate and prisoners are being called in randomly there may be a probabilistic answer, but for each person trying it maximize his own survival, it further depends on how risk averse he is. And there's twists like Grimbal said. Probably someone who went in once and only once, and is not averse to risk will make the call after 3 or 4 years, but that is not scientific.

What about the case where the switch still works, but there is also a mortality rate, and only the living people need to have entered? Further, what if the other prisoners don't know how many are dead and who is still alive?

Title: Re: 100 prisoners and no lightbulb
Post by Grimbal on Jul 5^th, 2005, 3:47pm

Hehe... maybe it's the switch that is defective and kills the prisonners. ;D

Title: Re: 100 prisoners and no lightbulb
Post by River Phoenix on Jul 5^th, 2005, 6:19pm

But every time the switch goes haywire, it goes into a broken position, which has to be fixed by the next prisoner, who will know that somebody died. So they all have to keep track of corpse tokens :o

Title: Re: 100 prisoners and no lightbulb
Post by SMQ on Jul 6^th, 2005, 6:07am

But in order to collect the corpse token they need a virtually dead badger... ;D

--SMQ