You are the ruler of a medieval kingdom who loves throwing parties. The courtier who tried to poison one of your wine bottles last time was furious to learn that you managed to identify which bottle he had poisoned out of 1,000 with just ten prisoners.
This time he's a bit craftier. He's developed a composite poison $P$: a binary liquid that's only deadly when two individually harmless components mix; this is similar to how epoxy works. He's sent you another crate of 1,000 wine bottles. One bottle has component $C_a$ and another one has component $C_b$. ($P = C_a + C_b$)
Anyone who drinks both components will die on the stroke of midnight on the night they drank the final component, regardless of when in the day they imbibed the liquid. Each poison component stays in the body until the second component activates, so if you drink one component one day and another component the next, you will die on midnight at the end of the second day.
You have two days before your next party. What is the minimum number of prisoners you need to use for testing in order to identify which two bottles are tainted, and what algorithm do you need to follow with that number of prisoners?
Bonus
Additionally, suppose that you had a fixed limit of 20 prisoners at your disposal, what's the maximum number of bottles you could theoretically test and come to an accurate conclusion about which bottles were affected?
Note: I don't actually know the answer to this puzzle, but thought it would be interesting to think about how you'd represent that information.
Answer
On the first day
Use 10 groups of 2 prisoner and number them 0.0, 0.1, 1.0, 1.1, 2.0, ..., 8.1, 9.0, 9.1.
Prisoner a.b drinks from bottles with $\left\lfloor\frac{index}{2^a}\right\rfloor\%2=b$. That means every bottle where the ath bit is b.
That gives us some groups where one prisoner survives and some groups where both prisoner survives.
Take a random group m with two survivor.
Prisoner m.0 has drunk exactly one poison and m.1 has drunk the other poison. If that would not be the case one of them would be dead.
Lets call the poison drunk by m.0 $x$ and call the other poison drunk by m.1 $y$.
We define $x_i=\left\lfloor\frac{x}{2^i}\right\rfloor\%2$ and $y_i=\left\lfloor\frac{y}{2^i}\right\rfloor\%2$. That means $x_i$ and $y_i$ are the ith bit of $x$ and $y$
Prisoner a.0 dies if $x_a=0$ and $y_a=0$ and prisoner a.1 dies if $x_a=1$ and $y_a=1$.
That means both survive if $x_a XOR y_a$.
We define $s=\sum_{i=0}^92^i \times \begin{cases} 1 & \text{if both prisoner survive} \\ 0 & \text{if one prisoner survive}\end{cases}$.
Corollary 1: $s = x XOR y$.
Proof: $s=\sum_{i=0}^92^i \times \begin{cases} 1 & \text{if both prisoner survive }\\ 0 & \text{if one prisoner survive} \end{cases}=\sum_{i=0}^9 2^i\times (x_i XOR y_i) = x XOR y$.
All prisoner from a group with two survivor have to drink from the bottles that prisoner m.1 has drunk on the first day. That will kill one prisoner of each group.
Corollary 2: Nobody drinks poison $x$ on the second day.
Proof: Only the stuff of m.1 is drunk on the second day and m.1 has drunk y (by definition) and survived.
There are 4 cases for each group:
If a.0 dies on the first day that means $x_a=0$.
If a.1 dies on the first day that means $x_a=1$.
If a.0 dies on the second day that means he has drunk $x$ on the first day (because of corollary 2). That means $x_a=0$.
If a.1 dies on the second day that means he has drunk $x$ on the first day (because of corollary 2). That means $x_a=1$.
It follows a.1 dies if $x_a=1$.
$x=\sum_{i=0}^9 2^i \times x_a=\sum_{i=0}^9 2^i \times \begin{cases} 1 & \text{if prisoner i.1 died} \\ 0 & \text{if prisoner i.0 died} \end{cases}$.
And with corollary 1: The other poison is $y=x XOR x XOR y = x XOR s$.
That can be improved to 20 Prisoners used and 11 survived by not forcing $m.0$ to drink stuff where we know that it will kill him.
Update: New result is 18 Prisoners used and 8 survived.
The algorithm is the same as above but prisoner 0.0 and 0.1 are not used and instead m.0 and m.1 do their job. Those hadn't created any information on the second day.
In detail:
First day is the same as the result before but leave out prisoner 0.0 and 0.1.
If half of the prisoner die on the first day it is clear where both poisons are (all bits except the last are equal and one bit can be read out of each group)
Else we can find a m where both prisoner of m survive.
On day 2 in all other groups where both survive they drink from the bottles that were drunk from by m.1 (Same as the result before).
m.0 and m.1 will drink from the that 0.1 would drink from.
If m.0 survives then the last bit of y is 0 if he dies the last bit of y is 1.
If m.1 survives then the last bit of x is 0 if he dies the last bit of x is 1.
Example
Example with 16 bottles and poison in 1 and 10:
First day:
1.0: 0011001100110011 --> survive
1.1: 1100110011001100 --> survive
2.0: 0000111100001111 --> survive
2.1: 1111000011110000 --> die
3.0: 0000000011111111 --> survive
3.1: 1111111100000000 --> survive
Now we know all bits where on prisoner died and in each group where both survive we know that the bit is different. In my example the bit 2 is 0 and bits 1 and 3 are different. We have no knowledge about bit 0. The possible answers are: x=000?, y=101? or x=001?, y=100? or x=100?, y=001? or x=101?, y=000?
In pair 1 and 3 both survive and we choose 1 as m. That means that the poison with bit 1 is called x and the other one is y. The possible answers are: x=001?, y=100? or x=101?, y=000?
Second day:
That means the second day there will be the following drinking:
1.0: 0111011101110111 --> die ==> the last bit of y is 1
1.1: 1101110111011101 --> survive ==> the last bit of x is 0
2.0: (doesn't drink)
2.1: (already dead) --> died 1st day ==> bit 2 of x is 0 and bit 2 of y is 0
3.0: 1100110011111111 --> died 2nd day ==> bit 3 of x is 1 and bit 3 of y is 0
3.1: 1111111111001100 --> survive
Result is x = 1010 and y = 0001
Bottle count that can be tested with n prisoner
I experimented with other bases and found an optimum with checking base 3 digits with 3 prisoner instead of base 2 digits with 2 prisoner. That needs $3log_3(n)+O(1)\approx 2.731ln(n)+O(1)$ prisoner instead of $2log_2(n)+O(1)\approx 2.885ln(n)+O(1)$ prisoner. But that doesn't decreases the number of needed prisoner here.
The result is that with $3*n$ prisoner you can test $2*3^n$ bottles,
with $3*n+1$ prisoner you can test $3*3^n$ bottles
and with $3*n+2$ prisoner you can test $4*3^n$ bottles.
That means 17 prisoner can check 972 bottles (a few short for it to be a solution to this question) and 20 prisoner can check 2916 bottles
No comments:
Post a Comment