# Finding the number of poisoned bottles

This is a well-known problem (discussed here and here), but I am adding a twist to it.

A king has 100 bottles of wine and poisons $$K$$ of them, where $$0 \leq K \leq 100$$. You have a supply of rats and need to determine how many of the bottles are poisoned. You are not interested in finding the actual poisoned bottles and you only want to find the value of $$K$$. You can get a rat to drink a mix of wine taken from different bottles. If the mix contains any poisoned wine then the rat will die after 1 hour. What is the minimum number of rats required to conclusively identify the value of $$K$$ in the general case (not any specific $$K$$)?

I only know the obvious solution that uses 100 rats, so I am very interested in seeing if better solutions exist! Note I am leaving this puzzle open to either adaptive (rats can be reused, but longer wait time) or non-adaptive (rats cannot be reused, but just 1 hour wait time) strategies. I am interested in both types of solutions.

P.S. No rats were harmed in the making of this puzzle :)

• rot13 Vf gurer nal orarsvg gb zvkvat nf bccbfrq gb frdhragvnyyl qevaxvat guebhtu gur vaqvivqhny obggyrf? Vs abar bs gurfr obggyrf vf cbvfbarq lbh pna erhfr gur fnzr eng naq vg jvyy yvir nsgre grfgvat rnpu ovggyr vaqvivqhnyyl be gur zvk, fb bhgpbzr naq vasb tnvarq ner gur fnzr. Vs gurer vf n cbvfbarq obggyr gur eng jvyy qvr va rvgure pnfr bayl jvgu vaqvihny obggyrf lbh jvyy trg n ovg zber vasb. Aug 11 '20 at 3:28
• @PaulPanzer the solutions in the links explain how mixing is beneficial for the case of finding the one/two poisoned bottles. I am not sure if mixing helps in this particular puzzle. Aug 11 '20 at 3:32
• But that's a clear trade-off. Let's take the one out of 1000 bottles poisoned example. You can find it either killing a single rat but potentially having to wait 1000 hours, or getting there faster (10 hours) but killing up to 10 rats. Aug 11 '20 at 3:38
• True, there is a clear trade-off. I am interested in seeing solutions with both strategy types (see my update). Aug 11 '20 at 3:42
• How many times can a bottle be sampled before it is empty? If I empty all the bottles, the number of bottles that still have poison is zero, but have I answered the puzzle? Aug 11 '20 at 13:20

I'm pretty sure the minimum is

100, or n for any value n such that 0 <= K <= n

If we consider the worst case scenario:

All n bottles are poisoned. In this situation any value less than n will leave some ambiguity where any value between the number tested and n would be a possible solution. In the worst case scenario, every bottle must be independently tested.

• Let $K = 0$ and your answer would allow $n = 0$, but of course it is impossible to determine how many bottles have poison with 0 rats, even if there are 0 poison bottles. You must have $n > K$ unless $K = 100$. Aug 11 '20 at 5:36
• @Dapianoman I think $n$ is meant to be an upper bound for $K$ that is known a priori. If you are told that $0\leq K\leq 0$, you can indeed determine $K$ without the use of any rats whatsoever. Aug 11 '20 at 15:58

If I...

...allow one rat to drink one bottle, wait all the time it takes to be sure that bottle isn't poisoned, and then send the same rat to drink the next bottle, until it dies from poisoning and I need the next rat...

...then...

...the minimum number of rats required to conclusively identify the value of $$K$$ is $$K+1$$.

...unless...

...$$K=100$$, in which case the minimum number of rats required to conclusively identify the value of $$K$$ is $$K$$, as pointed in other answer.

What is the minimum number of rats required to conclusively identify the value of K?

It just might happen to not always be the maximum number required.

• That is only true for K=1, but not for any K in general. Aug 11 '20 at 13:35
• @DmitryKamenetsky Actually, it's true for K=0 (mix all bottles and feed to one rat) and K=1 (individual give the rat 1 bottle at a time and hope the last one is the poisoned one). But it's still the minimum as per your question. Your question doesn't say "what is the fewest number of rats that can solve all possible combinations". I'll be honest... I am being very pedantic about your wording with my answer. I stand by it though, a good puzzle is only as good as it's written. Aug 11 '20 at 13:43
• yes you are right my wording wasn't specific enough. I tried to modify it. Aug 11 '20 at 14:01
• This answer is valid, you may need more than 1 rat to conclusively identify the value of K but the minimum number is 1 since you can't conclude anything with less than 1 rat. Unless the answer allows you to use chickens. Aug 26 '20 at 19:35

