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?

(In reply to An idea without the math. by George)

George

Still like your plan, but I think the success rate will be less than 50%.

The first person will enter and picking his box and following the numbers where they lead will have success as follows:

 = ((n-1)! * (n-x)!) / (n! * (n-x-1)!)  which I will call f(n)

  where n = number of personnel, x = boxes allowed to be searched

for n = 100 and x = 50 the first person will be successful 50% of the time.

This leads to the first person being unsuccessful 50% of the time or 1 - f(n)

Now, lets say the first person gets lucky and finds his number in his box. This probability will be = 1/n

The second person will not be successful some of the time. Specifically:

1 - f(n-1) = .495

Based on the first persons success, this will occur 1/n times or

[1-f(n-1)]/n = 0.00495 chance of failure

Total chance of failure is now 50.495%

Each chance of success for the first person, prior to looking through 50 boxes, leaves some small chance of the following searchers to fail.

Still working on the exact value. I find it quite iterative. ;) 

Posted by Leming on 2007-01-30 10:51:55