76
$\begingroup$

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)

  • 0
    Who poisoned my wine?2014-05-10

9 Answers 9

30

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.

  • 0
    @QiaochuYuan: Nice solution +1. Have you considered user52393's suggestion? It seems letting only cooks testing neighbouring bits will suffice since the sum of $i$'th through $j$'th bits can be computed from the sum of all neighbouring bits from $i$'th to $j$'th bits. What do you think?2018-03-31
10

Solution with 42 servants (also 41):

This gives a solution, for 2 poisons, using 42 servants, for 2187 (=3^7) wines. Represent the wines using trinary number system. You will get 7 Trits. We need to find out the trits of the two poisons.

    A-B-C-D-E-F-G 

(A) For Trit A, give wines with values 0,1,2 to 3 unique persons respectively. Do similar tests for rest of the Trits. There will be 7*3=21 such tests.

(B) Mix wines with AB values {00,11,22}. Give it to 1 unique person. Do similar tests on all 2-combination of Trits. There will be C(7,2)=21 such tests.

In Step (A), for a given Trit, at the most, 2 persons will die. If only one person dies, that Trit is resolved. Let's say that some Trits (B,C,E) didn't get resolved.

    1-(0|1)-(1|2)-0-(1|2)-0-0 

To link B&C, check if person for BC died in Step(2). If so, BC are {02,11}; else {01,12}.
To link C&E, check if person for CE died in Step(2). If so, CE are {11,22}; else {12,21}.

Total # of tests = 21+21 = 42


Explanation:

The idea is that when comparing Trits (in Step-B), we need to consider only two broad categories. One with only one common value. One with two common values (Not having a common value is impossible). Let's assume that trits A&D did not get resolved.

Follg shows them as having only one common value (0)

    A   D     =====     0   0     1   []     []  2 

Follg shows them as having two common values (0,1).

    A   D     =====     0   0     1   1     []  [] 

Either way, to link them, it is enough to know if at least one of {00,11,22} died. That resolves the values of both the trits.


Note: A solution for 1458 wines, 2 poisons, can be formulated with 41 servants, by using 7 digits (6 Trits + 1 Bit). This trick doesn't add much worth; it might find its use in testing higher number of poisons.

  • 0
    That was so clever! According to Qiaochu Yuan's MathOverflow link, 2187 wines can't be tested with fewer than 42 servants.2017-03-08
3

Solution with 40 servants:

Represent the wines using base-4 number system. You will get 5 digits (for 4^5=1024 wines)

    A-B-C-D-E 

(A) For digit A, give wines with values 0,1,2,3 to four unique persons respectively. Do similar tests for rest of the digits. There will be 5*4=20 such tests.

(B) Mix wines with AB values {00,11,22,33}. Give it to one unique person. Do similar tests on all 2-combination of digits. There will be C(5,2)=10 such tests (blue graph).

(C) Mix wines with AB values {10,21,32,03}. Give it to one unique person. Do similar tests on all 2-combination of digits. There will be C(5,2)=10 such tests (green graph).

enter image description here

In Step (A), for a given digit, at the most, 2 persons will die. If only one person dies that digit is resolved. If 2 persons die, it means it has two values (one for each poison).

Let's say two digits D&E got two values each. To link them up, you need to look if the person in Step(B) and Step(C) died for D&E. That is enough to link up the digits.

Explanation:

Look at the two graphs.

Assume D has values (1,3). Together, they connect with 0,1,2,3 (all possible values of E). This is the best case. No matter which two values of E you choose, you can uniquely connect them with values of D.

Assume D has values (1,2). Together, they connect with 0,1,2. One value of E (=3) remains unconnected. This is the worst case. Still, no matter which two values of E you select, at least one of them remains connected with values of D. That is enough for us.

1

This gives a solution using 60 servants for 1024 wines.Represent the wines using 10-bit binary numbers. Name the bits from A-J. Group the adjacent bits.

    AB--CD--EF--GH--IJ 

What is the value of AB for poisons? Give follg sets of wines to 4 different people.

    AB=00; AB=01; AB=10; AB=11 

If only one of them die, AB is completely resolved! If not, we get partial information. Do similar tests on remaining 4 groups.

    00--0(0|1)--11--(0|1)1--1(0|1) 

