Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose we have $n$ bottles of water, one of which is poisoned and which we want to identify. A mixture can be made by mixing some number of bottles of water. We have $k$ rabbits, and each day, each of the rabbits can be given a mixture - a rabbit dies if the mixture contains any poison. How many days are necessary to find out which bottle is poisoned?

A similar, but slightly different problem, is discussed here: Logic problem: Identifying poisoned wines out of a sample, minimizing test subjects with constraints

share|improve this question
3  
+1 for the title! –  Brian M. Scott Jan 30 '13 at 23:01
1  
You need to carry out $\lceil \log_{2} n \rceil$ tests to identify a single poisoned bottle. The tests can be planned in advance (e.g., you can prepare the mixtures each day without knowing any of the results from earlier days). With $k$ tests per day, you need $\lceil \frac{1}{k} \lceil \log_2{n} \rceil \rceil = \lceil \log_{2^{k}}{n} \rceil$ days. –  mjqxxxx Jan 30 '13 at 23:25
1  
@mjqxxxx I might be wrong, but I think that your numerical answer is dependent on all the rabbits surviving each day, while your solution assumes that some rabbits may die out. –  Calvin Lin Jan 31 '13 at 0:00
    
@CalvinLin: You're right; I was treating it as if you had $k$ rabbits each day. –  mjqxxxx Jan 31 '13 at 0:05
add comment

2 Answers

up vote 0 down vote accepted

In $d$ days of testing, each rabbit can experience at most $(d+1)$ outcomes: live for all $d$ days, or die on some day from $1$ to $d$. With $k$ rabbits, then, the number of possible outcomes in $d$ days is at most $(d+1)^{k}$. The maximum number of bottles from which a single poison bottle can be identified must also satisfy $$ N(k,d) \le (d+1)^{k}.$$ We will show that this bound is tight, so $N(k,d)=(d+1)^k$ exactly. This is clearly true for $d=0$. The proof for $d\ge 1$ is inductive on $d$. Suppose we have shown that $N(m,d-1)=d^{m}$ for all $m$. Given $(d+1)^k$ bottles and $k$ rabbits, we proceed as follows. For each bitstring of length $k$ that contains $m$ $0$'s, label $d^m$ bottles with that bitstring. The total number of labeled bottles is $$ \sum_{m=0}^{k}{{k}\choose{m}}d^m=\sum_{m=0}^{k}{{k}\choose{m}}d^m1^{k-m}=(d+1)^k. $$ Now feed a mixture to each rabbit, $i$, that includes water from each bottle with a $1$ in the $i$-th place of its bitstring. At the end of the day, the bitstring with $1$'s in the places corresponding to dead rabbits will be exactly the label on the poisoned bottle. If $k-m$ rabbits have died (which will be the case for some $0\le m\le k$), the selected bitstring has $k-m$ $1$'s and $m$ $0$'s; there are $d^m$ bottles with that bitstring, and we have $m$ surviving rabbits and $d-1$ days left to identify the poison bottle from among them. By the inductive hypothesis, this is enough, which completes the proof.

So, with $k$ rabbits and $d$ days, the maximum number of distinguishable bottles is exactly $(d+1)^k$. Inverting this, we see that for the case with $n$ bottles and $k$ rabbits, we need to be allowed $$ D(n,k)=\left\lceil n^{1/k}-1 \right\rceil $$ days to find the poison.

share|improve this answer
add comment

Let the answer be $S(n, k)$. All fractional number of days should be round up (i'm lazy to type the ceiling function.

If $k=1$, then we can only test 1 wine each day, so we need $n-1$ days. Remember that if there's only 1 wine left, it must be the poisoned one. So $S(n, 1) = n-1$.

If $k=2$, then by dividing up the wine into 3 groups of $ \alpha, \beta, n-\alpha - \beta$ on the first day, and testing the first 2 groups against the 2 rabbits. If both survive, poison is in the last group, and it will take $S(n - \alpha - \beta, 2) + 1$ days. Otherwise, poison is in the first 2 groups and it will take $S(\alpha, 1) + 1$ or $S(\beta, 1) + 1$ days. Hence, in order to minimize the number of days, we want to set these values to be all the same. This gives us $S(\alpha, 1) + 1 = \alpha - 1 + 1 = \alpha$, so $\alpha = \beta = S(n - 2\alpha, 1)+1$.

Since $S(1, 2) = 0$ and $S(2, 2) = 1$, so if we have $\alpha = \beta = 1$, then $n - 2\alpha \leq 1$. This shows that $ S(2, 2)=1, S(3, 2) = 1$ by giving 1 rabbit 1 wine each and that $(4, 2) =2$.

Since $S(3, 2)=1$ and $(4, 2) =2$., so if we have $\alpha = \beta = 2$, then $n - 2\alpha \leq 3$. This shows that $S(4, 2) = 2, S(5, 2) = 2, S(6, 2) = 2, S(7, 2) = 2$ by giving 1 rabbit 2 wines each, and that $S(8, 2) = 3$.

The pattern of the highest value of $n$ such that $S(n, 2) = m-1$ is $1, 3, 7, 13, \ldots$, where we're adding $2m$ to each term, so the terms of the series is $1+(m-1)\times m$. Thus, if $1 + (m-2) \times (m-1) < n < 1 + (m-1)\times m$, then $S(n, 2) = m$.

You can continue this procedure with $k=3$ rabbits. Break up the wines into 4 groups of $\alpha, \beta, \gamma, n-\alpha -\beta - \gamma$, and we test the first 3 groups on the 3 rabbits. We want $\alpha = \beta = \gamma = S(n- \alpha - \beta - \gamma, 2)$. Then, $S(n,3) = 1 + \alpha$.

Sadly, I'm not certain how to generalize this.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.