The Emperor

Let's follow the hint and construct a solution with one poisoned bottle out of eight. We will show that only three slaves are needed to find the poisoned bottle.

First of all label each bottle in binary starting from zero and ending at seven

000... 001... 010.. . 011... 100... 101... 110... 111

Now make up three different potions.

For the first slave include liquid from every bottle with a one in the first position.

For the second slave include liquid from every bottle with a one in the second position.

For the third slave include liquid from every bottle with a one in the third position.

Now wait twenty hours and see which slaves have died.

If the first slave has died the poisoned bottle's label must have a one in the first position (or a zero if the slave is still alive).

If the second slave has died the poisoned bottle's label must have a one in the second position (or a zero if the slave is still alive).

If the third slave has died the poisoned bottle's label must have a one in the third position (or a zero if the slave is still alive).

Each of the eight possible outcomes for the slaves thus produces one of the eight labels and so indicates the poisoned bottle.

In an exactly similar way you can find one poisoned bottle out of $1024=2^{10}$ bottles using 10 prisoners. Since we have only 1000 bottles, just add (or imagine) another 24 bottles of unpoisoned wine (or water)!

10 prisoners must sample the wine. Bonus points if you worked out a way to ensure than no more than 8 prisoners die.

Number all bottles using binary digits. Assign each prisoner to one of the binary flags. Prisoners must take a sip from each bottle where their binary flag is set.

Here is how you would find one poisoned bottle out of eight total bottles of wine.

In the above example, if all prisoners die, bottle 8 is bad. If none die, bottle 1 is bad. If A & B dies, bottle 4 is bad.

With ten people there are 1024 unique combinations so you could test up to 1024 bottles of wine.

Each of the ten prisoners will take a small sip from about 500 bottles. Each sip should take no longer than 15 seconds and should be a very small amount. Small sips not only leave more wine for guests. Small sips also avoid death by alcohol poisoning. As long as each prisoner is administered about a millilitre from each bottle, they will only consume the equivalent of about one bottle of wine each.

Each prisoner will have at least a fifty percent chance of living. There is only one binary combination where all prisoners must sip from the wine. If there are ten prisoners then there are ten more combinations where all but one prisoner must sip from the wine. By avoiding these two types of combinations you can ensure no more than 8 prisoners die.

One viewer felt that this solution was in flagrant contempt of restaurant etiquette. The emperor paid for this wine, so there should be no need to prove to the guests that wine is the same as the label. I am not even sure if ancient wine even came with labels affixed. However, it is true that after leaving the wine open for a day, that this medieval wine will taste more like vinegar than it ever did. C'est la vie.

Note that each prisoner will either die, or not die, giving you one bit of information. It takes 10 bits to represent all the positive integers $\le 1024$ , so certainly it can represent the first $1000$ positive integers (glasses) so you need 10 prisoners.

Suppose you have $x$ prisoners (designated by the letters A, B, C, D, etc.) You can assign each combination (A, B, ABC, BDF, AEFG, etc.) to a bottle. Therefore, the problem is to solve

$\sum_{n=1}^{x}\binom{x}{n}=1000$ , where $x$ is the number of prisoners required to test 1000 bottles

Now, since $\sum_{n=1}^{x}\binom{x}{n}=2^x-1$ , it follows that

$2^x=1001$ , and

$x=\frac{\log{1001}}{\log{2}}$

So the answer is 10 prisoners.

Number each bottle in binary with each number having 10 digits. e.g. 1 = 0000000001, 59=0000111011, 498=0111110010, etc.

Let the first digit correspond to the first prisoner, the second digit to the second prisoner, the third digit to the third prisoner and so forth. If the digit is a 0, do not give the corresponding prisoner the bottle but if the digit is 1, give it to him.

After the time has passed, record the prisoners which have died and their corresponding digit place. This will give you the binary number for the bottle which has been poisoned.

Therefore, only 10 prisoners are needed. I guess you can prove that no lesser way can be done by bashing it out.