# Logic problem: Identifying poisoned wines out of a sample, minimizing test subjects with constraints

I just got out from my Math and Logic class with my friend. During the lecture, a well-known math/logic puzzle was presented:

The King has $1000$ wines, $1$ of which is poisoned. He needs to identify the poisoned wine as soon as possible, and with the least resources, so he hires the protagonist, a Mathematician. The king offers you his expendable servants to help you test which wine is poisoned.

The poisoned wine is very potent, so much that one molecule of the wine will cause anyone who drinks it to die. However, it is slow-acting. The nature of the slow-acting poison means that there is only time to test one "drink" per servant. (A drink may be a mixture of any number of wines) (Assume that the King needs to know within an hour, and that any poison in the drink takes an hour to show any symptoms)

What is the minimum amount of servants you would need to identify the poisoned wine?

With enough time and reasoning, one can eventually see that this requires at most ten ($10$) servants (in fact, you could test 24 more wines on top of that 1000 before requiring an eleventh servant). The proof/procedure is left to the reader.

My friend and I, however, was not content with resting upon this answer. My friend added the question:

What would be different if there were $2$ wines that were poisoned out of the 1000? What is the new minimum then?

We eventually generalized the problem to this:

Given $N$ bottles of wine ($N \gt 1$) and, of those, $k$ poisoned wines ($0 \lt k \lt N$), what is the optimum method to identify the all of the poisoned wines, and how many servants are required ($s(N,k)$)?

After some mathsing, my friend and I managed to find some (possibly unhelpful) lower and upper bounds:

$log_2 {N \choose k} \le s(N,k) \le N-1$

This is because $log_2 {N \choose k}$ is the minimum number of servants to uniquely identify the $N \choose k$ possible configurations of $k$ poisoned wines in $N$ total wines.

Can anyone help us find an optimum strategy? Besides the trivial one requiring $N-1$ servants. How about a possible approach to start?

Would this problem be any different if you were only required to find a strategy that would for sure find a wine that is not poisoned, instead of identifying all poisoned wines? (other than the slightly trivial solution of $k$ servants)

-
It would be better to change the title of your question to say something about the problem itself. Something like "Math/Logic problem - 1000 cups of wine, one of which is poisoned". This will help people who know the answer look at the question, as well as make it easier to find later. –  Edan Maor Jul 24 '10 at 12:24
@workmad3: Number the wines from 0 to 999 and number the servants from 1 to 10. Feed servant k all the wines with a 1 in the kth binary position of their number. Wait an hour. If D is the set of dead servants, the number of the poisoned wine is $\sum_{i \in D} 2^{i-1}$. –  Simon Nickerson Jul 24 '10 at 13:51
@97832123 could you offer a possible rephrasing that would be more helpful to the community? –  Justin L. Jul 24 '10 at 21:50
@Justin: When someone else starts typing in the same question, the duplicate matcher will display your question title for them. Consider what title would make them most likely to click on it. "Can someone help me with a logic problem" will not do a good job of convincing them their exact question has already been asked. –  Larry Wang Jul 24 '10 at 23:28
@97832123 @Kaestur - I've edited my title; is it more helpful? =) –  Justin L. Jul 24 '10 at 23:31

I asked this question on MathOverflow and got a great answer there.

For $k = 2$ I can do it with ${\lceil \log_2 N \rceil + 2 \choose 2} - 1$ servants. In particular for $N = 1000$ I can do it with $65$ servants. The proof is somewhat long, so I don't want to post it until I've thought about the problem more.

I haven't been able to improve on the above result. Here's how it works. Let $n = \lceil \log_2 N \rceil$. Let me go through the algorithm for $k = 1$ so we're all on the same page. Number the wines and assign each of them the binary expansion of their number, which consists of $n$ bits. Find $n$ servants, and have servant $i$ drink all the wines whose $i^{th}$ bit is $1$. Then the set of servants that die tells you the binary expansion of the poisoned wine.

