One Poisoned Bottle in a Thousand
The puzzle
You have a thousand bottles. Exactly one is poisoned. The poison is lethal in any quantity, and it kills between twenty and twenty-four hours after it is drunk, with no symptoms before that.
You have twenty-four hours and a number of testers who will each drink from as many bottles as you ask. What is the smallest number of testers that guarantees you identify the poisoned bottle?
Stuck?
One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.
Hint 1
Each tester gives you one bit of information at the end: alive or dead.
Hint 2
How many different outcomes can ten testers produce between them?
Show the answer Hide the answer
Ten. Number the bottles 0 to 999 in binary; tester i drinks from every bottle whose i-th bit is a 1. The pattern of who dies spells out the poisoned bottle’s number.
How to get there
Each tester ends the day in one of two states, so n testers produce 2 to the power of n distinguishable outcomes. For a thousand bottles you need at least 1000 outcomes, and 2^9 is 512 while 2^10 is 1024 - so ten testers, and no fewer, can possibly work.
Ten is also enough. Number the bottles 0 to 999 and write each number in ten binary digits. Give tester 0 a sip from every bottle with a 1 in the ones place, tester 1 every bottle with a 1 in the twos place, and so on up to tester 9.
A day later, write a 1 for each tester who died and a 0 for each who lived, in the same order. That ten-digit binary number is the bottle. If testers 0, 3 and 5 die, the bottle is 1 + 8 + 32 = 41.
The technique worth keeping
Counting outcomes first tells you the answer before you have any method: if the question has a thousand possible answers and each tester yields one bit, you need ten bits. That lower bound argument is worth as much in an interview as the construction, and often more - it shows you knew the answer was ten before you knew how.