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.
1. Design a testing scheme that guarantees you identify the poisoned bottle, no matter which one it is.
2. Prove that 10 testers are sufficient (i.e., your scheme always works for 1000 bottles).
3. Prove that 9 testers would not be sufficient -- that is, no scheme with 9 testers can guarantee identification among 1000 bottles.
Open the full interactive solver, hints, and worked solution →