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)

I like this idea :) (I think actually you have to choose the 50 boxes at one time though)

I think the math would go as follows. Since there can only be at most one chain of size 51 or greater, we need only find the probability that you make 50 hops without returning to the original box.

Start with any number -- there is a 99/100 chance that won't lead you to the start. Then there are 99 numbers which you could be lead to. (You can't be lead back to any numbers you visited without going through the start first.) So there is a 98/99 chance the next number won't lead you to the start... and so on. Thus the probability equals 99/100*98/99*97/98*...*50/51 = 50/100, so the prisoners have a 1-50/100 = 50% chance of all prisoners coming out alive.

Posted by Gamer on 2007-01-29 15:20:37