Solution
A Thousand Bottles, Three Rounds
Show the problem again
A cellar holds 1000 bottles of wine, exactly one of which is poisoned. A taster who drinks any amount from the poisoned bottle dies at the end of the round in which they drank; a taster who has not drunk the poison survives. A taster can drink from any number of bottles in a round, and survivors can be used again in later rounds. You have three rounds, and you see who died at the end of each round before planning the next. What is the minimum number of tasters that is guaranteed to find the poisoned bottle?
Worked solution
The answer is 5. Let N(t, r) be the largest number of bottles that t tasters can resolve in r rounds. With r = 0 only one bottle can be resolved. In the first round some set of k tasters might die; those tasters are gone, and the remaining t - k tasters face a smaller problem with one fewer round, so N(t, r) = sum over k of C(t, k) N(t - k, r - 1). This evaluates to (r + 1)^t, which is 4^t for three rounds (the count of 'ways each taster can die in round 1, 2, 3 or survive'). Since 4^4 = 256 < 1000 ≤ 1024 = 4^5, four tasters cannot suffice and five can. To achieve it, write the bottle number (0 to 999) in base 4 with five digits; taster i drinks from the bottle in round d if its i-th digit is d (d = 1, 2, 3), and a digit of 0 means the bottle is never sampled by that taster. The round in which each taster dies (or that it survives) then spells out the digits of the poisoned bottle.
Source: Version of the 'poisoned wine / pigs' puzzle popularised in interview collections and on LeetCode; no traceable original source. Statement written for AxiomIQ.