This is a brain teaser I came across recently (original source):

A king has 100 bottles of wine, exactly one of which is poisoned. He decides to figure out which it is by feeding the wines to some of his servants, and seeing which ones drop dead. He wants to find out before the poisoner has a chance to get away, and so he doesn't have enough time to do this sequentially - instead he plans to give each servant some combination of the wines tonight, and see which are still alive tomorrow morning.

a) How many servants does he need?

b) Suppose he had 100 servants - then how many wines could he test?

Answer: the king needs 7 servants. Number the servants 0, 1, 2, 3, 4, 5, 6. Then assign servant $i$ to drink the wines which have an $0$ in their $2^i$s place, when written in binary. For example:

• Servant 0 will drink those wines which have a zero in their $2^0 = 1$s place; the even-numbered wines.
• Servant 1 will drink the wines with a zero in their $2^1 = 2$s place.
• Servant 6 will drink the wines which have a zero in their $2^6 = 64$s place; in this problem, those are just the wines numbered < $64$.

Now watch what happens to the servants, and begin writing an number in binary. Write a zero in the $2^i$s place if servant $i$ dies, and a one otherwise. That number is the number of the poisoned wine.

What is happening is that each servant is contributing one bit of information to our answer. We need $\log_2(n)$ bits of information to discriminate between $n$ options, so we need $\log_2(100) \approx 6.64$ servants for 100 wines. Oops, we can't have a partial servant, so we actually need 7. (The rounding up is an indication that we're not using the power of that last servant fully.)

Here we have a problem whose statement contains nothing about binary numbers, but whose solution makes extensive use of them. One wonders: where is that "2" coming from?

At first I thought that the "2" originated in the fact that we could only observe two outcomes: servant dies or servant lives. What if the wine could be poisoned severely or lightly, so there were three possible outcomes: servant dies, servant gets sick, servant lives? (The goal is the same: identify the poisoned wine.) Then there would be three outcomes, so we could use the same strategy but with ternary.

It turns out that doesn't work, but here's a modification that does. The wine is still either poisoned or not poisioned, but instead of just drinking or not drinking, the servants can either drink the wine fully, sip it a little, or not drink it at all. If you merely sip a poisoned wine, you just get sick rather than dying.

This extension gives us three actions to perform, so the servants can drink, sip, or abstain for wines that have a 0, 1, or 2 in their place. It also gives us three outcomes to observe, so we write a 0, 1, or 2 in the appropriate place depending on whether the servant dies, gets sick, or is unaffected. When the problem is modified in this way, it becomes easier due to the additional information we get: we need only $\lceil \log_3(100) \rceil \approx \lceil 4.14 \rceil = 5$ servants.

What's important is that the number of actions is equal to the number of outcomes. The "2" in the original problem comes from two actions that are related in lockstep to two outcomes.

[Edited 1/3/2020 — Lucy pointed out that I incorrectly said the wines Servant 1 drinks are a multiple of 4.]