Puzzle for Today

Puzzle No. 161 – Tuesday 13 February

You have one hundred 5 ml samples of blood and know that up to nine could be carrying a particularly nasty disease. Luckily, there is a test for the disease that requires only 1 ml of diseased blood. What is the maximum number of tests that must be performed to identify all diseased samples?

Today's #PuzzleForToday has been set by the School of Mathematics at The University of Manchester

The Answer will be available for a week.

The answer is at most 47.

At first sight you might think that you need to test all 100 samples, but this is not the case because the samples can be pooled. The worst case is that the test is binary, indicating only whether the disease is present or not. We are interested in a methodology that has the minimum number of tests in the worst possible case, which is not the same as a method that has the lowest number of tests on average. This general type of problem is known as group testing and has been studied since the 1940s.

There is an information theoretic lower bound which is the logarithm to base 2 of the number of possible states. In this case there are approximately 2,100,000,000,000 states (different ways in which up to 9 numbers can be selected from 1 to 100), which gives a minimum bound of 41 tests. The question is whether this can ever be realised in practice. There is a method based on binary splitting (dividing small groups in two repeatedly) due to Hwang (1972), which can find the answer in at most 47 tests. Here's how it works:

We divide the 100 samples into 12 groups of 8 samples each and one group of four. We test these groups (13 tests) and at most 9 will test positive. We must now consider the separate possibilities:

- Exactly 9 test positive, in which case we know that each group contains 1 diseased sample and we can find it in 3 tests per group using a binary search: test one half, if positive divide in half and repeat; if negative, divide the other group in half and repeat. This gives a total of 13 + 9 x 3 = 40 tests

- Exactly 8 test positive. Now we don't know whether each group contains 1 or 2 diseased samples. Proceed via binary search anyway, which will definitely yield 8 diseased samples. We now have (at most) 8 x 7 = 45 untested samples with at most one diseased. This can be found in 6 more tests in another binary search. This gives a grand total of 13 + 8 x 3 + 6 = 43 tests.

- Exactly 7, 6, 5 test positive, we use the same general approach to find a total of 47 tests, but because we now have more than one diseased sample after the first round of binary searches, we must repeat the overall process and subdivide the untested samples into groups of 16 (or 8 or 4 or 2) before binary searching.

- If 4 or fewer groups test positive then we can simply test each sample in the group individually. The maximum number of these tests is 32 and then we have (at most) 45 tests in total.

Note that none of these methods require any sample to be tested more than 10 times.

More fiendish brain-teasers and quizzes on BBC Radio...