wu :: forums
« wu :: forums - 100 prisoners & a lightbulb »

Welcome, Guest. Please Login or Register.
Mar 29th, 2024, 5:38am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: Icarus, Grimbal, ThudnBlunder, william wu, towr, SMQ, Eigenray)
   100 prisoners & a lightbulb
« Previous topic | Next topic »
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: 100 prisoners & a lightbulb  (Read 42918 times)
socrateinpigiama
Newbie
*





   


Posts: 1
Re: 100 prisoners & a lightbulb  
« Reply #25 on: Nov 26th, 2012, 7:33am »
Quote Quote Modify 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 Quote Modify 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 Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board