Thursday, August 20, 2009

Prisoners and Boxes

In a certain despotic nation, there are many prisoners being jailed. To alleviate the problem, the Emperor has decreed for all the prisoners to be "removed". What is decreed must be done; however the person doing the actual work is the High Jailer.

The Jailer thinks that the cost of bullets to execute everyone is too high, so he offers the prisoners the chance to earn their freedom. He proposes a game. There are X boxes in a room, with each box having the name of one unique prisoner. Since there are X prisoners, each prisoner's name is found in one and only one box.

The game is as follows: Each prisoner will be allowed to enter the room one at a time. The prisoner can then open all but one of the boxes; however, if the unopened box contains his name, everyone will be executed. If he does find his name in the opened boxes, he must restore the room to its original condition and leave the room. The prisoner will not be allowed to communicate to any prisoners that have yet to enter the room. If after all the prisoners have visited the room and found their names, they will all be released.

Needless to say, the boxes are arranged randomly. Still, each prisoner has a fairly good chance of finding his name; there is only a 1 / X chance of failing outright.

One of the prisoners, who is an amateur mathematician, remarks that the chance of everyone surviving is ( (X - 1) / X ) ^ X . He notes that by applying limits and using l'Hôpital's rule, the chance of surviving will increase with X, reaching e^-1 (0.368) when there are infinity prisoners. Not too bad a chance, he thinks.

At this point of time, another prisoner, an expert mathematician, speaks up and claims to have a better strategy! He shouts, "Why, with my plan, it is almost certain that we'll all survive!"

What is the mathematician's plan, and what is the chance of survival?

Note: This problem was derived from The condemned prisoners and the boxes, but the solution for our problem is more easily obtained.

No comments: