  In order to identify the infected individuals of a population, their samples
are divided in equally sized groups called pools and a single laboratory test
is applied to each pool. Individuals whose samples belong to pools that test
negative are declared healthy, while each pool that tests positive is divided
into smaller, equally sized pools which are tested in the next stage. In the
$(k+1)$-th stage all remaining samples are tested. If $p<1-3^{-1/3}$, we
minimize the expected number of tests per individual as a function of the
number $k+1$ of stages, and of the pool sizes in the first $k$ stages. We show
that for each $p\in (0, 1-3^{-1/3})$ the optimal choice is one of four possible
schemes, which are explicitly described. We conjecture that for each $p$, the
optimal choice is one of the two sequences of pool sizes $(3^k\text{ or
}3^{k-1}4,3^{k-1},\dots,3^2,3 )$, with a precise description of the range of
$p$'s where each is optimal. The conjecture is supported by overwhelming
numerical evidence for $p>2^{-51}$. We also show that the cost of the best
among the schemes $(3^k,\dots,3)$ is of order $O\big(p\log(1/p)\big)$,
comparable to the information theoretical lower bound
$p\log_2(1/p)+(1-p)\log_2(1/(1-p))$, the entropy of a Bernoulli$(p)$ random
variable.
