Note: Read this problem carefully, because it's completely different from the original.

As before, 100 prisoners are put into solitary cells, and there's a room with a light bulb. (No prisoner can see the light bulb from his or her own cell.) Every night, the warden picks a prisoner at random, and that prisoner goes to the living room. While there, the prisoner can toggle the bulb if he or she wishes. but this time, the prisoner needs to assert that he knows, which prisoner was in the living room before him. If the assertion is false, all 100 prisoners will be shot. However, if it is indeed true, all prisoners are set free. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.

The prisoners are allowed to get together one night, to discuss a plan.

But, the prisoners know that after that night, when they will go back to their solitary cells. the warden will choose one prisoner secretly (and this time, not randomly) and will kill him.

What plan should they agree on, so that eventually, someone will make a correct assertion?

(In reply to only 99% sure by Charlie)

To minimize the risk of falsely assuming that designated prisoner A was the one killed the first night, the prisoners could consult the following chart and judge an acceptable risk for all of them being shot. It's the probability that the designated prisoner, A, will not be the one killed the first night (0.99) times the probability he will go a specific number of days without having been in the room to be given the chance to turn on the light (0.99^d, where d is the number of days allowed), times the probability that after that number of day's the alternate will visit the room before him (0.5).

days   prob of 100
allowed   deaths
 100 0.18118619
 150 0.10961879
 200 0.06632007
 250 0.04012406
 300 0.02427531
 350 0.01468672
 400 0.00888556
 450 0.00537582
 500 0.00325240
 550 0.00196773
 600 0.00119049
 650 0.00072025
 700 0.00043576
 750 0.00026364
 800 0.00015950
 850 0.00009650
 900 0.00005838
 950 0.00003532
1000 0.00002137
1050 0.00001293
1100 0.00000782
1150 0.00000473
1200 0.00000286
1250 0.00000173
1300 0.00000105
1350 0.00000063
1400 0.00000038
1450 0.00000023
1500 0.00000014
1550 0.00000008
1600 0.00000005
1650 0.00000003
1700 0.00000002
1750 0.00000001
1800 0.00000001
1850 0.00000000
1900 0.00000000
1950 0.00000000
2000 0.00000000

DEFDBL A-Z
p = .01: q = .99
FOR days = 100 TO 2000 STEP 50
 pMistake = q * q ^ days / 2
 PRINT USING "##### #.########"; days; pMistake
NEXT

Posted by Charlie on 2007-03-07 11:20:07