Puzzle: 100 Prisoners and a Light Bulb

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 ]