Medium

Math

Alvin Wan

Nov. 24, 2016

# More Poisoned Wines

The King is hosting a party. Each of his guests must bring him a bottle of wine, with the guest's name engraved. Exactly two of his guests have poisoned their gifts to the King; any human that drinks this poisoned wine will die in exactly half a day. The King has $n$ dispensable servants, each of which is ready to test wine for the King. The party will last half-a-day and the King wishes to identify the traitor by the party's end. He can assign each of his servants 0 or more bottles of wine. Given $n$ servants, how many guests can the King invite and still be able to identify the traitor? What is his strategy for identifying the traitor?

# Solution

## How many guests can he invite?

He can invite up to $2^{\lfloor n/2 \rfloor}$ guests. First, given $k$ servants, we can uniquely identify up to $2^k$ numbers. See Poisoned Wine for an explanation. Second, to identify two numbers $k_1, k_2$, we can construct a system of two equations (for our two unknowns). We will take the sum and difference of $k_1, k_2$ for our two equations.

$$s = k_1 + k_2$$ $$d = k_2 - k_1$$

Note that the sum of two $n$-bit numbers is at most $n+1$ bits, and the difference is at most $n$ bits. If we allocate $\lfloor \frac{n}{2} \rfloor$ servants to represent the difference $d$ and $\lceil \frac{n}{2} \rceil$ to the sum $s$, then $k_1$ and $k_2$ can have a bit representation of at most $\lfloor \frac{n}{2} \rfloor$ bits. The maximum value representable, or the maximum number of guests, is then $2^{\lfloor \frac{n}{2} \rfloor}$.

## What is his strategy?

This has been briefly outlined in our answer to the previous part. Take all $m = 2^{\lfloor \frac{n}{2} \rfloor}$ bottles, and enumerate them arbitrarily, so that we have

$$b_1, b_2, \dots, b_m$$

### Representing Difference

Take the first half of servants $n_d = \lfloor \frac{n}{2} \rfloor$ to represent the difference, and enumerate them.

$$s_1, s_2, \dots ,s_{n_d}$$

Take all possible pairwise combinations of numbers in $\{1, 2, \dots m\}$ - let's call the $i$th combination $c_i$ - and take the bit representation of their difference, $d_i = c_{i1} - c_{i2}$. Let the bit representation of the $i$th difference be $\text{Bit}(d_i) = d_{i1} d_{i2} \dots d_{ in_d }$. Again, assign each digit to a servant and have the servants drink according to their assignments.

$$s_j = d_{ij}$$

Note that many pairs of combinations will have the same bit representation. However, we have yet to procure our second equation.

### Representing Sum

We now take the second half of servants, and enumerate them.

$$s_{ n_d + 1}, s_{ n_d+2 }, \dots, s_n$$

Take all possible pairwise sums, take the bit representation of the sum, and have the servants drink according to their assignments.

$$s_{n_d + j} = d_{ij}$$

### Solving the System

At the end of the party, we note the deaths and recover our unique bit representation of the sum $s$ and the difference $d$. Then, simply solve the system. Without loss of generality, assume $k_2 > k_1$. Take $d = k_2 - k_1 \implies k_2 = d + k_1$.

$$s = k_1 + k_2$$ $$k_1 = s - k_2$$ $$k_1 = s - (d + k_1)$$ $$k_1 = s - d - k_1$$ $$k_1 = \frac{s-d}{2}$$

We can finally plug in to obtain a closed-form solution for $k_2$.

$$k_2 = d + k_1 = d + \frac{s-d}{2} = \frac{s+d}{2}$$

Zijin Cui suggested a more elegant solution on August 12, 2019, now included below. Sounds obvious in retrospect...

A more elegant and naive approach would be to assign every distinct pair of bottles a distinct binary code and whichever binary code of tasters who die will correspond to that pair of wine. With 2^(N/2) people, there are just less than 2^N possible pairs using combinatorics. This solution makes it extendable to any number of bottles being poisonous.

Back to all Riddles

« Back to all posts