Puzzle: 100 Prisoners and a Light Bulb

Re:Puzzle: 100 Prisoners and a Light Bulb by oditogre on Tuesday November 13, 2007 @05:28PM (#79546)

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.

[ Parent | on HN ]

Re:Puzzle: 100 Prisoners and a Light Bulb by barns on Wednesday November 14, 2007 @12:01AM (#79658)

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.

[ Parent | on HN ]

Re:Puzzle: 100 Prisoners and a Light Bulb by mxh on Wednesday November 14, 2007 @02:31AM (#79688)

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.

[ Parent | on HN ]

Re:Puzzle: 100 Prisoners and a Light Bulb by run4yourlives on Wednesday November 14, 2007 @12:27PM (#79774)

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.

[ Parent | on HN ]

Re:Puzzle: 100 Prisoners and a Light Bulb by lotu on Wednesday November 14, 2007 @11:25PM (#79986)

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

[ Parent | on HN ]