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 plan must have a form of communication (non-verbal) after the first person enters the room and looks at the 50 slips in the 50 boxes.

If given the chance, the first person should rearrange the 50 boxes that she looks at from lowest to highest. Spacing between the boxes could also give a clue as to the number of missing boxes between any given two boxes.

success = 50%

The second person, if her number is 2, would look at the first two boxes and 48 of the remaining boxes. (48 of the first 50 can be eliminated)

success = 50/52 = 96%  cumulative success = 48%

If her number is not 2, but lets say 50, then look at the 10 middle boxes and 40 of the remaining 50. I am assuming that the odds are favorable that 50 will be close to the center.

success = approx 50/60 = 83% cumulative success = 41%

Then rarrange the 40 boxes with the original 50.  

If the third persons number is 27 then choose the boxes 10-50 of the 90 already looked at and the 10 that have not been looked at. Then reposition in correct order

success = 100% cumulative success = 41%

Posted by Leming on 2007-01-29 10:36:43