13
$\begingroup$

You are an assistant to the king, who has scheduled a party tomorrow. There are 1000 wine bottles in the king's possession, and unfortunately, 3 of them are poisonous. Consuming from any of these bottles will result in death the following day.

Your task is to identify the 3 poisonous bottles by tomorrow morning to ensure the safety of all the guests.

Possible Solution:
You have the option to use prisoners to help you in this endeavor. One possible approach is to assign each of the 1000 prisoners to drink from a different bottle. By observing the 3 prisoners who die the next day, you can determine which bottles are poisonous.

Objective:
However, your challenge is to find a solution that uses the fewest number of prisoners possible to achieve this objective.

$\endgroup$
6
  • $\begingroup$ With only one bottle poisoned $\endgroup$
    – bobble
    Commented Mar 9 at 15:19
  • 2
    $\begingroup$ For even 2 poisoned bottles I think the optimal number is not known: math.stackexchange.com/q/639/346149 $\endgroup$
    – tehtmi
    Commented Mar 11 at 6:40
  • 8
    $\begingroup$ Interesting that we are not interested in minimizing the number of prisoners that we kill but the number of prisoners to whom we give some wine. $\endgroup$
    – Evargalo
    Commented Mar 11 at 14:11
  • $\begingroup$ @Evargalo that would be 2 if we are lucky, 3 otherwise. If you had two evenings, it would be more interesting. $\endgroup$
    – Lot
    Commented Mar 11 at 14:13
  • $\begingroup$ @Lot My solution (and several others) give samples from the same wine to many prisoners, so many prisoners will die. In my 108-prisoner solution, up to 27 prisoners can die, and at least 9 will definitely die. In my 105-prisoner solution, up to 36 prisoners can die. $\endgroup$
    – isaacg
    Commented Mar 11 at 16:46

7 Answers 7

12
$\begingroup$

Part 3: I can improve my part 2 solution to use

103 prisoners.

I do this by changing

My list of moduluses to [3, 5, 7, 8, 11, 13, 17, 19, 23]. While these moduluses only multiply to 892371480, which is less than $10^9$, an exhaustive search of all 3281 partitions of the nine moduluses into three sets verifies that every partition has at least one subset with product at least 1001. The partition [[3, 17, 19], [5, 8, 23], [7, 11, 13]] is the most balanced of all of the partitions, with products [969, 920, 1001].

Thus, by the same argument as in part 1 below,

If a wine fails all of its tests, it must be a poisoned wine. If it wasn't poisoned, it would have to match one of the poisoned wines modulo a number which is at least 1001, so it is poisoned.

My solution

Would require 106 tests if all moduluses were tested naively, but by incorporating the "23 in 20 tests" refinement described below in part 2, we can get that down to 103 tests.


Part 2: The part 1 solution can be improved to

105 prisoners,

using a suggestion by @tehtmi in the comments and using @AxiomaticSystem's solution as a building block.

As tehtmi pointed out, if we can find a better way to test the moduluses, then we can improve the solution. A modulus-testing problem is almost the same as the original problem, with a number of wines equal to the modulus. If we had a solution to the k-wine problem that used less than k tests, we could also do the modulo-k portion of my answer in less than k tests. Wherever the k-wine solution would test the jth wine, we'll test all wines equal to j modulo k. The only caveat is that the solution needs to work for 1, 2, or 3 poisoned wines. This is fine, because all solutions posted so far satisfy that requirement.

Now, let's incorporate @AxiomaticSystem's solution.

Using the "row, column, wrapping diagonal, wrapping antidiagonal" testing system on a 5x5 grid, we can test 25 wines using only 20 tests. In particular, we can test all of the possibilities mod 23 using only 20 tests. This saves 3 tests relative to my solution above, using the same set of moduluses.


Part 1: I have a solution which uses

108 prisoners.

My solution is a specific implementation of the "Chinese remainder sieve", described by David Eppstein, Michael T. Goodrich, and Daniel S. Hirschberg in "Improved combinatorial group testing algorithms for real-world problem sizes", SIAM Journal on Computing 36.5 (2007): 1360-1375.

