0
$\begingroup$

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 :)

Improve this question
$\endgroup$
11
  • $\begingroup$ 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. $\endgroup$
    – Paul Panzer
    Aug 11, 2020 at 3:28
  • $\begingroup$ @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. $\endgroup$
    – Dmitry Kamenetsky
    Aug 11, 2020 at 3:32
  • 1
    $\begingroup$ 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. $\endgroup$
    – Paul Panzer
    Aug 11, 2020 at 3:38
  • $\begingroup$ True, there is a clear trade-off. I am interested in seeing solutions with both strategy types (see my update). $\endgroup$
    – Dmitry Kamenetsky
    Aug 11, 2020 at 3:42
  • $\begingroup$ 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? $\endgroup$
    – Ross Presser
    Aug 11, 2020 at 13:20

7 Answers 7

Reset to default
13
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Dapianoman
    Aug 11, 2020 at 5:36
  • 2
    $\begingroup$ @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. $\endgroup$
    – ManfP
    Aug 11, 2020 at 15:58
8
$\begingroup$

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.

Improve this answer
$\endgroup$
5
$\begingroup$

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

The answer is 1 rat.

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

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ That is only true for K=1, but not for any K in general. $\endgroup$
    – Dmitry Kamenetsky
    Aug 11, 2020 at 13:35
  • 2
    $\begingroup$ @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. $\endgroup$
    – musefan
    Aug 11, 2020 at 13:43
  • $\begingroup$ yes you are right my wording wasn't specific enough. I tried to modify it. $\endgroup$
    – Dmitry Kamenetsky
    Aug 11, 2020 at 14:01
  • $\begingroup$ 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. $\endgroup$
    – Iuri Guilherme
    Aug 26, 2020 at 19:35
3
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ "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. $\endgroup$
    – Stef
    Aug 11, 2020 at 12:29
  • 1
    $\begingroup$ 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. $\endgroup$
    – Florian F
    Aug 11, 2020 at 14:26
  • $\begingroup$ >"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? $\endgroup$
    – Dapianoman
    Aug 13, 2020 at 5:59
  • $\begingroup$ @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). $\endgroup$
    – Dapianoman
    Aug 13, 2020 at 6:01
  • $\begingroup$ 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. $\endgroup$
    – Florian F
    Aug 14, 2020 at 7:07
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ 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) $\endgroup$
    – Stef
    Aug 11, 2020 at 12:22
  • $\begingroup$ Could you combine your two answers into one please. $\endgroup$
    – Dmitry Kamenetsky
    Aug 11, 2020 at 14:12
  • $\begingroup$ If you mean to remove one bottle at a time from the mix, then, when the rats stop dying you have identified a single poisoned bottle, the last one you removed from the mix. And that at the cost of possibly many rats. You should better test one bottle at a time. $\endgroup$
    – Florian F
    Aug 12, 2020 at 11:11
  • 1
    $\begingroup$ @DmitryKamenetsky but this is a different approach, my other answer tries to isolate the poisoned bottles (easier) while this one tries to isolate the non poisoned bottles (harder, probably kills more rats). $\endgroup$
    – Iuri Guilherme
    Aug 26, 2020 at 19:36
  • $\begingroup$ @Stef I mean I have isolated the bottles without any poison because I discarded all the bottles that could have poison. The process in the first paragraph explains how I will come to the conclusion that I have made a batch of isolated bottles that are guaranteed not to have poison. The second and third paragraph go about finding out which bottles are poisoned in the discarded batch (the ones not in the isolated "good bottles" batch). $\endgroup$
    – Iuri Guilherme
    Aug 26, 2020 at 19:41
0
$\begingroup$

Testing several bottles together instead of letting a rat drink from the first, second etc bottle until it dies or survives all the bottles never gains more information, so it is pointless.

Now to find the number of bottles: Assume the king who never lies tells you that he picked one bottle, poisoned the other 99, and then either poisoned the last bottle or not. So you know the answer is 99 or 100.

Mixing two or more bottles is pointless, because you know the rat is going to do, no information gained at all. So you can only give each rat in turn a bottle to drink, until one survives or all 100 rats are dead. If the king poisoned all the bottles or you and the rats are unlucky and the unpoisoined bottle is the last one, all 100 rats die.

Improve this answer
$\endgroup$
1
  • $\begingroup$ why is testing several bottles together pointless? $\endgroup$
    – Dmitry Kamenetsky
    Aug 13, 2020 at 0:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.