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?

another way cold be: prisoner no.1 enters, looks at the first 50 boxes. if he finds his number he will move it to the end of the second half of 50 boxes, and the rest 49 he would arrange as so: the largest number he found the first and the smallest second and so on alternately in all the left 49 boxes in a descending order.

then the second prisoner that would enter is no.100, which knows to check the first box- if the number there is smaller than his, he knows to check boxes 50-99, and the he can rearrange them with the first 50, (knowing what the gaps in the first 50 boxes must be).

 if he does find his number in the first 50 then the next prisoner, no.2 would do that.

I'm not good with calculating probabilities though...

Posted by Talia Meir on 2007-01-30 11:24:25