# Identifying poisoned wines

The standard version of this puzzle is as follows: you have $1000$ bottles of wine, one of which is poisoned. You also have a supply of rats (say). You want to determine which bottle is the poisoned one by feeding the wines to the rats. The poisoned wine takes exactly one hour to work and is undetectable before then. How many rats are necessary to find the poisoned bottle in one hour?

It is not hard to see that the answer is $10$. Way back when math.SE first started, a generalization was considered where more than one bottle of wine is poisoned. The strategy that works for the standard version fails for this version, and I could only find a solution for the case of $2$ poisoned bottles that requires $65$ rats. Asymptotically my solution requires $O(\log^2 N)$ rats to detect $2$ poisoned bottles out of $N$ bottles.

Can anyone do better asymptotically and/or prove that their answer is optimal and/or find a solution that works for more poisoned bottles? The number of poisoned bottles, I guess, should be kept constant while the total number of bottles is allowed to become large for asymptotic estimates.

-
From the viewpoint of a rat, any bottle of wine sounds like alcohol poisoning. – KConrad Mar 29 '11 at 4:26
I don't know how to do the problem, but I can't help feeling it's equivalent to finding a 2-error-correcting binary code of minimal dimension given ... something-or-other. I'm pretty sure the solution to the 1-bottle problem can be expressed in terms of the Hamming codes, and if you do that then maybe what I'm saying about 2-error-correcting codes will become clear. – Gerry Myerson Mar 29 '11 at 5:12
@Thomas: sure. After an hour, the only information you have if you used $m$ rats is the information about which rats are dead or alive, so you can only get $m$ bits of information this way. So $\lceil \log N \rceil$ is optimal for one bottle. – Qiaochu Yuan Mar 29 '11 at 5:47
@Roland You have only one hour to perform the test so you cannot wait to see which rats survive to reuse them. Otherwise, it would be easy: one would simply administrate the different wines successively to a single rat until it dies. – Anthony Leverrier Mar 29 '11 at 9:58
Isn't this what postdocs are for? – Mariano Suárez-Alvarez Jun 8 '11 at 4:23

Each bottle of wine corresponds to the set of rats who tasted it. Let $\mathcal{F}$ be the family of the resulting sets. If bottles corresponding to sets $A$ and $B$ are poisoned then $A \cup B$ is the set of dead rats. Therefore we can identify the poisoned bottles as long as for all $A,B,C,D \in \mathcal{F}$ such that $A \cup B = C \cup D$ we have $\{ A, B \} = \{ C, D \}$. Families with this property are called (strongly) union-free and the maximum possible size $f(n)$ of a union free family $\mathcal{F} \subset 2^{ [n] }$ has been studied in extremal combinatorics. In the question context, $f(n)$ is the maximum number of bottles of wine which can be tested by $n$ rats.

In the paper "Union-free Hypergraphs and Probability Theory" Frankl and Furedi show that $$2^{(n-3)/4} \leq f(n) \leq 2^{(n+1)/2}.$$ The proof of the lower bound is algebraic, constructive, and, I think, very elegant. In particular, one can find $2$ poisoned bottles out of $1000$ with $43$ rats.

-
+1: very nice, now the rats have no chance ;-) – Suvrit Apr 1 '11 at 21:49
Perhaps oddly, I find myself caring more about the abstract formulation than about the puzzle formulation. Will have to look at the FF paper when I find time! – Yemon Choi Apr 1 '11 at 23:03
Many thanks! This question has been bothering me for quite some time. – Qiaochu Yuan Apr 2 '11 at 1:56

This problem also goes by the name "nonadaptive combinatorial group testing" and has been around since at least World War II, when the U.S. government was trying to isolate syphilis cases in soldiers. ("Nonadaptive" means you have to specify all the tests in advance, whereas "adaptive" means you can use the results from previous tests before deciding which ones to do next.)

The standard reference on group testing appears to be Combinatorial Group Testing and Its Applications, by Du and Hwang. Part II, which comprises Chapters 7-9, is on nonadaptive testing. In particular, finding optimal testing structures when there are two or more "defectives" is still an open problem.

However, if $t(d,n)$ is the number of tests required to isolate $d$ defectives out of $n$ total subjects, the bounds $\Omega(\frac{d^2}{\log d} \log n) \leq t(d,n) \leq O(d^2 \log n)$ are known. The Wikipedia article on disjunct matrices has a discussion and some proofs.

It might be interesting to compare the solution for the adaptive version of this problem, as we can give a definite answer in this case.

Let $n(t)$ denote the maximum number of bottles of wine for which 2 poisoned ones can be identified in $t$ adaptive tests. In "Group testing with two and three defectives" (Annals of the New York Academy of Sciences 576, pp. 86-96, 1989) Chang, Hwang, and Weng give explicit testing procedures that yield the lower bounds $$n(t) \geq 89 \cdot 2^{\frac{t}{2}-6}, t \text{ even, } t \geq 12;$$ $$n(t) \geq 63 \cdot 2^{\frac{t-1}{2}-5}, t \text{ odd, } t \geq 13.$$

