A variation of the poisoned bottle problem

Question

Old story.

The King has received X=950 bottles of wine, exactly one of which is poisoned enough to kill a man exactly 24 hours after ingestion. The King wants to feed some N prisoners some mix of the bottles of wine and figure out conclusively in exactly 24 hours the identity of the poisoned bottle.

• What is the minimum value of N that is needed?
• For that value of N, find the algorithm that minimizes M the number of prisoners who will die in the worst case (By smart choice you can make M less than N)
• How much higher could X be so that N and M remain the same?

Answer 1

Label the bottles in binary, from 0000000001 to 1110110110 (=950). Use 10 soldiers to represent the ten bits that were needed in the bottle labelling. Let each soldier sip from all the bottles that have a label number with their bit equal to 1. When some soldiers die, they indicate exactly which bits in the number are 1, and the surviving soldiers the bits which are 0. From this you can easily identify the bottle.
With 10 soldiers you can test up to 2^10=1024 bottles assuming you start your numbering at 0000000000. If you must prove there is poison present then you cannot use the zero label and can only test 2^10-1 = 1023 bottles.

To minimise the number of dead soldiers, you need to minimise the number of bits used in the bottle numbers. You could number the first ten using powers of 2, which use only one set bit in binary. The next 10C2 = 45 bottles you can label using numbers that have only two bits set. Then use all the numbers with three bits set, etc.

bits  #labels  Total
0     1        1
1     10       11
2     45       56
3     120      176
4     210      386
5     252      638
6     210      848
7     120      968
8     45       1013
9     10       1023
10    1        1024

To get to 950, you will need some numbers that use 7 bits, so in the worst case with 10 soldiers, 7 of them will die. You can test up to 968 bottles with the same worst case (or 967 if you need to prove poison is present).

Answer 2

Firstly i find N as number of binary numbers for 950-1; N=10;

Now distribution for lowest M:
First bottle - no one = 0000000000
Second - one person - 1000000000
Third - one person - 0100000000
…
11th - one person - 0000000001
12th - two ppl - 1100000000
13th - two ppl - 1010000000
...
and every possible combination for lowest number of ppl. So i wont use for example 0111111111, but will use better 1111000000. M = max number of '1's in those combinations = 7 Higher N = lower M. X could be.... 1024-45-10-1=968? (combinations of '0's in '1's like:
0111111111
1011111111
...

Or longer: X=1+10+45+120+210+252+210+120=968

Answer 3

This is just to complete the answer by saying why with the minimal $N$ namely $N = 10$, we cannot improve on $M=7$ prisoners (i.e., $M=6$ prisoners is not achievable).

Whatever mix of bottles we feed to the prisoners, the "information" we get at the end of the experiment period is precisely a list of prisoners who died: some subset of the set of prisoners. If we had $N$ prisoners and up to $M$ of them could have died, this information is one of (up to) $$\binom{N}{0} + \binom{N}{1} + \dots + \binom{N}{M}$$ possibilities. We cannot use this information to distinguish among $X$ possibilities if $X$ is greater than this number, so we need $$ X \le \binom{N}{0} + \binom{N}{1} + \dots + \binom{N}{M} \quad (\le 2^N)$$ With $X = 950$ from $X \le 2^N$ we get $N \ge 10$, and with $N = 10$ the above inequality gives $M \ge 7$.

In other words, if at most $6$ of the $10$ prisoners die, then the information we get is one of $1 + 10 + 45 + 120 + 210 + 252 + 210 = 848$ sets, which is not enough for telling apart $950$ bottles. (Though you could go up to $11$ prisoners and have at most $5$ die, or use $13$ prisoners and have at most $4$ die, or use $18$ prisoners and have at most $3$ die, or $44$ prisoners and have at most $2$ die, or of course $949$ prisoners and have at most $1$ die.)