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.

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 days

I 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 :)

My solution, before I look at others' replies: One person is designated to turn on the light. The designated person should be the person with the most well-ingrained sleeping pattern in the group. If anybody comes in and it's their first time in the room and the light is on, they turn it off. If the designated guy finds the light to be on for 3 visits in a row and he's sure it's been 200 days since the first time, I think he can fairly confidently declare that all have visited the room.

On any given day, a given prisoner has a .99 probability of NOT visiting the room.

Over a period of N days, a given prisoner has a pow(.99, N) probability of having _NEVER_ visited the room. Therefore, the probability a given prisoner HAS visited the room at least once over a period of N days is (1-pow(.99, N)).

Therefore, the probability that X prisoners have each visited the room at least once over a period of N days is pow((1-pow(.99, N)), X)[1]. If I'm in the room, the question I need to answer is: How likely is it that each of the 99 other prisoners have visited the room at least once in the preceeding N days?

Let's visit Mr. Python:

   N    P(safe)  Cost[2]
 ----- -------- ----------
  100: 0.000000 (18250.00)
  200: 0.000001 (18249.99)
  300: 0.006887 (18124.31)
  400: 0.166419 (15212.86)
  500: 0.520678 ( 8747.63)
  600: 0.787901 ( 3870.80)
  700: 0.916504 ( 1523.81)
  800: 0.968598 (  573.08)
  900: 0.988391 (  211.87)
 1000: 0.995735 (   77.83)
 1100: 0.998437 (   28.53)
 1200: 0.999428 (   10.45)
 1300: 0.999790 (    3.82)
 1400: 0.999923 (    1.40)
 1500: 0.999972 (    0.51)
 1600: 0.999990 (    0.19)
 1700: 0.999996 (    0.07)
 1800: 0.999999 (    0.03)
 1900: 0.999999 (    0.01)
 2000: 1.000000 (    0.00)
 2100: 1.000000 (    0.00)
 2200: 1.000000 (    0.00)
 2300: 1.000000 (    0.00)
 2400: 1.000000 (    0.00)
 2500: 1.000000 (    0.00)
 2600: 1.000000 (    0.00)
 2700: 1.000000 (    0.00)
 2800: 1.000000 (    0.00)
 2900: 1.000000 (    0.00)
 3000: 1.000000 (    0.00)
 3100: 1.000000 (    0.00)
 3200: 1.000000 (    0.00)
 3300: 1.000000 (    0.00)
 3400: 1.000000 (    0.00)
 3500: 1.000000 (    0.00)

[1]I know this can't be exactly right, because prisoner visits aren't independent events, but I figure it can't be that wrong, and I want to go home.

[2]Cost is calculated in expected days of life forgone, multiplying (1-P(safe)) by 50 years by 365. Arbitrary, but it gives some idea of how much expected life you gain by waiting longer to roll the dice.

[3]I know this is ducking the intention of the question, but I think the point that death isn't that bad a risk if the probability is low is a legitimate one.

If I'm right, I saved myself 22 years in solitary confinement.

(I'm working on a solution; will post it here soon)

The prisoners select a counter, whose count begins at 0 and increases to 1 when he himself enters the room.

When the counter enters the room:

1)If the bulb is off, leave

2)If the bulb is on and relatively cool, turn it off, increment count by 1, and leave

3)If the bulb is on and relatively hot, turn it off, increment count by 2, and leave

When others enter the room:

1)If the bulb is off and the prisoner has yet to signify his presence, turn it on at the end of the day. This counts as signifying one's presence.

2)If the bulb is on and the prisoner has yet to signify his presence, leave it on all day. If the bulb was relatively cool, then this will count as signifying one's presence.

3)If the bulb is on and relatively cool and the prisoner has already signified his presence, turn it off at the start of the day and back on at the end of the day.

4)Else, do not touch the bulb.

When the count reaches 100, he asserts that all have visited.

Everytime someone visits the room has to take the following two steps:

(1)actions:

- if it's their first time make sure the light is off (i.e. if off don't touch, if it was on, turn it off)

- if you have been there before make sure the light is on (i.e. if it was off turn it on, and if it was already on don't touch it)

(2)counting:

- if the light was off when you walked in then add one more to your count

- if it was on then don't count anything

this way everyone counts, we now have 100 counters. And whoever reaches hundred first (counting themselves in) should report it.

Note: the guy that went in on day one, should not count for the day before, but everyone else will count their day before if appropriate (based on the rules above).

I think you should give the best answer to this question NOW, the one you say that takes 3500 days... I also hope that the first answer given by slashcom is not in fact the best answer (as you said it yourself) and you didn't just waste everyone's time for nothing ...even if its 5 min of everyone's time, it adds up to a lot of time and its not ethical...

the reason I am posting this is because this post is almost out of the news and it already seems to be forgotten ... I would be pretty pissed if I had spent more time like other users such as curi and everyone else that tried to solve your problem...

I couldn't resist peeking ;)

The counter will always turn the light off (and count the number of times he does so).

When the counter reaches 99, he knows that all 100 prisoners have visited the room.

It could take forever - especially since the jailer can not be truly random and could potentially pick a single prisoner (or even the counter) every single day.

All it takes is two prisoners to go to the room in between counter visits, and the counter will only ever reach 98.

See the subtle difference between slashcom's answer and yours?

When each prisoner goes into the room they will cut themselves and leave their mark in blood in the room. Or they could scratch the wall etc.

Before you say this won't work because the warden could mess with the marks I don't have 30 something years to wait around for randomness to finish.

In other words, is the intent to use only whether the bulb is on or off to solve this?