One Poisoned Barrel
The puzzle
A cellar holds 1000 barrels and exactly one is poisoned. The poison kills in exactly one month, in any dose.
You have one month and a number of testers who may each sip from as many barrels as you like. What is the smallest number of testers that always identifies the barrel?
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 at the end of the month: died, or did not.
Hint 2
How many different outcomes can n testers produce between them?
Show the answer Hide the answer
Ten. Number the barrels 0 to 999 in binary and have tester k sip from every barrel whose k-th bit is 1.
How to get there
After a month each tester is either dead or alive - one bit each. Ten testers give 2^10 = 1024 distinct outcomes, which is just enough to name 1000 barrels; nine would give 512, which is not.
Write each barrel number in 10-bit binary. Tester k drinks from every barrel with a 1 in position k.
At the end, read the dead testers as 1 and the living as 0. Those ten bits spell out the number of the poisoned barrel exactly.
The technique worth keeping
Count the information before designing the test: n yes-or-no answers can distinguish at most 2^n cases. Once the bound is known, binary labelling is usually the construction that meets it.