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?
I wonder if anybody will read this, as the thread died more than two years ago. At any rate, three mod n schemes have been suggested so far:
Mod 2: Two designated prisoners, even and odd days
Mod 7: 7 designated prisoners, days of the week
Mod 100: Posted solution.
It turns out that all mod n schemes (n > 1) have a 1/100 chance of having a light turned on on any given day, so they are all tied.
HERE'S THE MATH:
Warden kills one of the selected n with probability n/100. If that occurs, one of the remaining (n-1) goes into the room with probability (n-1)/99, and has a 1/n probability that he can turn on the light.
or
Warden fails to kill one of the selected n with probability (100-n)/100. If that occurs, one of the selected n goes into the room with probability n/99, and has a 1/n probability that he can turn on the light.
Probability that light gets turned on tonight =
(n/100)((n-1)/99)(1/n) + ((100-n)/100)(n/99)*(1/n) =
(100n - n)/(n*99*100) = 1/100
Interestly enough, if the warden doesn't kill anybody, then the odds are unchanged. One of the original n goes into room with probability n/100, and has a 1/n chance of turning on the light.
(1/n)*(n/100) = 1/100. The only difference if the warden doesn't kill anybody is that now n = 1 works also, with daily probability 1/100.
The calendar scheme suggested by Charlie is not a mod 31 scheme, because not all months have 31 days. Prisoners 1-28 have a greater than 1/31 chance of turning the light on when they go in the room, and prisoners 30 and 31, have a less than 1/31 chance. Now there are five cases to consider: Warden kills (a) Prisoner 30, (b) Prisoner 31, (c) Prisoner 29, (d) One of prisoners 1 - 28, or (e) some other prisoner. I haven't done the math, but I suspect that it all evens out, and that there is still a daily probability of 1/100.
FINAL NOTE:
Among all the schemes, I prefer the day of the week scheme. If prison is like any other institution, then prisoners know what day of the week it is from what's on TV, or what the chef is serving, or how many days since Sunday services.
Edited on July 18, 2009, 2:12 pm
All mod n schemes work equally well
