Poisoned Bottle Identification with Binary Testing
You have 1000 bottles of wine, and exactly one of them is poisoned. The poison is undetectable by any means other than drinking it -- any tester who consumes even a drop will die exactly 24 hours later, with no symptoms before that. Testers who drink only unpoisoned wine are perfectly fine.
You have 10 volunteer testers and a single 24-hour window. At the start of the window, each tester can drink from as many bottles as you choose. After exactly 24 hours, you observe which testers have died and which have survived.
- Design a testing scheme that guarantees you identify the poisoned bottle, no matter which one it is.
- Prove that 10 testers are sufficient (i.e., your scheme always works for 1000 bottles).
- Prove that 9 testers would not be sufficient -- that is, no scheme with 9 testers can guarantee identification among 1000 bottles.
Hints
- Think of each tester as providing one bit of information -- alive or dead. How many bits do you need to distinguish 1000 possibilities?
- Consider assigning each bottle a unique binary number and using the testers to "read out" the bits of the poisoned bottle's number.
- Label bottles $1$ through $1000$ in 10-bit binary. Tester $j$ drinks from bottle $i$ exactly when the $j$-th bit of $i$ is 1. The death pattern directly encodes the answer.
Worked Solution
How to Think About It: The core challenge is that you only get one round of tests -- every tester drinks at time zero and you read results 24 hours later. So you cannot adapt based on intermediate results. This means your entire strategy must be a single pre-committed assignment of bottles to testers. The question becomes: how do you design that assignment so the pattern of deaths uniquely identifies the poisoned bottle? The key is to think of each tester as a single binary digit -- alive or dead, 0 or 1. Ten testers give you a 10-bit binary string, which can encode $2^{10} = 1024$ distinct outcomes. Since $1024 > 1000$, there are enough distinct patterns to label every bottle.
Key Insight: Assign each bottle a unique 10-bit binary number. Tester $j$ drinks from bottle $i$ if and only if the $j$-th bit of bottle $i$'s binary label is 1. The pattern of deaths then reads out the binary label of the poisoned bottle.
The Method:
- Label every bottle with a unique number from $1$ to $1000$.
2. Write each label in binary using 10 digits (pad with leading zeros). For example: - Bottle 1: $0000000001$ - Bottle 2: $0000000010$ - Bottle 7: $0000000111$ - Bottle 1000: $1111101000$
- Assign each of the 10 testers to one bit position ($j = 1, 2, \ldots, 10$, from least significant to most significant).
- At time zero, tester $j$ drinks from every bottle whose $j$-th bit is 1. For instance, tester 1 drinks from all odd-numbered bottles (bit 1 is 1), tester 2 drinks from bottles 2, 3, 6, 7, 10, 11, $\ldots$ (bit 2 is 1), and so on.
- After 24 hours, observe which testers died. Construct a 10-bit string where bit $j = 1$ if tester $j$ died, and bit $j = 0$ if tester $j$ survived.
- Convert that 10-bit string from binary to decimal. The result is the label of the poisoned bottle.
Why this works: Each bottle has a unique binary label, so each bottle causes a unique pattern of deaths. The poisoned bottle contributes its poison to exactly the testers whose corresponding bits are 1. No other bottle shares that label, so no other bottle could produce the same death pattern.
Why 10 suffice: With 10 testers, there are $2^{10} = 1024$ distinct possible death patterns (including the all-zeros pattern where nobody dies, which would correspond to bottle 0 -- unused since we label from 1). Since $1024 \geq 1000$, every bottle gets a unique pattern.
Why 9 are not enough: With 9 testers, there are only $2^9 = 512$ distinct death patterns. By the pigeonhole principle, if you have 1000 bottles and only 512 possible outcomes, at least two bottles must map to the same pattern. If the poisoned bottle is one of those two, you cannot distinguish them. No testing scheme with 9 testers can guarantee identification among 1000 bottles.
Practical Considerations:
- The scheme requires each tester to drink from roughly 500 bottles (about half, since each bit is 1 for about half the labels). This is fine as long as any amount of poison is lethal -- mixing does not dilute the effect.
- The all-zeros pattern (no deaths) is a valid outcome corresponding to bottle 0. Since we label from 1, this outcome would indicate an error (no bottle is poisoned), which is ruled out by the problem statement.
- This is essentially a binary code with Hamming distance at least 1 between any two codewords. For guaranteed identification (not error correction), distance 1 suffices.
Answer: Label each bottle $1$ through $1000$ in binary using 10 bits. Tester $j$ drinks from all bottles whose $j$-th bit is 1. The binary string of tester deaths gives the poisoned bottle's label. Ten testers provide $2^{10} = 1024 \geq 1000$ distinct outcomes (sufficient); nine testers provide only $2^9 = 512 < 1000$ (insufficient by pigeonhole).
Intuition
This problem is really about information theory dressed up as a logic puzzle. Each tester is a binary channel -- they either die (1) or survive (0). With 10 independent binary channels and one round of testing, you can distinguish at most $2^{10} = 1024$ outcomes. That is exactly the information-theoretic capacity of your system. The binary encoding scheme is not just one clever trick -- it is the optimal scheme, using every bit of information the testers can provide.
This pattern shows up constantly in quantitative work. Whenever you need to identify one item out of $N$ possibilities using binary tests, you need $\lceil \log_2 N \rceil$ tests. It is the same principle behind binary search, error-correcting codes, and even how computers address memory. In a trading context, you might use the same logic to design a minimal set of diagnostic trades that pinpoint which of $N$ possible market regimes is active, or to determine the source of a PnL discrepancy across $N$ books using the fewest reconciliation checks.
Trader's Intuition (Mapping Perspective):
A good trader sees this immediately as a one-to-one mapping problem. You have 1000 objects to label and a single observation window — you assign labels at the start, wait 24 hours, and read the result. The key insight is recognizing that $2^{10} = 1024 > 1000$: ten binary digits give you enough labels for all 1000 bottles with room to spare.
This is the same structure as "a biased coin has probability $1/1000$ of landing heads — how many flips do you need to identify which coin out of 1000 is biased?" The connection is $2^{10} = 1024 \approx 1000$ — ten bits of information suffice. The binary encoding is not a clever trick; it is the natural mapping from the problem's structure. Once you see it as a labeling problem, the binary assignment writes itself.