Prisoner Problems

Quite a few well-known logic puzzles involve a prison setting, giving them a darker tone that makes them memorable and more fun to think about.

This joke prisoner problem is amusing but impossible, as its rather surreal solution involves English homonyms.

I also won't bother describing the famous prisoner's dilemma from game theory.

Then there's the paradox about the prisoner who's told he'll be executed some time next week and that it will be a surprise. So he reasons thus: "They can't kill me on Friday, because I would know by Thursday night and it would not be a surprise."

"But this implies if they haven't killed me by Wednesday night, then I know I'm dead on Thursday because I can't be killed on Friday. Which means it wouldn't be a surprise. Hence I cannot be executed on Thursday."

"Repeating this argument a few times shows that I cannot be executed on any day next week!" he concludes triumphantly.

But on Tuesday morning he is executed, much to his surprise! What's going on?

And there's the tale about the prisoner who is to choose his method of execution: if the last statement he utters is true then he is executed in some gruesome fashion, and on the other hand, if it is false then he is executed in some different but equally gruesome fashion. (The particular methods of execution change from telling to telling. I just can't think of any right now.) What should he say?

A tougher puzzle involves one-hundred prisoners in a prison that contains one-hundred cells and a single room with a single light bulb that can be turned on or off. Every day a prisoner is chosen at random and placed in the room. At any time, any prisoner can ask for freedom. When he asks, if every prisoner has spent at least one day in the room with the light bulb then everybody is set free. (The warden has been keeping track.) Otherwise everybody is executed.

The prisoners can talk amongst themselves before entering this bizarre jail, but once inside they are kept isolated, and the light bulb becomes their only means of communication. How can they free themselves?

Lastly, there is a similar problem that is the main reason for this post. A friend told me this puzzle a few months ago and I don't want to forget it.

Again, there are one-hundred prisoners and a special room, but this time the room contains one-hundred identical boxes, each containing exactly one slip of paper bearing a prisoner's name. Every prisoner's name is present, but no one knows which box contains which name.

The prisoners are taken to the room one at a time. Once inside they are allowed to open and examine the contents of up to fifty boxes. They must then leave the room as they found it, so the boxes they chose are closed when they are done.

After all prisoners have visited the room, if each prisoner has seen his name on a slip of paper then they are all free to go. Otherwise they are all executed.

As before, they can all examine the room and boxes (but not open them) and devise a strategy together beforehand, but no communication is permitted once the process begins.

Clearly if a prisoner picks fifty boxes at random he has only a 50% chance of finding his own name, and if every prisoner does this then the chance that all of them find their names is 1/2^100. That is, they will almost certainly be executed.

How can they obtain at least a 30% chance of surviving?