Logic problem: Identifying poisoned wines out of a sample, minimizing test subjects with constraints
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.
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.
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).
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.