Author |
Topic: 100 prisoners & a lightbulb (Read 43029 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print