The first 4 prisoners test every wine whose index is 0 mod 4, 1 mod 4, 2 mod 4, and 3 mod 4. The next 5 prisoners test each of the mod 5 possibilities. Test each possibility for each of the moduluses [4, 5, 7, 9, 11, 13, 17, 19, 23]. Among these tests, there will be exactly 3 wines for which every test the wine was included in turned up poisonous. These are the poisonous wines.
Note that the sum of these moduluses is 108.

Why does this work?

For a given wine i, suppose all of its tests turn up poisonous. I will prove that wine i must be poisonous. Let j, k, l be the poisonous wines. If i isn't poisonous, then for each modulus, at least one of j, k, and l must match i. But note that the product of the moduluses is $1338557220 > 10^9$. As a result, one of j, k, or l must match i on a subset of the moduluses with product at least 1000. But if two numbers match on a set of relatively prime moduluses, then by the Chinese remainder theorem, they match modulo the product of those moduluses. And all of my moduluses are relatively prime. So i matches one of j, k, or l modulo a number which is at least 1000. So i must be one of j, k, or l.

Note that

This solution would work for up to 1103 wines, because the product of my moduluses is $1338557220$, which exceeds $1338273208 = 1102^3$.

$\endgroup$
2
  • 1
    $\begingroup$ Is $n$ tests the best way to test the $n$ remainders mod $n$? It seems like this is just a subproblem, slightly harder in general because there could also be 1 or 2 poisoned items. It's sort of begging the question, but maybe the smaller numbers are more tractable to improve via another method (like computer search) for hopefully some small improvement. $\endgroup$
    – tehtmi
    Commented Mar 11 at 12:23
  • $\begingroup$ @tehtmi That's a good idea - for instance, using Axiomatic's solution on a 5x5 grid would allow 25 (or 23) options to be tested in only 20 tests, which would save 3 tests from this solution. $\endgroup$
    – isaacg
    Commented Mar 11 at 15:42
11
$\begingroup$

I can find the three poisoned bottles using at most

130 prisoners, as follows:

In a similar vein to Bob Bixler's suggestion, arrange the 1000 bottles in a 33×31 rectangle, leaving 23 gaps arranged however you like. To each prisoner, assign either:
- every bottle in a row, [33]
- every bottle in a column, [31]
- every bottle in a diagonal, spanning the short side and wrapping around the long way, [33] or
- every bottle in an antidiagonal, likewise arranged, [33]
until every prisoner has been assigned a different line. In the morning, there will be exactly three bottles that are not contained in any living prisoner's line - those are poisoned.

Why does this work?

Clearly, each of the three poisoned bottles will satisfy that criterion. In order for there to be more, there must be a way to choose a safe bottle, such that three poisoned bottles are sufficient to cover its row, its column, and both diagonals. However, by fixing the diagonals to the length of the shorter side of the rectangle, we ensure that diagonals intersect rows and columns at only one bottle - the safe one. Additionally, by making the rectangle's dimensions both odd, we ensure that any two diagonals meet at at most one bottle - the safe one. Thus, since no poisoned bottle can cover two directions at once, at least four poisoned bottles are required to make their identities ambiguous.

$\endgroup$
7
$\begingroup$

The lower bound of necessary prisoners I have found is:

28 prisoners

because

There are 1000C3 = 166,167,000 ways to poison 3 cups out of 100 cups. We need to assign each of different case of cups being poisoned to a unique combinations of prisoners dying. A prisoner can either die or not die, so n prisoners can represent 2^n different combinations of poisoned cups. We can find n = 28 to be the minimum n such that 2^n > 1000C3.

$\endgroup$
4
  • 6
    $\begingroup$ That's a minimum, but is it achievable? It's not obvious how to construct a list of assignments that maximizes efficiency. $\endgroup$
    – Ed Murphy
    Commented Mar 9 at 15:30
  • 1
    $\begingroup$ hmmm, good point. I've edited my answer to say lower bound instead. $\endgroup$ Commented Mar 11 at 4:02
  • $\begingroup$ By general principles, it is always achievable. It may be very convoluted, but it can always be achieved. $\endgroup$ Commented Mar 11 at 19:49
  • 3
    $\begingroup$ @PaulSinclair By your logic, shouldn't there be a (convoluted) way to solve it for 4 bottles, using 2 prisoners? $\endgroup$ Commented Mar 11 at 22:32
4
$\begingroup$

