One poisoned bottle
You have 1,000 bottles of wine and exactly one is poisoned. You have test strips that turn red 24 hours after touching even a drop of poison. A strip can be touched by many bottles, but you only have time for one 24-hour round of testing.
What is the fewest strips that guarantees you find the poisoned bottle?
Show hint
Each strip ends up as either red or not red: one bit of information. How many bits do you need to tell 1,000 bottles apart?
Show solution
10 strips.
Number the bottles 0 to 999 and write each number in binary using 10 bits. Strip i gets a drop from every bottle whose bit i is 1. After 24 hours, read the strips as a binary number: red is 1, not red is 0. That number is the poisoned bottle.
It works because 210 = 1,024 ≥ 1,000, while 9 strips give only 512 patterns.
Want a problem like this every day? See today's problem and keep a streak going.