Poisoned Wine (1000 Bottles): Puzzle and Step-by-Step Solution
Logic & Strategy
Medium
Reported at Citadel, Jane Street, Two Sigma, Hudson River Trading
The puzzle
A king has 1000 bottles of wine, and exactly one is poisoned. Even a sip of the poison kills in about a day, and the banquet is tomorrow, so there is time for only one round of testing. What is the smallest number of testers needed to find the poisoned bottle?
Short answer: Ten. Number the bottles in binary and let tester k sip from every bottle whose k-th bit is 1; the pattern of deaths spells out the poisoned bottle's number.
Step 1: Count the outcomes you need to distinguish
There are 1000 possible answers, one per bottle. After one round, each tester ends up in one of two states, alive or dead. With n testers there are 2^n possible patterns of outcomes, and each must point to a different bottle.
So you need 2^n to be at least 1000. 2^9 = 512 is too small and 2^10 = 1024 is enough, so at least 10 testers are needed. The question is whether 10 suffice.
Step 2: The binary labelling
Number the bottles 0 to 999 and write each number in 10-bit binary. Bottle 5 is 0000000101; bottle 999 is 1111100111. Give tester k a sip from every bottle whose k-th bit is 1.
Tomorrow, write a 1 for every tester who died and a 0 for every survivor. That 10-bit number is exactly the poisoned bottle's label, because tester k died if and only if the poisoned bottle's k-th bit is 1. Ten testers find the bottle with certainty.
Step 3: What changes with more time
If there is time for two rounds, each tester now has three outcomes: died after round one, died after round two, or survived. With n testers there are 3^n patterns, and 3^7 = 2187 is the first power of three above 1000, since 3^6 = 729. So seven testers are enough.
The scheme is the same in base three. Write each bottle's number in base three. In round one, tester k drinks from bottles whose k-th digit is 2. In round two, the survivors drink from bottles whose k-th digit is 1. A tester who dies in round one marks a 2, one who dies in round two marks a 1, and a survivor marks a 0. The digits name the bottle.
Step 4: Why firms like it
It is information theory in a costume: count the outcomes, count what each measurement can reveal, and design measurements that use every outcome. The same reasoning sizes a test plan, a hashing scheme or a group-testing design.
Why interviewers ask it
Lead with the counting bound, 2^n ≥ 1000, then show the construction that meets it. The two-round base-three follow-up is asked often enough to have ready.
Knowing the proof is half of it. Work Poisoned Wine (1000 Bottles) interactively, then take it under a clock with the rest of the Outcry simulators.