1,000 bottles, one poisoned, 10 test strips, a single round of testing. Find it.
A king has 1,000 bottles of wine, and he knows exactly one is poisoned. A test strip dipped in wine reveals the poison after some hours, but each strip can only be used once, and he needs an answer in a single simultaneous round of testing. What is the fewest number of test strips he needs to guarantee finding the poisoned bottle?
Reveal the answer
Just 10 strips. Number the bottles 0 through 999 in binary, which needs at most 10 binary digits. Dip strip 1 into every bottle whose first binary digit is 1, strip 2 into every bottle whose second digit is 1, and so on. The exact combination of strips that come back positive spells out the poisoned bottle's number in binary. The puzzle is a classic illustration of 'group testing,' a field of combinatorics and information theory studying how few yes/no tests can pinpoint one item out of an enormous set.