One Thousand Samples, Ten Tests, math that surprises you lesson

A collection holds 1,000 samples, and exactly one of them is special. A test can be run on a pool made by mixing portions of many samples, and it answers yes when the special sample is in the pool and no when it is not. If the samples are tested one at a time, ten tests check only ten of them. This page shows how ten pooled tests, all planned in advance, always identify the special sample, why nine tests can never be enough, and which assumptions the method depends on.

Key terms

Group testing

Definition Group testing is the problem of finding the special items in a collection by testing pools, groups of items combined and tested together, instead of testing each item alone. Robert Dorfman proposed the idea in 1943 as a way to screen large numbers of blood samples with fewer tests. The puzzle on this page is an ideal case. There are $1{,}000$ samples, numbered $0$ to $999$ , and exactly one of them is special. A test applied to a pool says yes exactly when the pool contains a portion of the special sample. Tests never make mistakes, combining samples does not change what a test detects, and each sample can be divided into portions that go into several pools. Under these assumptions ten tests always suffice, and all ten pools can be chosen before any result is known. Write each sample’s number in binary with ten digits, and put a portion of the sample into test $k$ when its $k$ th digit from the left is $1$ . The ten answers, with yes read as $1$ and no as $0$ , spell the special sample’s number in binary. Nine tests are never enough, even if each test is chosen after seeing the earlier answers, because nine answers form at most $2^9 = 512$ different patterns, fewer than the $1{,}000$ samples. If two samples could be special, if a test could give a wrong answer, or if mixing could hide the special sample, this design can point to the wrong sample. The puzzle is a model of information, not a description of how real laboratory tests behave.

In plain words Each test asks one yes-or-no question about the special sample’s number, namely whether a particular binary digit of it is $1$ . Ten answers give all ten digits, and the digits give the number.

Example Take the small version with eight samples, numbered $0$ to $7$ , and three tests. The three-digit binary numbers $000$ to $111$ name the eight samples, and each test pools the samples that have a $1$ in one place.

Test	Place value	Samples in the pool
first	4	4, 5, 6, 7
second	2	2, 3, 6, 7
third	1	1, 3, 5, 7

If sample 5 is special, the answers are yes, no, yes, which read as $101$ , and $4 + 1 = 5$ names sample 5 even though it was never tested alone. Sample 0 is in no pool, so the answers no, no, no point to it. That works only because exactly one sample is special. If the collection might hold no special sample, the answers no, no, no would have two explanations. With 1,000 samples one fix is to number them $1$ to $1{,}000$ , so that every code contains a $1$ and the all-no pattern can only mean that none is special. Ten tests still suffice, since the $1{,}001$ cases fit into $1{,}024$ patterns.

Pooled samples

Definition A pooled sample, or pool, is a mixture of portions taken from several samples and tested as one. In the ideal model of this puzzle a pool tests positive exactly when at least one of its samples is special. A single test therefore answers a question about every sample in the pool at once, but a positive result does not say which sample in the pool is special, or how many are. Pools may overlap, because a sample divided into portions can contribute to several pools.

In plain words A negative pool clears every sample in it with one test. A positive pool only says that something special is somewhere inside, so the pools have to be designed so that their answers together single out one sample.

Example Tested one at a time, ten samples use up all ten tests, and if every answer is no, $990$ candidates remain. In the binary design the first test pools the $488$ samples numbered $512$ to $999$ , the ones whose first binary digit is $1$ , so a single answer settles whether the special sample is among those $488$ or among the other $512$ . Each sample goes into one pool for each $1$ in its binary number. Sample $0$ goes into no pool, and sample $999$ , written $1111100111$ , is divided into eight portions. No sample from $0$ to $999$ needs more than nine.

Binary encoding

Definition Binary encoding writes each whole number in base $2$ , using only the digits $0$ and $1$ . Every whole number $n$ with $0 \le n < 2^k$ can be written in exactly one way as

\begin{aligned} n &= b_{k-1} 2^{k-1} + \dots \\[0.4em] &\quad + b_1 \cdot 2 + b_0, \end{aligned}

where each digit $b_i$ is $0$ or $1$ . The string $b_{k-1} \dots b_1 b_0$ is the $k$ -digit binary numeral of $n$ , with leading zeros when needed. Different numbers get different strings, so the $k$ digits work as an address. To decode a string, add the place values $2^i$ of the digits that are $1$ . In the puzzle every sample has a ten-digit code. Test 1 reads the digit with place value $512$ , test 2 the digit with place value $256$ , and so on down to test 10, which reads the digit with place value $1$ .

