Identifying poisoned wines

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

I have a solution that uses just 28 rats. The idea is to use a 28x1000 2-separable testing matrix $M$, where $M_{ij}$ is 1 if rat $i$ drinks bottle $j$ and 0 if he doesn't drink it. A matrix is 2-separable if the boolean OR of any of its two columns is unique. You can read more about such matrices here: https://en.wikipedia.org/wiki/Disjunct_matrix

You can find the actual matrix $M$ here: https://pastebin.com/4yDd1XvG

I plan to write a short report describing the method I used to find $M$.

UPDATE:

A 27x1065 2-separable matrix has been found so it is possible to solve this problem with 27 rats. See https://oeis.org/A054961

Answer 6

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?

Answer 7

How about quaternary/base-4?

For example, $999_{10}=33213_{4}$ denoted by $ABCDE_{4}$

We just need 36 rats, which are $A=0,1,2,3$, $B=0,1,2,3$,

$C=0,1,2,3$, $D=0,1,2,3$, $E=0,1,2,3$

and $(A-B)/4 =0,1,2,3$,$(A-C)/4 =0,1,2,3$,

$(A-D) / 4 =0,1,2,3$,$(A-E) /4 =0,1,2,3$,

For example the wine$12321_{4}$, 9 cats $A=1$,$B=2$,$C=3$,$D=2$,$E=1$,$(A-B)/4 =3$,$(A-C)/4 =2$,$(A-D) / 4 =3$,$(A-E) /4 =0$ drink it.

If we find the cats $A=0,1$,$B=1$,$C=0,2$,$D=0$,$E=1,3$,$(A-B)/4 =0,3$,$(A-C)/4 =0,3$,$(A-D) / 4 =0,1$,$(A-E) /4 =2,3$ are dead,

then we know $01001_{4}$ and $11203_{4}$ are poisoned.

For 10000 wines or more wines, I think we can try to calculate the cases:base-2,base-3,base-4,base-5...to get a not bad solution.