Some statistics from my little python simulation:
n: 1000 (I ran my simulation 1000 times)
Mean: 10425.721 days
Stddev: 1005.34467779 days
Min: 7506 days
Q1: 9711 days
Median: 10391 days
Q3: 11074 days
Max: 14090 days
Note: can someone tell me how to do single linebreaks in the comments?
If I knew how to paste code in here, I would show you my simple python script to test it.
Edit: 1000 runs: Average: 10109 Lowest: 7389 Highest 13461
It would probably be helpful if that information was readily available via a link near the "add comment" and "reply" buttons
import random
def run():
prisoners = {}
for x in range(100):
prisoners[x]=0
days=0; counter=0; bulb=0
while counter<100:
prisoner = random.randint(0, 99)
days += 1
if prisoner == 0:
if bulb == 1:
bulb = 0; counter += 1
else:
if prisoners[prisoner] == 0 and bulb == 0:
bulb=1
return daysI still have a bug in my algorithm and I'm not even sure it will really work.
if bulb on: do not touch
if bulb off:
if you haven't been visited before, consider yourself counted, and do nothing.
if you have been in here before, turn it on. you are now the counter. look at the day number (1-based). if it's day 36, then 35 people (including yourself) have visited the room.
day 100:
if bulb off, and you haven't been there before, declare victory (super lucky!)
if off, but you have been there before, you're the counter and the count is 99.
if bulb on: turn it off.
after day 100:
use the original solution with a counter.
speedup:
you get about 12.2 people counted in the first 100 days. normally it's somewhere around one person counted per 100 days. so total time is around 100 + 87.8*100. a bit better. not near 3500 though.
i think the improvement was a little less good than i guessed because i jumpstart getting the first dozen or so people counted, and they are a little easier to count than the last people.
http://www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBul...
It includes my answer :)
1) If the lightbulb is off, leave the room.
2) If the lightbulb is one, turn it off and increment his count.
Every other prisoner follows the following rules:
1) If the lightbulb is on, do not touch it.
2) If the lightbulb is off and you have not flipped it on before, flip it on.
3) If the lightbulb is off but you have previously flipped it on, then do not touch it.
When the counter reaches 100, he may tell the guard that everyone has visited.