Identifying poisoned wines - MathOverflow

Identifying poisoned wines

2011-03-29T04:18:43Z

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 by Alan Cooper for Identifying poisoned wines

2011-03-29T06:11:58Z

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 by Ori Gurel-Gurevich for Identifying poisoned wines

2011-03-29T06:55:20Z

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 by Sergey Norin for Identifying poisoned wines

2011-04-01T17:29:34Z

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 by rcompton for Identifying poisoned wines

2011-04-02T02:49:24Z

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 by Mike Spivey for Identifying poisoned wines

2011-06-08T04:11:54Z

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 by TonyD for Identifying poisoned wines

2012-12-27T04:20:14Z

I'm kinda confused on how this works. I get log(2) of 1000 ~ 10, but is that only for binary events? Could someone walk me through how out of 1000 bottles, the EXACT poisoned bottle (1/1000) can be found by drinking only 10? Are you breaking up the bottles into groups, and then pouring all of the wine together, effectively poisoning the group? You can only test 1 bottle at a time, so with 10 tests, you will only test 10 bottles right, .1% of the entire group?

Thanks!