A group of terrorists have taken 100 men as hostages and numbered them as hostage 1,2,3...,100. The terrorists tell them that each one of them is asked to enter a room (one at a time) where there are 100 boxes each containing a paper with one number in it (each number is placed to a random box and each box contains only one paper).

Once a hostage is asked to enter a room he chooses 50 boxes to be opened and if he finds his number on any of the papers he will be escorted to a waiting room. If however the hostage fails to find his number all of the hostages are brutally killed. If all of the hostages succeed in finding their own number they all will be spared.

After telling this the terrorists give some time for the men to consider for an optimal strategy to survive. Once they have agreed on their strategy all communication is forbidden.

If all of the hostages choose 50 boxes at random their probability of survival is kind of weak (.5^100). What kind of strategy should they use to survive at least with 30% probability?

The first hostage sent in should be #1 (I'm assuming that the hostages can pick which order they go in as part of their strategy). He should make two lines of boxes. One with the even numbers and one with the odd numbers. When the hostage finds his box, he should put it in a corner out of the way. If hostage #1 finds the #2 box, he should place it in front of the door. The second hostage should be #2.

So, when #2 goes in, he can see right away if #1 found his box. If there isn't a box in front of the door, he knows it is in the pile that hasn't been sorted yet. There should be fifty boxes left to sort through, and #2 knows for a fact that his box is one of the fifty. After the remaining 50 boxes are sorted into odd and even piles, everyone has a 100% chance of finding their box. To quicken the pace, each hostage should stack their box in the corner with the other previously found boxes.

This strategy would give the group as a whole a 50% chance of survival. The only person taking a risk would be the first hostage. After that it's easy.

Posted by andrew on 2007-01-29 16:16:30