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 AZ
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 20070307 11:20:07 