In plain words Binary writes a number as a sum of different powers of two, such as $13 = 8 + 4 + 1$ , and records with a $1$ or a $0$ whether each power is used. Reading the digits back and adding the powers marked $1$ recovers the number.

Example The number $613$ splits into powers of two as

\begin{aligned} 613 &= 512 + 64 + 32 \\[0.4em] &\quad + 4 + 1, \end{aligned}

so its ten-digit code is $1001100101$ , with ones in the places worth $512$ , $64$ , $32$ , $4$ and $1$ . If sample $613$ is special, tests 1, 4, 5, 8 and 10 say yes and the other five say no. Adding the place values of the five yes answers gives back $613$ .

Bit

Definition A bit, short for binary digit, is a single symbol that is $0$ or $1$ , the natural record of one yes-or-no answer. A string of $k$ bits has $2^k$ possible values, since each added bit doubles the count. Hence $k$ yes-or-no answers can tell apart at most $2^k$ cases. This holds even when each question is chosen after seeing the earlier answers, because a tree of $k$ yes-or-no questions has at most $2^k$ leaves. In information theory the bit is also a unit of information, and singling out one of $N$ equally likely possibilities takes $\log_2 N$ bits, where $\log_2 N$ is the exponent $e$ with $2^e = N$ .

In plain words Every yes-or-no answer can at most double the number of cases you can tell apart. Ten answers allow $1{,}024$ patterns, enough for $1{,}000$ samples, while nine allow only $512$ .

Example The two powers of two around $1{,}000$ are

\begin{gathered} 2^9 = 512 < 1{,}000, \\[0.4em] 2^{10} = 1{,}024 \ge 1{,}000, \end{gathered}

so ten tests are the fewest that can work, and the binary design reaches that limit. In bits, one of $1{,}000$ equally likely samples takes $\log_2 1000 \approx 9.97$ bits to single out, just under ten. The design leaves $1{,}024 - 1{,}000 = 24$ patterns unused, the codes of the numbers $1{,}000$ to $1{,}023$ . Under the assumptions none of them can occur, so seeing one shows that something went wrong. Such checks catch only some errors. If sample $999$ , with code $1111100111$ , is special and test 6 wrongly says yes, the pattern $1111110111$ is the code of $1{,}015$ , which is unused, so the error is noticed. If sample $5$ , with code $0000000101$ , is special and test 9 wrongly says yes, the pattern $0000000111$ is the code of sample $7$ , and the error goes unnoticed.

Check yourself

Which tests say yes when sample 100 is special? If tests 2, 3, 7 and 10 say yes and the other six say no, which sample is special?

Show the answer

The number $100$ splits as $64 + 32 + 4$ , so its ten-digit code is $0001100100$ . The places worth $64$ , $32$ and $4$ are read by tests 4, 5 and 8, so those three tests say yes and the other seven say no.

Tests 2, 3, 7 and 10 read the places worth $256$ , $128$ , $8$ and $1$ , so the pattern $0110001001$ decodes to

256 + 128 + 8 + 1 = 393,

and sample 393 is special.

What is the fewest number of tests that always finds one special sample among 1,024 samples? Among 1,025 samples? How many patterns go unused in each case?

Show the answer

For 1,024 samples, numbered $0$ to $1{,}023$ , ten tests suffice, since $2^{10} = 1{,}024$ gives exactly one ten-digit code per sample. Nine tests give only $512$ patterns, so ten is the fewest. All $1{,}024$ patterns are used, from ten answers of no for sample 0 to ten answers of yes for sample $1{,}023$ , so no impossible pattern is left over to signal that something went wrong.

For 1,025 samples ten tests are too few, because ten answers form only $1{,}024$ patterns and two samples would have to share one. Eleven tests give $2^{11} = 2{,}048$ patterns, which is enough, and

2{,}048 - 1{,}025 = 1{,}023

of them go unused.

Break the promise of exactly one special sample. In the eight-sample design, what do the three tests show if samples 3 and 5 are both special? Could any design with three tests handle every case of one or two special samples among eight?

Show the answer

Sample 3 has code $011$ and is in the second and third pools. Sample 5 has code $101$ and is in the first and third pools. A pool says yes when it contains at least one special sample, so all three tests say yes. The pattern $111$ is the code of sample 7, and the design would wrongly name sample 7, which is not special at all.

No three-test design can handle these cases, whether the tests are planned in advance or chosen one at a time. There are $8$ ways for one sample to be special and

\binom{8}{2} = \frac{8 \cdot 7}{2} = 28

ways for two to be special, $36$ cases in all, while three yes-or-no answers form only $2^3 = 8$ patterns. Some two cases would have to share a pattern.