I have an off by one error here. We only need to count to 99, not to 100. So I think it's 100*(100+99%2) or 14950.
-- Raul On Tue, Sep 11, 2012 at 11:23 AM, Raul Miller <[email protected]> wrote: > Initially, almost any prisoner will do -- the light bulb is initially > off, and almost any prisoner will turn it on. And then you have an > expected wait of 100 prisoners before it gets turned back off. > Simple... > > As time goes on, though, you have to wait longer and longer for a > prisoner that's not turned the light on to take action. And, then, > you have to wait another 100-ish prisoners to turn the light bulb off. > But these are two independent events. So I think at the end, we have > an expected value of approximately 100 prisoners to turn the light > bulb on for the last time, and then another expected value of > approximately 100 prisoners to turn it back off. So that's 200 visits > at the end for the last light cycle. > > If every case were like this, we would have 100 repeats of the on/off > sequence, for 20000 expected days. So 2e4 should be an upper bound on > expected value. I think the actual expected value is 100*(100+101%2) > or 15050 days (or slightly over 41 years). > > Of course, if any of the prisoners get sick and die before this time > elapses, that could mean that they never get out. > > Or, did I miss something? > > -- > Raul > > On Mon, Sep 10, 2012 at 11:32 PM, Jordan Tirrell > <[email protected]> wrote: >> I got an expected number of rounds around 1e6. It seems a bit high but I >> think it might be right. So if they want to be 100% they'll die of natural >> causes while waiting. >> >> I wasn't on the forums 5 years ago but its certainly a good problem. >> >> >> >> On Mon, Sep 10, 2012 at 6:06 PM, Roger Hui <[email protected]>wrote: >> >>> V. good. >>> >>> A related question for the 100 Prisoners problem, is the expected >>> number of rounds before the prisoners go free, if each prisoner has >>> the same chance of being picked in each round. >>> >>> Did you solve the 88 Hats problem when it was posed here 5 years ago? >>> >>> >>> >>> On 9/10/12, Jordan Tirrell <[email protected]> wrote: >>> > 99 of the prisoners switch the light if and only if it is currently off >>> and >>> > they have not turned it on in a prior round. >>> > >>> > The one other prisoner turns the light bulb off every time time he finds >>> it >>> > on (otherwise leaves it off). He asserts the claim after he has turned it >>> > off 99 times. >>> > >>> > >>> > >>> > On Mon, Sep 10, 2012 at 11:55 AM, Roger Hui >>> > <[email protected]>wrote: >>> > >>> >> 100 prisoners are in solitary cells, unable to see, speak or communicate >>> >> in >>> >> any way from those solitary cells with each other. There's a central >>> >> living >>> >> room with one light bulb; the bulb is initially off. No prisoner can see >>> >> the light bulb from his own cell. Everyday, the warden picks a prisoner >>> >> at >>> >> random, and that prisoner goes to the central living room. While there, >>> >> the >>> >> prisoner can toggle the bulb if he wishes. Also, 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. However, if it is indeed true, all prisoners are set free. >>> >> Thus, >>> >> the assertion should only be made if the prisoner is 100% certain of its >>> >> validity. >>> >> >>> >> Before the random picking begins, the prisoners are allowed to get >>> >> together >>> >> to discuss a plan. So -- what plan should they agree on, so that >>> >> eventually, someone will make a correct assertion? >>> >> ____________________ >>> >> >>> >> Posed to me by Arthur Whitney at Iverson >>> >> College<https://sites.google.com/site/iversoncollege/>. >>> >> This puzzle resembles the 88 >>> >> Hats<http://www.jsoftware.com/papers/88hats.htm>puzzle but is (IMO) >>> >> easier. >>> >> ---------------------------------------------------------------------- >>> >> For information about J forums see http://www.jsoftware.com/forums.htm >>> >> >>> > ---------------------------------------------------------------------- >>> > For information about J forums see http://www.jsoftware.com/forums.htm >>> > >>> ---------------------------------------------------------------------- >>> For information about J forums see http://www.jsoftware.com/forums.htm >>> >> ---------------------------------------------------------------------- >> For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