Although perhaps not optimal I can think of 2 ways to do this. They are 2D and 3D array testing. The 2D would have a 32x32 array with the 1,024 cells containing the 1,000 bottles (leaving 24 blank cells). Each of the 32 rows and 32 columns would be assigned to 1 prisoner (so a total of 64 prisoners). Each prisoner would sample a container consisting of a blend of all the 32 bottles assigned to him in his row or column. If one or more of the 32 bottles in each row or column contains poison then that prisoner assigned to that row or column would die and that row or column would be marked. The intersections of the marked rows and columns would indicate a poisoned bottle if there are either 3 marked rows or 3 marked columns (with 3 marked rows there would be 1 marked column and vice-versa). In the case with 2 marked rows and 2 marked columns there would be 4 intersections. However you don't know which of the 4 would be a good bottle. So the king may decide to just throw out all 4 which would waste 1 good bottle but each good bottle would have had only 2 samples taken from it.

3D array testing using 30 prisoners would waste 24 bottles at most. This would be modeled by a 10x10x10 cube with 1000 3D cells each containing a bottle. Each prisoner would be assigned a "slice" through the cube consisting of 100 3D cells (so he would sample a blend of 100 3D cells). So with 3 primary faces and 10 prisoners per side that's 30 prisoners.

$\endgroup$
5
  • 2
    $\begingroup$ Your 3D scheme does waste bottles: If it yields 9 dead prisoners, then you have 27 suspicious bottles. So that is 24 wasted $\endgroup$ Commented Mar 10 at 22:13
  • $\begingroup$ @KrisVanBael - 9 dead prisoners will identify three unique points in the 3D space that identify exactly 3 bottles. Each of them will represent a slice, and there will 3 points where those 9 slices intersect, each with a bottle of poisoned wine. No wasted wine! $\endgroup$
    – NoeS
    Commented Mar 11 at 1:40
  • 3
    $\begingroup$ Wouldn’t 3 sets of 3 parallel slices intersect in 27 bottles? If you consider that each prisoner tests one decimal digit of the bottles index, then you wouldn’t know which digits to combine. $\endgroup$ Commented Mar 11 at 6:43
  • 3
    $\begingroup$ And similarly in 2d, the three poinsoned bottles could all be on different rows and different columns, leading to 6 dead prisoners and 9 suspect bottles that you would have to throw away. $\endgroup$ Commented Mar 11 at 9:45
  • 1
    $\begingroup$ @KrisVanBael - Oops. Of course you are right. Note to self - don't post when you're too tired to think carefully. ;) $\endgroup$
    – NoeS
    Commented Mar 11 at 13:32
4
$\begingroup$

I have a solution that uses

74 prisoners.

The idea is similar to isaacg's solution, but in a different setting.

Arrange the bottles in a 10x10x10 cube. Test each value of each of the three coordinates, and for each $k \in \{1, 2, 3, 4\}$, test each value of $x + ky + k^2z$ mod 11. This requires 3 * 10 + 4 * 11 = 74 tests.

This works because

These values are the dot product of the vector $(x, y, z)$ with either a standard basis vector or the vector $(1, k, k^2)$ in $\mathbb{F}_{11}^3$. These seven vectors have the property that any three are linearly independent. The hardest case is when all three are of the form $(1, k, k^2)$, but then these three vectors form a Vandermonde matrix.

If the poison bottles are $i$, $j$, and $k$, and bottle $v$ also fails every test, then each of the 7 dot products must equal the same dot product for either $i$, $j$, or $k$. Thus, one of the poison bottles must match $v$ in three of these dot products. Since the three vectors involved form a basis of $\mathbb{F}_{11}^3$, it follows that $v$ must equal $i$, $j$, or $k$.

$\endgroup$
3
  • $\begingroup$ Nicely done! I think this is much better than is possible with anything more similar to my solution. $\endgroup$
    – isaacg
    Commented Mar 12 at 16:57
  • $\begingroup$ This solution could be improved by using a smaller field, but I have no idea how to generate (or even prove the existence of) a set of vectors with the required properties. $\endgroup$
    – Nitrodon
    Commented Mar 12 at 17:27
  • $\begingroup$ Not the easiest solution to follow, but yes, it seems to work. Definitely one step ahead of all others. $\endgroup$
    – Florian F
    Commented Mar 12 at 20:33
