The King is hosting a party. Each of his guests must bring him a bottle of wine, with the guest's name engraved. Exactly one of his guests has poisoned the gift 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 to drink. 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? Hint: The King can invite many more than just $n$ guests.

Solution

How many guests can he invite?

The king can invite at most $2^n$ guests, for the following reason: at the conclusion of the party, each servant has two possible states - alive or dead. One servant has the ability to distinguish between two bottles of wine. Two servants have the ability to uniquely identify one among four bottles of wine. We can continue this process inductively to see that $n$ servants can uniquely identify one among $2^n$ bottles of wine.

What is his strategy?

Take all $m = 2^n$ bottles, and enumerate them arbitrarily, so that we have

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

Additionally enumerate all servants.

$$s_1, s_2, \dots ,s_n$$

For the the $i$th bottle, $b_i$, we take the binary representation of $i$. Let this be $d_1d_2 \dots d_n$, and assign the $j$th servant $s_j$ to the $j$th digit $d_j$.

$$s_j = d_j$$

Have the servants drink according to their assigned numbers, where a 1 denotes "drink" and 0 denotes "do not drink". This way, a specific pattern of death at the end of the party will uniquely identify a bit string and thus a bottle.

Harder: More Poisoned Wines Back to all Riddles