Consider CD & GH. If we know if set DG=00 died, we can link them. Since we dont know which test would be required, we run all 4-tests:

    CG=00; CH=00; DG=00; DH=00 

Similarly for GH and JK. If GJ=00 didnt die, the poisons will be:

    00--00--11--01--11     00--01--11--11--10 

Total # of tests/people needed: 5*4 + C(5,2)*4 = 60


PS: If you use groups of 3 (rather than 2), it doesn't improve. If you use groups of 4 or more, it worsens.

0

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.

0

There are two solutions Binary and Dimensional.

The binary solution:

We give each bottle a binary number corresponding to its numerical position in the line of bottles. We need enough columns to accommodate the given number of bottles. For instance, if we have 8 bottles :

0 -> 000

1 -> 001

2 -> 010

3 -> 011

4 -> 100

5 -> 101

6 -> 110

7 -> 111

(Note: the first bottle has position 0)

We can test with three columns. Three doses are made one for each column, taking one drop from each bottle if and only if it has a 1 in that column. For instance, the first sample has drops from bottles 4,5,6 and 7.

Each dose is given to one person. We just note which of them die. If none die, the first bottle has poison. If all die, the eight bottle (number 7, binary) is poisoned. If the first and third die, the sixth bottle (binary 5).

The binary solution results in an uncertain number of deaths, averaging 1.5, or 50%. But it uses the smallest number of tasters.

The Dimensional solution:

In the simplest case, treating the bottles as points in a line, we need 1000 servants and 1 dies.

Making a square, we need 32 rows and 32 columns. Some spaces are empty, it won't matter, since empty spaces have the same effect as unpoisoned bottles.

Each dose has drops from 1 row. 64 persons take the dose, two die, indicating a row and a column, the poison bottle is at the intersection.

Making a cube, we have 10 x 10 x 10 bottles. We make 3 doses with a drop from each square, on the x y and z axis. Again, the poisoned bottle is at the intersection.

The progression should now be clear:

Arrangement: Line

Consists of: Points

Test using : Points

Number used: 1000

Number dead: 1

Arrangement: Square

Consists of: Lines

Test using : Lines

Number used: 32 x 2 = 64

Number dead: 2

Arrangement: Cube

Consists of: Squares

Test using : Squares

Number used: 10 x 3 = 30

Number dead: 3

For any given number of bottles, to arrange in n dimensions we take the nth root and round of to the next higher integer. At 5 dimensions, we use 20 testers and 5 die.

Increasing the dimensions can go on and on.

  • 0
    Chris, Consider 2-dimensional solution with 2-poisons. Each point is a single wine; each line/row stands for a mixture of those wines. You are testing rows/columns. If you found that 4 persons died *(row=1, row=2, col=1, col=2)*, you don't know which diogonal has the two-poisons : *[(1,1),(2,2)]* OR *[(1,2),(2,1)]*. In 2-dimensions, you have 2-diagonals that you need to resolve. In general (dims,diagonals) grow as (1,0),(2,2),(3,4),(4,8), ..($n$,$2^{n-1}$).2016-09-02
0

Look at Identifying 2 poisoned wines out of 2^n wines for a easier, guided explanation on how it can be solved using $6n$ tests given $2^n$ wines.

0

I wrote a code that searches for such an arragement with less than 40 servants. I randomized 1000 groups of 12 servants, representing the servants that drink each bottle. Afterwords, I found two couples of wine bottles that have the same union of servants who drink them. I rerandomized the servants that drink each of the four(or three) bottles in the unions.

That approach found a solution for as much as 36 servants.

  • 0
    Could please write out the detailed proof of your solution?2018-03-29
0

I have a solution that uses just 28 slaves. The idea is to use a 28x1000 2-separable testing matrix $M$, where $M_{ij}$ is 1 if slave $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

When I find some free time, I plan to write a short report describing the method I used to find $M$.

Dmitry Kamenetsky

  • 0
    Hi Hans. The proof is in the matrix that I provided. If you take the boolean OR of any of its two columns then you will find that it is unique. This means that we can use this matrix to identify the location of any two poisoned bottles out of 1000.2018-03-30