wu :: forums « wu :: forums - 100 prisoners & a lightbulb » Welcome, Guest. Please Login or Register. Apr 17th, 2024, 8:48am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: SMQ, towr, Icarus, Eigenray, Grimbal, william wu, ThudnBlunder)    100 prisoners & a lightbulb « Previous topic | Next topic »
 Pages: 1 2 Reply Notify of replies Send Topic Print
 Author Topic: 100 prisoners & a lightbulb  (Read 42938 times)
socrateinpigiama
Newbie

Posts: 1
 Re: 100 prisoners & a lightbulb   « Reply #25 on: Nov 26th, 2012, 7:33am » Quote Modify

The solution is:
The prisoners agree on who counts. Say his name is Tom.
When a non-Tom prisoner is called he:
-turns on the light if the light is off and he never turned it on
-nothing otherwise

So, a non-Tom prisoner will, some day, turn the light on, then never do anything again.

Every time Tom gets called, if he finds the light turned on, he turns it off and count +1.

When he reaches 99 he can say without doubt that everyone has been called.

You can do this for N prisoners also.
 IP Logged
Paul Hammond
Newbie

Posts: 29
 Re: 100 prisoners & a lightbulb   « Reply #26 on: Nov 26th, 2012, 4:59pm » Quote Modify

Yes, that is the so-called "single leader" solution. It takes about 10,418 days on average  (see graphs on the previous page of this thread):

We have to wait 99 times for the counter to turn the light off, with an average wait of 100 days each time, so that's 9,900 days.

Then for the last prisoner to be counted we have to wait an average of 100 days for him to turn up, for the second-last we have to wait 100/2 = 50 days (because it could be either of the two remaining prisoners), and so on. Total expected wait for all the other prisoners is 100/1 + 100/2 + ... + 100/99, or 100 times the 99th Harmonic number, which is approximately 5.18.

That gives 518 days, and 9,900 + 518 = 10,418 .
 IP Logged
 Pages: 1 2 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »