Find the composite poison in the wine bottles

Question

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 1

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$.

On the second day

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$.

Result

$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$.

20 Prisoners used and 10 survived.

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

Answer 2

A simple solution for 1000 prisoners 998 dead

Number all prisoners and bottles 1-1000, and have each prisoner drink from ALL bottles except their matching number.

The 2 surviving prisoners have the numbers of the poisoned bottles.

** the bottles may be slightly depleted by the 999 prisoners taking a drink

We could also omit the last prisoner and deduce if only one prisoner survives the last bottle is the second poison.

500 prisoners 499 dead Expanding the above technique using 500 prisoners drinking from 998 (so prisoner 1 omits bottles 1 and 2, prisoner 2 omits 3 and 4) we get either 499 dead prisoners and the exact combination or 498 prisoners and a choice of 4 bottles (with the knowledge that its 1 of 1 and 2 and 1 of 3 and 4)

We can then make the surviving prisoners drink 1 of the bottles they didn't drink the first time - if they die they drank the poison if they live they didn't.

2nd extension - 116 prisoners - 114 dead

Take 20 prisoners.

The 1st omits bottles 0-100; the 2nd omits bottles 50-150 etc. (The last prisoner has 950-1000 and 0-50.)

In the worst case 4 will survive giving us 2 gaps of 50 ie 100 bottles to narrow down

Add 96 new prisoners to the surviving 4 and number them 0-100 (and bottles 0-100) ensuring that the 4 "lucky" prisoners are omitting bottles they have previously omitted. The 2 survivors will point to the 2 poisoned bottles.

3rd extension - 86 prisoners 84 dead I used a little javascript function to find the optimum of this method

Same as above 40 prisoners omit 50 bottles each (overlapping the last prisoner by 25).

Worst case leaves 4 alive - and a 50 bottle gap. add the 46 prisoners to allow us to test all 50.

I need to find a better solution for the 2nd day to improve this any further

4th extension - 62 prisoners 60 dead Realised the "worst case" was solvable using the binary expansion so

As above, 40 prisoners omit 50 bottles each (overlapping the last prisoner by 25).

The "worst case" leaves 4 alive - and 2 25 bottle gaps. needing only a further 6(+ the 4) prisoners using the binary method.

If only 2 prisoners survive we have a 25 bottle gap and need to add 22 and deduce the last result to complete.

5th extension 45 prisoners all potentially dead

Thanks to @user2357112 in the comments

Day 1 - use 40 prisoners as above but give each 525 bottles (1st prisoner has 0-525, 2nd 25-550 etc.)

If the poison is in separate groups then in the worst case 20 die (poison is in consecutive groups) this leaves 20 prisoners - more than enough to do the binary method.

If both poisons are in 1 group of 25 then 21 prisoners will have died leaving 19 to test the group with. add in 5 so that we can test all but 1 (and deduce that result as before)

6th extension and bonus removed (they were wrong - thanks @Timbo for helping with my mistake).

Answer 3

Here's a strategy that uses 124 prisoners. It's probably possible to reuse some of the prisoners from day 1 to day 2 to reduce that number, but I want to get a simple strategy posted so other people can build on it and find cleaner ways to present it.

To make the numbers work out a bit nicer, we add 24 bottles of water to the crate, so we're testing 1024 bottles. Group the bottles into 32 groups of 32 bottles each, and label the bottles from 1-1 up to 32-32. Group the prisoners into 4 groups of 31, and label the prisoners from A1 to D31.

On day one, we pour 32 cocktails, each composed of wine from every bottle in a single group, and label the cocktails from 1 to 32. In group A, every prisoner drinks from all cocktails labeled up to and including their number, so for example, prisoner A12 drinks from cocktails 1 through 12. In group B, every prisoner drinks from every cocktail with a label greater than their number, so for example, prisoner B12 drinks from cocktails 13 through 32.

By looking at which prisoners die, we can determine which two cocktails (or which one cocktail) contained poison. If A13 lives and A14 dies, cocktail 14 had poison. If B11 dies and B12 lives, cocktail 12 had poison. If all the A prisoners live, cocktail 32 had poison.

If we find that one cocktail contained poison, we repeat this procedure with the bottles that went into that cocktail instead of with cocktails, and with two fresh sets of prisoners. If we find that two cocktails contained poison, then everyone in group C drinks the first cocktail and a single bottle that went into the second, and everyone in group D drinks the second cocktail and a single bottle that went into the first. Either way, we find the poisoned bottles.

---

Further work: we can reuse at least 31 prisoners, bringing the number we need down to 93. If only one cocktail contains poison, then we have 31 testers who only drank cocktails to the left or right of it, and we can reuse them on the second day. If two cocktails contain poison, then everyone who drank cocktails to the left of "right poison" and everyone who drank cocktails to the right of "left poison" survived. This is at least 32 people. Some of them are contaminated with poison, but we know whether they have left poison, right poison, or neither. We can assign anyone with left poison to the group that would have taken left poison anyway, and similarly for right poison.

Answer 4

For the first part: you need to sacrifice only one prisoner.

Take all combinations of 2 bottles: $\binom{1000} 2$ = 499500. So take 499500 prisoners and give each of them a drop of a different combination of two bottles. Give each prisoner a bracelet with the number of the bottles he drank.

At midnight, one of the prisoners will die and we now know which two bottles were poisoned.

Answer 5

The best answer I've come up with so far tests 35 prisoners in the worst case. It uses a similar setup as previous answers, but instead of separating the 1000 bottles into 4 groups of 250, I separate them into 8 groups of 125. This reduces the number of prisoners needed to 35 from 39 (I'll explain how I calculate this at the end).

Day One
First, we separate the bottles into 8 groups of 125 each. We take 8 prisoners and have them drink from 7 out of the 8 groups (prisoner 1 drinks from all but group 1, etc.) After this (as stated in other answers, but I'll clarify if needed), we're down to two scenarios for day two.

Day Two - Scenario 1
In the first scenario, 2 of our original prisoners have lived. This means that 2 of the 8 groups of bottles each contained one poisoned bottle. We'll label these groups A and B, each with 125 bottles. Now we can set up a simple binary mapping with 7 prisoners per group:

Prisoner 1: 0000001 (1,3,5,7,etc.)
Prisoner 2: 0000010 (2,3,6,7,10,11,etc.)
Prisoner 3: 0000100 (8,9,10,11,12,13,etc.)
...

The figure above shows the "bit" that the prisoner would be assigned, and all of the corresponding bottles he would sample from. You would first set up two groups of 7 prisoners (prisoner A1, A2... B1, B2...). One group would drink every bottle from group A, then apply their binary mapping to group B. The other group of prisoners would do the opposite. After this, you perform a logical OR on the dead prisoners' assigned bits. For example, if prisoners A1, A6, B3, B4 and B7 died, then the bottles that were poisoned were A33 (0100001) and B76 (1001100).

After this, we tested 14 prisoners on day two, and lost 6 prisoners on day one (re-using the two survivors), for a total of 20 prisoners. This is the best case scenario.

Day Two - Scenario 2
In the second scenario, only 1 of our original prisoners has survived. This means that 1 of the 8 groups contains both poisoned bottles. This is far more difficult.

There are two steps to day two. The first step is a simple binary mapping with 7 prisoners, similar to how you would solve the original "poisoned bottle" problem (only one poisoned bottle). Assign each prisoner one of 7 "bits". This is done the same as day one, above. The deaths in these prisoners will tell you which bits of the poisoned bottles are both 1's between the two bottles. For example, say bottles 39 and 97 are poisoned. In binary, these bottles would be:

37: 0100111
97: 1100001

The 1st bit and the 6th bit (from the right) are both shared between these two bottles, which means that prisoner 1 and prisoner 6 will both die, as they are the only two who would have sampled both bottles.

Now that we have the bits that are the same between both bottles, we need the bits that are different. To do this, we take 21 additional prisoners. These prisoners aren't given one "bit" each, but two. Thus prisoner 1 will be mapped to 0000011, and will drink any bottle with a 1 in the first or second bit (1,2,3,5,6,7,9,etc.)

Prisoner 1: 0000011 (1,2,3,5,6,7,9,etc.)
Prisoner 2: 0000101 (1,3,4,5,6,7,9,etc.)
Prisoner 3: 0000110 (2,3,4,6,5,7,9,etc.)
...

There will be many prisoners that die from this batch. First, we need to discount all the prisoners that would have died with a repeating bit (as in step 1). These prisoners would have died regardless of what their second bit was. In our previous example (with bottles 39 and 97), these would be:

Prisoner 1: 0000011
Prisoner 2: 0000101
Prisoner 4: 0001001
Prisoner 7: 0010001
Prisoner 11: 0100001
Prisoner 12: 0100010
Prisoner 13: 0100100
Prisoner 14: 0101000
Prisoner 15: 0110000
Prisoner 16: 1000001
Prisoner 21: 1100000

We know which prisoners these would be because of step one. Since prisoners 1 and 6 died in step one, the 1st and 6th bits are repeats. Any prisoners in step two with these bits are ignored. The remaining dead prisoners from step two are considered. Using our example, the dead prisoners would be:

Prisoner 17: 1000010
Prisoner 18: 1000100

What this says is that one bottle has the 7th bit set and the other bottle has the 2nd bit set (from prisoner 17). We also know that one bottle has the 7th bit set and the other bottle has the 3rd bit set (from prisoner 18). The only combination that makes this true is to have:

Bottle A: 1000000
Bottle B: 0000110

When we combine these with our known repeating bits, we get:

Bottle A: 1100001 (97)
Bottle B: 0100111 (39)

Note that we're performing the tests for step one and step two simultaneously and just noting the results afterwards.

Also note, that I believe step one is necessary. I don't believe you can determine which are the repeating bits using only step two, but I'm still trying to prove my concept.

Summary
In total, we have used 20 prisoners in scenario one (6 dead from day one, 14 more tested on day two). In scenario two, we've used 35 prisoners (7 dead from day one, 7 more tested on day two step one, and 21 more tested for step two).

Note that we know we need 21 prisoners for step two because we're looking at combinations of 2 bits chosen out of 7, which is 7C2 = (7!)/((7-2)!2!). This is how I determined that dividing the original 1000 bottles into 8 groups was ideal. Other possible configurations:

4 groups of 250
First day: 3 dead Second day: 8 + 8C2 = 8 + 28 = 36 Total: 39

8 groups of 125
First day: 7 dead Second day: 7 + 7C2 = 7 + 21 = 28 Total: 35

16 groups of 62/63
First day: 15 dead Second day: 6 + 6C2 = 6 + 15 = 21 Total: 36

Answer 6

Working off of Collett's answer, how about this: First day, split bottles into groups of 250, 4 prisoners drink from the other 750 bottles. We have at most 2 survivors, which indicate the groups of 250 the poisons are in.

Then, we take the remaining 2, 14 unused, and leave 2 alone, and split them into 2 groups of 8. They each drink all 250 of one group (remaining 2 don't do this), then use the original solution on the other group of 250 to figure out the bottles.

Total: 18 prisoners.

Better explanation of 2nd day:
Say the 2 remaining prisoners are the ones that didn't drink 250's (A) and didn't drink 500's (B)
We make a new A' group that's composed of A and 7 others, and they drink all of 500's.
We make a new B' that's composed of B and 7 others and they drink all of 250's.
Since you have 8 slaves in each group $2^8 = 256$ which means you can determine the other poison in each group. So, A' tests all of the 250's, and B' tests all of the 500's.

They do that by doing a bitwise map. Each prisoner is a bit mapping (e.g. 00000100 and 00000010) and each bottle is represented by it's number in binary, and if your bottle matches your mapping, you drink.

EDIT:
So, what happens if you're left with only 1 group of 250 left? Well, you'd be left with 17 prisoners left. Luckily, if you get 2 groups of 8 out of them, you can still figure out the poison. Put the poisons in a 250x250 grid, and do the binary mapping on each axis.

You'll lose at most 19 prisoners here.

The mapping would look like (numbers are bottles, letters are prisoners), in this case, there are 8 bottles, so we need 3 prisoners per axis. Each prisoner drinks the bottles below them or on their row

Prisoners  a   a   a
             b b     b
                 c c c
Bottles  0 1 2 3 4 5 6
       7 x x x x x x x
     d 6 x x x x x x
   e   5 x x x x x
   e d 4 x x x x
 f     3 x x x
 f   d 2 x x
 f e   1 x

EDIT 2:
Bitwise mapping is ideal for finding 1 element out of a set, not 2, in a single trial, so if you have both poisons in 1 group, you'll have to use a brute force method day 2. So, best case 18, worst case, well, much worse.

Answer 7

Combining the answer of @Collett89 and the comments of @user2357112, I get:

45 prisoners used, 33 died

---

The first day

On the first day, have 40 prisoners drink from 525 bottles each, with each prisoner shifting by 25 bottles. In other words, prisoner 0 drinks from 0..524, prisoner 1 drinks from 25..549, etc, with the range wrapping around after 999 (so prisoner 20 drinks from 500..999 and 0..24). There are two cases that result.

The second day, case 1

Most of the time, there will be 2 groups of 25 bottles that are suspect, with poison A in one group and poison B in the other group. Depending on where the two bottles were located, between 2 and 20 prisoners died. So at least 20 prisoners survived and can be reused. To find the two specific bottles requires 10 prisoners. It takes 5 prisoners to find each bottle.

To find the one poison bottle in a group of 25, you have 5 prisoners drink from all of the bottles in the other group (some of the survivors will have already done this). Then each of the 5 prisoners drinks from bottles that have a particular bit is set in the binary representation of the bottle. So, prisoner 0 drinks from bottles where bit 0 is set (1, 3, 5, 7, ... 25). Prisoner 1 drinks from bottles where bit 1 is set (2, 3, 6, 7, 10, 11, ... 23). At the end, the dead prisoners make up the bits of the bottle number. So if prisoners 0, 2, and 3 died, the bottle number would be 01101 or 13. To avoid the worst case of 4 prisoners dying, number the bottles such that the bottles with 4 bits are skipped (i.e. don't use 15, 23, 27, 29, 30, 31). At worst, 3 prisoners die per bottle found.

Final result, case 1: 40 prisoners used, 26 died

The second day, case 2

The other possibility is that both poisoned bottles will be in the same group of 25 bottles. This means 21 prisoners will have died on the first day. Now, we do the same sort of thing as on the first day. We need 24 prisoners, and each will drink from 13 bottles, shifted by one. This will kill between 0 and 12 prisoners.

Final result, case 2: 45 prisoners used, 33 died

---

By the way, I tried with other numbers such as 32 prisoners dividing the bottles into groups of 32. But 40/25 was the best split given that the worst case scenario was to find both poison bottles in the same group.

Answer 8

I think you can do a similar approach as the original problem. This only needs 19 prisoners that could potentially die.

First make mixtures of all wines combined with all other wines. That way you get 1000 x 999 / 2 mixtures is 499,500 mixtures. This number is smaller then 2^19. Only one of these mixtures is lethal! Label these mixtures 1 to 499,500 in binary. Prisoner 1 then takes a sip from all mixtures with a 1 in the first position, prisoner 2 with a 1 in the second position and so on.

Now you can point exactly to which mixture is lethal depending on what prisoners die and point to the poisoned bottles.

For example if prisoner 1,5,10 and 11 die the poisonous mixture is mixture 1000100001100000000

By the way. I only use 1 day here. maybe it can be improved with 2 days. I don't know that

Answer 9

I have an answer that requires only $19$ prisoners in the worst case!

Let's split the bottles into four groups of $250$. We need $4$ prisoners: they're assigned a number from 1 to 4 and everyone drinks all the bottles except the one with his name. After the first midnight, we have these possibilities:

• Three die: It means that the poisoned bottles were both in one fourth of the total, which is $250$ bottles. On the second day, $16$ prisoners are enough to isolate the poisoned bottles using a Bitwise operation, which is a binary map. Since we can recycle the first day survivor and use him for the second day too, we only need $16$ for the second day plus the $3$ first day dead guys, for a total of $19$ prisoners.
• Two die: We have isolated the two bottles inside two groups of $250$ bottles each. For each group we need $8$ prisoners to perform the bitwise strategy and identify the poisoned bottle in that group, which is $16$ prisoners for the second day. Since we can recycle the first day survivors, we globally need $16$ prisoners plus the two dead guys, for a total of $18$ prisoners!

With 20 prisoners, how many bottles can I test?
If the above strategy is optimal, and it's likely to be so, I'd say the maximum number of bottles is $1024$. We split them into $4$ groups of $256$ and we see, using the binary operation, that we'll need no more than $20$ prisoners to detect the poisoned bottles.

What is the bitwise operation I mentioned before?
I will explain it using simple (small) examples, you just need to know that it can be extended to any number of elements.
Suppose that you have $4$ bottles and know that $1$ contains poison. Now, let's say we have two prisoners, $A$ and $B$.
$A$ drinks from bottles $1$ and $3$.
$B$ drinks from bottles $1$ and $2$

We have these options:

• $A$ alive, $B$ dead -> Poison is in $2$
• $A$ alive, $B$ alive -> Poison is in $4$
• $A$ dead, $B$ alive -> Poison is in $3$
• $A$ dead, $B$ dead -> Poison is in $1$

As you can see, we were able to analyze $4$ bottles using $2$ prisoners. Generally, for $n$ bottles you need $log_2\ n$ prisoners (if decimal, round to upper integer).

What if we have two poisons in the same group of bottles?
As before, we can perform a bitwise operation, but this time for $n$ bottles is requires $2log_2\ n$ prisoners.
An example with $4$ bottles (two poisons) and $4$ prisoners is here:

Bottles are named $1,2,3,4$ while prisoners are $A,B,C,D$