Fewest number of prisoners needed

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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.

Answer 6

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.

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.

Answer 7

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.