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?

Leaving the boxes in the order they were found in, they are numbered. Hostage 1 comes in and looks under the box associated to his number. If, for example, he find #17 under it, he will go look under box #17, and goes where that box tells him to go. Finding his number would eventualy send him back to box #1, thus making a sort of "cycle" among the boxes. If that cycle is less than 50 boxes long, all hostages with numbers in that cycle will be spared. The odds of all of them surviving are equal to the odds of no cycle being more than 50 boxes long.

I'm not very good with probabilities, so hopefully someone else will come along and do the math required. I'm willing to bet that this is the intended way to solve it. Let's hope these terrorists arn't math majors.

Posted by George on 2007-01-29 14:36:59