One Poisoned Bottle

Question

Exactly one of 1000 wine bottles is poisoned; any trace kills in 30 days. The banquet is in 31 days, so there's time for only one round of testing. Lab rats can each sip arbitrary mixtures, all simultaneously. What is the minimum number of rats that guarantees identifying the bottle?

Accepted Answer

Ten rats. Number the bottles 0 to 999 and write each number in binary, 10 bits. Rat i sips from every bottle whose i-th bit is 1. After 30 days, exactly the rats whose bit is set in the poisoned bottle's number die: read the death pattern as a 10-bit binary number, and it literally spells the answer. (Bottle 0 kills no rats, also a valid, distinguishable outcome.) Lower bound: one round means the test design is fixed up front; each rat contributes one bit, so k rats produce at most 2^k distinct outcomes. You must distinguish 1000 hypotheses: 2^9 = 512 < 1000 le 1024 = 2^10, so 9 rats can't and 10 can. Tight. The reframing being tested: "testing" is code design. Adaptive halving intuition (split bottles, test, recurse) is worthless here, the 30-day latency permits one parallel round, so the entire decision tree must be flattened into a codebook where every hypothesis maps to a unique outcome vector. This is non-adaptive group testing, and the same one-shot-encoding instinct applies whenever feedback is slower than the decision cycle.

One Poisoned Bottle

Problem

Your answer

Hints

More Brainteasers & Logic to train on