The problem
1000 bottles of wine, exactly one poisoned. The poison is lethal in any dose but takes 24 hours to act. You have prisoners to test with and 24 hours. What is the minimum number of testers?
The answer: 10
The construction
Number the bottles 0 to 999 and write each number in binary - 10 bits suffices since 2^10 = 1024.
Assign each tester to one bit position. Tester i drinks from every bottle whose i-th bit is 1.
After 24 hours, read the outcome as a binary number: tester i contributes a 1 if they died and a 0 if they lived. That number is the poisoned bottle's index.
Bottle 5 is 0000000101, so testers 0 and 2 drink from it and only those two die. No other bottle produces that exact pattern, because binary representations are unique.
Why ten is also the minimum
Each tester produces one bit of information - alive or dead. n testers give 2^n distinguishable outcomes. To identify one bottle among 1000 you need 2^n at least 1000, so n at least 10.
Being able to state the lower bound as well as the construction is what separates a complete answer from half of one. Interviewers usually ask "can you do better?" precisely to see if you have it.
Variants
Two poisoned bottles. Much harder - you now need to distinguish C(1000, 2) ≈ 500,000 possibilities, requiring at least 19 testers, and the clean binary construction no longer works because the death patterns of two bottles OR together ambiguously. This needs superimposed codes.
Poison acts in 12 hours, and you have 24. Two sequential rounds, so each tester yields more than one bit: alive after both, died in round one, died in round two. With 3 outcomes per tester you need only ceil(log base 3 of 1000) = 7 testers.
That last variant is the best follow-up, because it tests whether you understood that the answer is about counting distinguishable outcomes rather than about binary specifically.
More in brainteasers.