Poisoned Wine

Problem. You have $n$ bottles of wine; exactly one is poisoned. A taster who drinks from the poisoned bottle dies after exactly one day (the delay is fixed). You have one day. What is the minimum number of tasters needed to identify the poisoned bottle?

The answer

$\lceil {\log }_{2}n\rceil .$

Binary encoding. Number the bottles $\mathrm{0..}n-1$. Taster $i$ drinks from every bottle whose $i$-th bit is 1. After a day, read the pattern of deaths as a binary number — that is the poisoned bottle’s index.

int tasters = 0;
while ((1 << tasters) < n) tasters++;
// taster i drinks from every bottle b with (b >> i & 1)
// result: index = sum over dead tasters i of (1 << i)

For $n=1000$: 10 tasters. For $n=10^6$: 20.

The lower bound

Each taster produces one bit of information (dead or alive), so $k$ tasters distinguish at most $2^k$ outcomes. To identify one of $n$ bottles, $2^k\ge n$, hence $k\ge {\log }_{2}n$.

This is an information-theoretic bound, and it is tight because the binary encoding achieves it. The same argument gives the $\Omega (n\log n)$ lower bound for comparison sorting, and the $\lceil {\log }_{2}n\rceil$ bound for binary search.

Variants

$d$ poisoned bottles

Now $\left(\genfrac{}{}{0ex}{}{n}{d}\right)$ outcomes must be distinguished, so at least ${\log }_2\left(\genfrac{}{}{0ex}{}{n}{d}\right)$ tasters are needed. Achieving it requires non-adaptive group testing designs (superimposed codes); the construction is much harder than the $d=1$ case, and $O(d^2\log n)$ tasters suffice.

Multiple rounds

With $r$ rounds and $k$ tasters, each taster yields a value in $\{$survives all, dies in round 1, …, dies in round $r\}$ — that is $r+1$ outcomes per taster, so $(r+1{)}^k\ge n$:

$k=\lceil {\log }_{r+1}n\rceil .$

With 2 days and 3 tasters you can handle 27 bottles instead of 8.

Adaptive testing

If you can wait between tests, binary search uses one taster and $\lceil {\log }_{2}n\rceil$ days. The trade-off between tasters and time is exactly $k\cdot \log (\text{outcomes per taster})\ge {\log }_{2}n$.

Limited tastings per taster

If each taster may drink from at most $m$ bottles, the encoding must use low-weight codewords — a combinatorial design problem.

The general principle: information theory as a lower bound

$\text{minimum tests}\ge \frac{{\log }_2(\text{number of possible answers})}{{\log }_2(\text{outcomes per test})}.$

Problem	Outcomes	Bound
Poisoned wine, 1 poison	$n$	${\log }_{2}n$ tasters
Comparison sorting	$n!$	${\log }_2(n!)=\Omega (n\log n)$ comparisons
Binary search	$n$	${\log }_{2}n$ comparisons
Finding a counterfeit coin (balance: 3 outcomes)	$n$	${\log }_{3}n$ weighings
Guessing a number with yes/no	$n$	${\log }_{2}n$
Mastermind	$6^4$	$\ge {\log }_{\text{feedback}}$
20 questions	$2^{20}\approx 10^6$

The counterfeit-coin problem is the classic three-outcome instance: a balance scale gives left, right, or equal, so ${\log }_{3}n$ weighings suffice to find a fake among $n$ coins (and $\lceil {\log }_3(2n+1)\rceil$ if you must also determine whether it is heavy or light).

Why it is worth knowing

Two transferable ideas:

1. Encode the answer in binary and let each test read one bit. This solves a whole family of “minimum number of parallel tests” problems.
2. Count the outcomes to get a lower bound. Whenever a problem asks “what is the minimum number of queries”, the information-theoretic bound is the first thing to compute — and it is very often achievable.

See also: Binary Search · Entropy · Complexity Theory