Poison, rats, and two days to find the bottle
One of 1,000 wine bottles is poisoned. The poison, in any amount, kills a rat exactly 24 hours after it is drunk. You have 48 hours before the party. Each rat can be given a mixture of samples from any bottles you like at time 0, and any rat still alive after 24 hours can be given a second mixture then.
With a single feeding, 10 rats suffice (binary encoding). Using the two feedings, what is the smallest number of rats that guarantees you identify the poisoned bottle within 48 hours?
Show a hint
A rat that drinks at time 0 and at 24 hours can end in three states: dead at 24 hours, dead at 48 hours, or alive. Three states per rat means base three.
Your answer
Solving needs a free account
Answers, streaks and solutions unlock when you are signed in. Reading the question and the hint stays free.
Discussion
💡 Discussion rules
- No full solutions here. Hints and approaches only.
- Complexity, edge cases and intuition are the point.
- Interview experiences are welcome. Respect your NDAs.
Loading discussion…
Learn the concepts
The theory behind this question.