(I promised the guys in a Nadder! to post this, so here I go! Keeping my promise!)
Some time ago, Panos Papasoglu, a friend of mine, over dinner at the (highly recommended) Khukuri Nepalese restaurant in Edinburgh, told me a simple probability problem which, in his words, was the most interesting mathematical puzzle he's ever heard:
There are 100 prisoners who are sentenced to death. However, the prison's head, being merciful, offers them a possible way out: He puts 100 identical boxes, perfectly arranged in a row, in the death chamber and places the prisoner's names in them, one name per box. The prisoners wait in a room outside the death chamber. Each prisoner is asked to proceed to the death chamber and open at most 50 boxes. If he finds his name in one of them he is transferred to the mercy room where he waits. If all prisoners succeed in finding their names then they are all spared from death and are released. On the event that one of them fails to find his name in one of the 50 boxes of his choice, the process is stopped and all prisoners are immediately executed. The prisoners can talk to one another whilst in the waiting room, but, once a prisoner gets transferred to the death chamber or the mercy room, he cannot tell the others anything at all.
The question is: Can the prisoners devise a strategy to increase their chance of survival?
To see why the question makes sense, let's see what the chance is in the absence of any strategy: The chance that a prisoner will find his name is 50/100=1/2. So, if the prisoners act independently from one another, the chance that they all find their names is 1/2100 = 0.000000000000000000000000000000789. (That is, if the experiment is repeated in one thousand billion billion billion prisons then in roughly one of them the prisoners will survive.) So any strategy at all is welcome.
But is there any? What can the prisoners do? They are completely ignorant about the boxes' contents and each prisoner cannot talk to the others.
After hearing the problem, I though the same as everybody else. No way. I then went home and thought harder. I realised that, indeed, there is something that the prisoners can do. In a sense, there is one source of randomness (the random placement of names in boxes) and another one (the ordering of prisoners). If, somehow, we can couple the two (the worst we can do is keep them independent!), then, certainly, we can increase the probability of success. I thought of some schemes but none of them gave me the fantastic increase as the one presented next.
THINK IF YOU WISH ...
AND WHEN YOU ARE READY TO GIVE UP...
CLICK HERE
Some time ago, Panos Papasoglu, a friend of mine, over dinner at the (highly recommended) Khukuri Nepalese restaurant in Edinburgh, told me a simple probability problem which, in his words, was the most interesting mathematical puzzle he's ever heard:
There are 100 prisoners who are sentenced to death. However, the prison's head, being merciful, offers them a possible way out: He puts 100 identical boxes, perfectly arranged in a row, in the death chamber and places the prisoner's names in them, one name per box. The prisoners wait in a room outside the death chamber. Each prisoner is asked to proceed to the death chamber and open at most 50 boxes. If he finds his name in one of them he is transferred to the mercy room where he waits. If all prisoners succeed in finding their names then they are all spared from death and are released. On the event that one of them fails to find his name in one of the 50 boxes of his choice, the process is stopped and all prisoners are immediately executed. The prisoners can talk to one another whilst in the waiting room, but, once a prisoner gets transferred to the death chamber or the mercy room, he cannot tell the others anything at all.
The question is: Can the prisoners devise a strategy to increase their chance of survival?
To see why the question makes sense, let's see what the chance is in the absence of any strategy: The chance that a prisoner will find his name is 50/100=1/2. So, if the prisoners act independently from one another, the chance that they all find their names is 1/2100 = 0.000000000000000000000000000000789. (That is, if the experiment is repeated in one thousand billion billion billion prisons then in roughly one of them the prisoners will survive.) So any strategy at all is welcome.
But is there any? What can the prisoners do? They are completely ignorant about the boxes' contents and each prisoner cannot talk to the others.
After hearing the problem, I though the same as everybody else. No way. I then went home and thought harder. I realised that, indeed, there is something that the prisoners can do. In a sense, there is one source of randomness (the random placement of names in boxes) and another one (the ordering of prisoners). If, somehow, we can couple the two (the worst we can do is keep them independent!), then, certainly, we can increase the probability of success. I thought of some schemes but none of them gave me the fantastic increase as the one presented next.
THINK IF YOU WISH ...
AND WHEN YOU ARE READY TO GIVE UP...
CLICK HERE
