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?

We know not who is to go in first, but each knows their own number.

The first prisoner (hopefully) finds his/her number within the allowed 50 and places it in that ordinal location.  The remaining 49 boxes which are allowed to be chosen are placed in their respective locations.

The second prisoner should then look for his/her number at that position.  On failure it is to be appropriately placed along with the other 49 selected.

Assuming this goes to plan the last prisoner knows that the boxes are in order from 1 to 100 and can assuredly choose freedom for all.

I'm not ready to calculate the probabilities of this, but I am happy to told about the weaknesses of this strategy.

Posted by brianjn on 2007-01-31 05:52:43