For $k = 2$ we need to find $n$ butlers, $n$ maids, and ${n \choose 2}$ cooks. The cooks will be named $(i, j)$ for some positive integers $1 \le i < j \le n$. Have butler $i$ drink all the wines whose $i^{th}$ bit is $1$, have maid $i$ drink all the wines whose $i^{th}$ bit is $0$, and have cook $(i, j)$ drink all the wines such that the sum of the $i^{th}$ bit through the $j^{th}$ bit, inclusive, mod 2, is $1$. This is how the casework breaks down for butlers and maids.

• If both butler $i$ and maid $i$ die, then one of the poisoned wines has $i^{th}$ bit $0$ and the other has $i^{th}$ bit $1$.
• If only butler $i$ dies, then both of the poisoned wines have $i^{th}$ bit $1$.
• If only maid $i$ dies, then both of the poisoned wines have $i^{th}$ bit $0$.

The second two cases are great. The problem with case 1 is that if it occurs more than once, there's still ambiguity about which wine has which bit. (The worst scenario is if all the butlers and maids die.) To fix the issue with case 1, we use the cooks.

Let $i_1 < ... < i_m$ be the set of bits where case 1 occurs. We'll say that the poisoned wine whose $(i_1)^{th}$ bit is $1$ is wine A, and the other one is wine B. Notice that the sum of the $(i_1)^{th}$ through $(i_2)^{th}$ bits of wine A mod 2 is the same as the sum of the $(i_1)^{th}$ through $(i_2)^{th}$ bits of wine B mod 2, and we can determine what this sum is by looking at whether cook $(i_1, i_2)$ died. The value of this sum determines whether the $(i_2)^{th}$ bit of wine A is 1 or 0 (and the same for wine B). Similarly, looking at whether cook $(i_j, i_{j+1})$ died tells us the remaining bits of wine A, hence of wine B.

One last comment for now. The lower bound is not best possible when $k$ is large compared to $N$; for example, when $k = N-1$ it takes $N-1$ servants. The reason is that any servant who drinks more than one wine automatically dies, hence gives you no information.

-
By the way, I don't know how I feel about this phrase "the astute mathematics student." It seems kind of demeaning. –  Qiaochu Yuan Jul 29 '10 at 3:50
@Qiaochu - fixed :) i await your solution; a rather large group of my friends are about to give up and go with brute-force using a computer programmer. –  Justin L. Jul 29 '10 at 5:15
Some thoughts. If you want to approach the lower bound, you need to be very careful about how many wines each servant drinks. For fixed N and k there is an optimum number of wines which gets you as close to 1 bit of information as possible, but I have no idea how I would decide what sets of wines to drink other than randomly. The probabilistic method might be capable of showing that a strategy which is close to optimal exists with positive probability, but I don't know much about these matters. –  Qiaochu Yuan Aug 1 '10 at 5:33
Some more thoughts. The above strategy generalizes to a strategy which requires kn + k {n \choose 2} servants, where n = log_k N, but I can't actually prove that it works yet... –  Qiaochu Yuan Aug 3 '10 at 0:26
This is the best answer I'm probably going to get, and I concluded that this question/puzzle is not one that will be solvable any cleaner than this. Thanks for all your help –  Justin L. Sep 7 '10 at 20:25

Technically, a molecule of wine can't contain a molecule of poison, but I'm splitting hairs. I know what you mean.

I consider this problem impossible to solve because of the time constraints. Any time taken to find the correct bottle is taken away from the time necessary for the poison to kill the servant.

If one's objective were to protect the king, it could be done with a single servant. Simply give wine to the servant an hour before the king is ready for his. If the servant dies, pick another bottle. It could take up to 999 tries to find the right bottle, but the king would be safe, and only one servant's life is put at risk.

I don't know about you, but it would probably take me the whole hour to number a thousand bottles. Mixing wines would seem equally time consuming.

-