Problem of the Week 1060
Detecting Disease Efficiently
This is based on a true story about detection of syphilis in U.S. military recruits during World War II. Source: D. Teague, College Math Journal 37:4 Sept 2006, 261-268.
Suppose that in a group of 1,000,000 men, 100 of them have a disease that can be detected by an expensive blood test, but it is not known which 100 have the disease. Suppose one has an unlimited supply of blood from each recruit, but is trying to minimize the number of tests needed to determine the 100 diseased cases.
For example, one could combine the blood of #1 and #2, combine the blood of #3 and #4, and so on, performing 500,000 tests. At most 100 of these will be positive. Then one could individually test the 200 men still in doubt, for a total of 500,200 tests. It is possible to do much better; for example, one can combine the samples after the first round, too.
Design a method that succeeds with, in the worst case, as few tests as possible.
Actually, I don't have a proof of optimality, so the idea is to get the number as low as you can. Perhaps a reader can provide a proof of optimality. An obvious lower bound is 100. The source I got this from does it with about 2500 tests, and it is certainly very close to optimal, but the source is considering a continuous version of the problem, and it seems possible to me that the answer in the discrete case posed above could differ by a small amount from this.
© Copyright 2006 Stan Wagon. Reproduced with permission.