The minimum is $$K + 1$$ or 100, whichever is smaller. The only way to tell if a bottle has poison is if it kills a rat, and if a rat is killed it cannot be used to test any other bottles. So in the case of $$K = 100$$ you need 100 rats to die. For $$K = 0,\dots,99$$ once the $$K$$th rat dies you are guaranteed to have found all the bottles, and the last rat survives.

• "The only way to tell if a bottle has poison is if it kills a rat, and if a rat is killed it cannot be used to test any other bottles." is not strictly true. You are allowed to mix liquids from more than one bottle together. You could imagine using a rat to determine that there is at least one poisoned bottles among a subset of the bottles, and use clever combinations to get a lower number of rats. At least, your answer does not prove that it isn't possible. You have only proven that K+1 rats is sufficient; not that it is the minimum.
– Stef
Aug 11 '20 at 12:29
• It is not that hard. Suppose J<K rats got killed. Ignore all the bottles that a rat tested and survived. Among the remaining bottles pick for each rat the the last bottle it drank from. These J bottles can be poisoned. And not other bottle needs to be. Aug 11 '20 at 14:26
• >"use clever combinations to get a lower number of rats" Like what combinations? It's impossible to determine that a bottle has poison unless it has killed a rat. That's practically by definition, after all. What is poison but that which kills? Aug 13 '20 at 5:59
• @Florian F If you let J < K, and only J bottles are poisoned, then you arrive at a contradiction, because K is DEFINED as exactly the number of bottles which are poisoned (thus J = K => K < K is a contradiction). Aug 13 '20 at 6:01
• J is the number of rats killed. I showed that you cannot determine the value of K without killing at least K rats. If the number of rats killed, J, is less than K, then you cannot exclude that only J bottles are poisoned. Aug 14 '20 at 7:07

Looking at the benefit of mixing...

...(without it I don't think you can do better than 100 rats because feeding a single unmixed bottle to a rat only tells the status of that single bottle.), trying a binary search, if in the worst case you have K=100 poisoned bottles and split it into two 50 bottle groups, then mixing each group and feeding it causes the rat to die (since all bottles are poisoned) which forces us to split that group again; it doesn't tell us the number of poisoned bottles in that group. So we have to keep splitting until we can't anymore, i.e. until we have 100 single-bottle groups, which we then give to 100 rats respectively, and then we know the number in those groups and the total number K. Which means we've gone through more than 100 rats, which is worse than the naive approach. So a binary-search approach using mixing doesn't seem to be better than the naive approach.

My gut feeling is

that nothing will beat the naive approach, as my hunch is that mixing multiple bottles still only gives you definite knowledge about one more bottle at the cost of one more rat, the same thing you get when you do the naive approach of one rat per bottle.

If I...

...mix all 100 bottles and give that mix to the first rat, wait all the time it takes to be sure that mix isn't poisoned, and in the event of rat dying, I give a mix of 99 bottles to the next rat, and so on until the rats stop dying...

...I have isolated all the bottles without any poison. Let that be $$n$$ for $$0≤n≤100$$. It already took me $$101-n$$ rats unless $$n=0$$ in which case it already took 100 rats. Let that number be $$r$$...

...so now I have to make sure there aren't any bottles without poison in the bottles I discarded. I had put them all in an organized row while I was discarding them so I'll start from the first I discarded. I'll give one by one to the rats just like my other answer. Therefore I will need more $$s$$ rats where $$K-n>=s>=0$$ to determine the value of $$K$$, which is $$K=r+s$$.

That would be a very inefficient solution to the problem, unless...

...the rats stop dying very early or the first rat doesn't die.

So it's kind of a...

lottery of efficiency.

• Your sentence "...I have isolated all the bottles without any poison." in the second paragraph is not true (which you acknowledge in the third paragraph)
– Stef
Aug 11 '20 at 12:22