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 problem states "Once they have agreed on their strategy all communication is forbidden." -- so that might include non-verbal communication as well. If it is allowed, it is likely that you can't change spacing, orientation, or other characteristics of the boxes or the terrorists would catch on.

If the boxes looked identical, the boxes could be arranged without giving any clues to anyone who hasn't looked inside them. I agree with Leming's strategy. Move the boxes you look at to the front and order them.

They would need to predetermine a k, like 10 for example. Then when subsequent prisoners come in, they would pick k boxes from the sorted section and 50-k boxes from the unsorted section (and sort them). Once all the boxes are sorted, it is impossible to miss, and since they know k in advance, each prisoner can know how many boxes are sorted at that time, and thus where the sorted section ends.

The question now is what k maximizes the algorithm, as larger k mean more boxes chosen from the sorted section and an improvement in odds for that prisoner, but a small k means the boxes get sorted faster, so fewer prisoners with uncertainty.

Posted by Gamer on 2007-01-29 14:56:41