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

Back to all Riddles