1
$\begingroup$

For completeness, seeing Nitrodon's lower result, an answer similar to AxiomaticSystem:

That needs only 92 prisoners.
observation:
We get the most information from a prisoner (worst case) if it dies half of the time, i.e. tests around 206 bottles.
1000 is just below 4^5, so testing rows column etc. of such a hypercube seems efficient
I did not get this to work.
1000 is also just below 5 * 5 * 6 * 7

lemma 1: We can find from to 34 groups the up to 3 poisoned groups using 23 prisoners.

lemma 1a: We can determine the up to three 'bad batches' from a a total of 30 using 5+6x3 = 23 prisoners. This by testing from the 5x6 rectangle below: all rows, columns, upward diagonals and the number-pattern below.
enter image description here
lemma 1b: We can test an additional 4 'bad batches'.
- The 4 types of group all show at most 3 of the 30 group as poisoned.
- Any three types of group are enough to find 2 poisoned batches, and any 2 enough to find 1 poisoned batch.
So, if
- all column-tasters also taste batch 31
- all row-tasters also taste batch 32
- all diagonal-tasters also taste batch 33
- all pattern-tasters also taste batch 34
We can identify which of 31..34 are poisoned, and then use the remaining group types to identify the rest.

lemma 2: We can determine the up to three 'bad batches' from a rectangle by testing all rows, columns and diagonals, if both dimensions are odd-sized.

Since 1000 < 33x33 we need to test 33 groups 4 times.

Combining lemma 1 with lemma 2, this means only 92 prisoners are needed.

$\endgroup$
2
  • $\begingroup$ You get closest to 1/2 survival chances when testing 206 bottles. $\endgroup$
    – Florian F
    Commented Mar 12 at 20:53
  • $\begingroup$ @FlorianF indeed; corrected. $\endgroup$
    – Retudin
    Commented Mar 12 at 21:40
0
$\begingroup$

So just to try and solve a simpler problem. From spherical-wug-in-a-vacuum's response we see that

The possible number of configurations 1000c3 is between 2^27 and 2^28 meaning a binary representation of all possible states with 27 is impossible.

Thus we have a difficulty, as while it is trivial to translate one bottle in 1000 to a mapping of 10 people, it is harder to figure out how to translate the fractional bits to a concrete mapping of servants.

So to simplify I want an easier to think about example that meets the essential criteria here specifically

(Number of bottles) choose (Number of poison [3 for consistency]) is between 2^(3integer) and 2^(3integer+1).

The simplest would be for between 8 and 16 which 5c3 (10) is between.

So for our smaller example we have 5 bottles, and we want to use 4 servants to represent all the possible states. We should be able to represent 16 states with 4 servants. However, the servant's states are not independent.

We can visualize all possible poison states:

OOXXX OXXXO OXXOX OXOXX XOOXX XOXXO XOXOX XOOXX XXOXO XXOOX

An unfortunate thing falls out of this exercise though, the number of servants and the number of wine bottles are tragically close (off by 1). So we actually can solve it by having each servant drink one and leaving one untouched and if only 2 die the last was poisoned. In the larger cases the remainder will not necessarily be a single bottle. The tricky thing comes when servants are not necessarily independent and could be dying for multiple reasons. For that purpose we would likely need to scale to between 2^6 (64) and 2^7 (128) which would work for 9c3 or 10c3.

Hope my failed experiment can strike inspiration for someone else.

$\endgroup$
2
  • 1
    $\begingroup$ Apparently, it is impossible to reach the information theoretic bound starting with 8 wines I think. 8 choose 3 is 56 which would be bounded by needing 6>lg2(56) prisoners. oeis.org/A290492 lists the supposed optimal values (number of wines that can be tested for n prisoners starting at n=0) up to n=12; 8 is supposedly proven to need 7 prisoners. (I assume Dmitry Kamenetsky verified these small cases using computer analysis.) 12 is the first point at which you gain more than 1 wine from adding an additional prisoners (first non-trivial solution). $\endgroup$
    – tehtmi
    Commented Mar 12 at 0:10
  • $\begingroup$ Dope, love finding a good oeis reference. $\endgroup$ Commented Mar 12 at 14:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.