In the Du and Hwang text it is shown that, for $t \geq 4$, we have the upper bound $$n(t) \leq 2^{\frac{t+1}{2}} - 1/2.$$
(Note that this is the upper bound on $f(n)$ given in Sergey Norin's answer.)

These bounds tell us that $n(18) \leq 723$ but that $n(19) \geq 1008$. Thus 2 poisoned bottles can be identified out of 1000 in 19 adaptive tests but no fewer, using the testing procedure described in the Chang, Hwang, and Weng paper.

-

You yourself give the solution in the link: the probabilistic method. Without trying to optimize, take $r$ rats and for each one choose the subset of wines randomly, each wine with probability $1/2$ (say). Call these subsets $A_m$. Now let $\{i,j\}$ and $\{k,l\}$ be two possibilities for which bottles are poisoned. We want to know whether there's a rat separating these two possibilities, that is, that the outcome if the $i$-th and $j$-th bottles are the poisoned one will be different for that rat, then if the $k$-th and $l$-th bottles are poisoned. For any specific rat, this happens if $A_m$ intersects $\{i,j\}$ but not $\{k,l\}$ or vice verse. This happens with some fixed positive probability (again, not optimizing). Therefore, it fails with probability $q$ which is strictly less than 1. Hence, the probability for it to fail for all $\{A_m\}_{m=1}^r$ is $q^r$. There are less than $n^4$ pairs of possibilities for poisoned wine bottles, hence the probability of having some pair for which this fails is at most $n^4 q^r$ and taking $r=C \log n$ suffices to make this negligible.

-
I guess the problem is not to find a solution that works on average but one working in the worst case. – Anthony Leverrier Mar 29 '11 at 7:09
This works in the worst case. With high probability, if you have $r=1000 \log n$ rats and choose the subsets of wine bottles randomly each with probability $1/2$ you get a solution which work in the worst case (i.e. no matter which pair of bottles are poisoned). – Ori Gurel-Gurevich Mar 29 '11 at 7:16
I believe that since there are exponentially many choices for the probabilistic experiment, but only polynomially many ways the poison could be picked, there is some single string of random bits that works with $O(\log n)$ rats for all possible arrangements of the bottles. This requires using a concentration bound, such as Chernoff bounds. – Derrick Stolee Mar 29 '11 at 13:25
If I'm not mistaken, the optimal choice here is probability 1/3, leading to $r\sim\frac{3\log n}{\log(27/19)}$. For $n=1000$, this gives $r=59$. – Emil Jeřábek Mar 29 '11 at 13:27
@Zander: It's possible my argument is flawed, but I don't think so. The random variables $\{A_m\}_{m=1}^r$ are, by definition, independent, so the events are also independent. The events aren't independent for different $i,j,k,l$, but for that part I use union bound. (a general remark, I suggest using a less determined tone in your comments, such as "I think there is a flaw in the argument" or even "I don't understand this part, can you explain it", see the beginning of this comment. – Ori Gurel-Gurevich Mar 30 '11 at 5:19

There's a very similar problem in compressed sensing genetic screening for rare alleles (cf http://nar.oxfordjournals.org/content/38/19/e179.full ). The technique almost works here provided we can determine how much poison a rat gets. Seems reasonable, a rat that gets more poison dies faster.

In our problem the idea would be to create a sample for each rat to drink by randomly pooling together wine from many bottles. Specifically, for rat $i$ we draw $A_{ij}$ liters of wine from each of the $j=1,...,N$ bottles where $A_{ij}$ is $\mathcal{N}(0,1)$ distributed. Let $b_i$ denote the amount of poison measured in rat $i$ and let $x_j$ denote the amount of poison in bottle $j$.

This yields the highly underdetermined linear system $$A\vec{x} = \vec{b}$$ where we know a priori that $\vec{x}$ is sparse. The sparsest solution to this linear system may obtained in polynomial time by solving the convex optimization $$\min |\vec{x}|_1 \text{ s.t. } A\vec{x}=\vec{b}$$

The number of rats required here is $\mathcal{O}(s \log(N))$ where $s$ is the number of poison bottles.

-

For the case of one poisoned bottle I would expect the answer to be logbase2(N) because we could then have each rat drink from the bottles whose positions' binary digits include the rat's position and the rats that die will be those whose positions give the binary representation of the bad bottle's position.

If that is correct then for two bad bottles I would be inclined to think of doing the same thing with the list of all bottle pairs, but of course there is not just one poisonous pair. In order to identify the unique doubly poisonous pair we need to replace the rats by something that only dies if it gets a double dose. It seems that pairs of rats would suffice for this, but then the total number needed would be 2*logbase2(NC2) which gives only 38 for N=1000, so if your answer is optimal I must have missed something.

Where did I go wrong?

-
Try it for something smaller, like $N=5$, where you can write everything out, and see if your proposed protocol (which you haven't actually given) works. – Gerry Myerson Mar 29 '11 at 6:15
It is not known (by me) that Qiaochu's answer is optimal. Also, an obvious use of pairs of rats only pins down those digits in the encoding that the two bottles share. You need a parallel encoding and additional rats to determine which two bottles are affected, within an hour. I suspect, using three randomly chosen encodings and 60 rats, one has a high probability of success of identifying the two bottles. Now if I only had a proof... . Gerhard "Off To See The Wizard" Paseman, 2011.03.28 – Gerhard Paseman Mar 29 '11 at 6:35
Yes, of course you are right. A pair of rats could die from two single doses, each from a bottle-pair with only one bad bottle. – Alan Cooper Mar 29 '11 at 8:10