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 just read the solution and I find mine is much better.

Number 1, all the prisoners only have to remember two names and two situations instead of 100 situations and 100 names.

Number 2, I thought about this method while writing my solution and decided that method was flawed because the chances of the prisoner getting chosen on his particular day are roughly 1/10000 (100 prisoners, 100 numbers, multiply out).   My method gives 1/100 chance every 100 days.   If we were to assume that it takes a maximum number of days equal to the total chance of the light being turned on then your method takes 10000 days or roughly 30 years, my method takes 200 days if the first prisoner is the one who gets killed, 100 if he doesn't or roughly 1/3 to 2/3 of a year.

Posted by Brandon on 2007-03-19 17:52:02