Puzzle: 100 Prisoners and a Light Bulb

The prisoners elect a counter. His count is initially 0, but increases to 1 the first time he walks into the room. Whenever he visits the lightbulb he will do the following:

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.

How many days does this take on average?

I haven't done a simulation, but I would guess not much more than 10,000. Almost every visit of the counter would decrement the number of prisoners who haven't flipped yet by one.

There's a solution that takes around 3500 days.

Curse you, amichael! No! No, I am not going to try to solve this problem tonight. I'm going to do ourdoings.com coding on the train ride home. I am not going to think about prisoners, light bulbs and distributed systems. I'll check in tomorrow and see if someone else has posted the answer, but I won't try to come up with it myself. You tempt me, but I resist. :-)

First 99 days:

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 wrote code. 1000 trials. naive mean: 10389.832 my strategy's mean: 9392.652

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.

Here's a paper on the subject:

http://www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBul...

It includes my answer :)

can you run mine through and see how many days you get!

I'm working on a solution using the current day (modulo the population) as a kind of covert channel to keep track of the number of prisoners who already visited the room (the basic idea is that, if the light is on on day 64, at least 64 people have visited the room).

I still have a bug in my algorithm and I'm not even sure it will really work.

Good guess. 100 runs: Average: 10163 Lowest: 7762 Highest 12391

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

http://news.ycombinator.com/item?id=32766

It would probably be helpful if that information was readily available via a link near the "add comment" and "reply" buttons

Along with all other relevant info for working with text in comments.

Thanks.

 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 just realized I used "one" instead of "on". :-P

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?

Somebody should do an Ask PG for this. The line breaks in the comments drive me nuts. Sometimes they work, sometimes they don't. Sometimes you can start with them working and then they're not working again.

I think the chance of anyone being lucid enough to carry out the solution after 9.5 years of solitary confinement is small enough that the solution doesn't really matter. Someone will say they've all been in there after the first year just to put themselves out of their misery!

dude, it's a puzzle. Don't think of it as a real life situation.

In stead of waiting a decade or more, I would make a shank.

Upmodded for proof of first optimal brute-force solution.

I now have Tool stuck in my head. Yes, it's related to the puzzle. Would probably be a better puzzle if you said they were aiming to get out ASAP (although you could fairly assume it...)

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.

The puzzle states that he has to be 100% sure that everyone had been to the room. "fairly confidently" is not good enough here. And, it won't matter if you increase the number of visits in a row to 5, 20, or more, there is still no guarantee.

Balls to that. I'm armed with a bad attitude and worse math. By my reckoning:

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)

After 1000 days, I'm guessing everyone's visited. Screw you guys, I'm going home.[3]

[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.

I'm with you. Hell, even 1000 days is a long time, I'd give 'er after 800. If I'm wrong, such is life.

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

You will also save your self 22 years in solitary confinement if your wrong. So win win.

I love this: "...from his or her own cell", "...if he or she wishes"!

It can take less than 20 days if they have Michael Scofield with them.

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

Assuming this is an incandescent lightbulb with mediocre or poor heat conductivity and that the lapse between "end of the day" and "start of the day" is sufficiently short, extra information can be communicated using the temperature of the bulb (unless it burns out). For example:

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.

I suppose yet further information could be attempted to be communicated by toggling the bulb enough to attempt to cause it to burn out and then observing replacements by finding a serial number of some sort, but that's getting outlandish.

You can also try to twist the bulb in the socket and observe the orientation of the text written on it relative to other markers in the room.

I would make every prisoner into a counter!

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).

so, the light gets turned off 100 times in total. there are 100 different people counting. none ever reach 100 in their count.

I was trying to eliminate the one counter to make it faster, but I see your point ...you just saved a bunch of lives, and got yourself an up vote!...I looked at the other possible solutions and they all seem to take a while, but I am planning a escape, are you in?

dear amichail,

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...

A solution that takes around 12 years [http://www.algonet.se/~ug/projects/lightbulb/double.html]

I couldn't resist peeking ;)

hopefully we'll get the one with 3500 days too (at this point just to know we weren't fooled and wasting time)

The group selects one person to work as a counter. All other prisoners will only turn on the light if it is off and it is their first time in the room (if it's on they do nothing).

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.

Aren't the chances of it not taking forever infinitesimal?

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?

I was going to bite my tongue before commenting on this, but that is the answer.

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.

I've written a simulator that seems to fit with intuition, but you guys might want to check out my code (http://scripts.mit.edu/~bcater/prisoners_code.php). It gives me just under 10,000 operations, on average.

Are the prisoners prevented from turning the bulb or using other pieces of the room as counters?

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

The intent is to use the light bulb in the obvious way.

thats eazy if they all go in they should be able to say ...that bulb thing wount help really whats if it blows how many thing will a light buld light b4 it blows