0
$\begingroup$

Preface

This is a quite interesting question that I have come across some earlier years in my Olympiad training. Due to my bad memories and notebook record, I failed to trace back where I found this question. I also lost the original solution to this problem. It was not until recently, I started reading about different number of systems rather than the decimal system that another solution crossed my mind.

I had solved the problem below using the binary system. But what troubles me is that, the number used was rather symbolic, which means, it has little to do with mathematics. So I added some extensions to the problem. The extension is an open question, and I didn't really know how to solve it.

Please give your solution to the original problem, it is okay if you don't use the binary system. And please help me solve my extension.

Any help is appreciated.


Problem

A king is throwing a party. During the party, a mandarin is reported to be ill due to wine poison. Therefore, the king ordered the soldiers to check the wines. There are $2019$ bottles in the cellar, and the guards decided to use rats to try and find the poisonous bottle. Assume that the attempts does not take time, and the rat also take one hour to die. There is also only one hour to do all the tasting. How many rats are there needed to find out the poisonous bottle?

Note that: a rat can taste many bottle (all $2019$ is okay, but of course this is not a solution) as long as it doesn't die. However, if a rat tasted both bottle A and bottle B, and it dies, we don't know whether A or B is poisonous.


Extension

So in the problem above, the number $2019$ and 1 hour has hardly any meaning. Now I am going to link all these numbers together.

A king is throwing a party. During the party, a mandarin is reported to be ill due to wine poison. Therefore, the king ordered the soldiers to check the wines. There are $x$ bottles in the cellar, and the guards decided to use rats to try and find the poisonous bottle. Assume that the attempts do not take time and the rats die after one hour. If the guards has 100 rats and one hour to find the bottle, what is the maximum value of $x$?

$\endgroup$
  • $\begingroup$ the question is a bit weird. in the original one, what is the point of 18 hrs if we cannot use it right, i thought if a rat taste bottle A and then taste bottle B, survive even 18 hrs after tasting bottle A but died 18 hrs after tasting bottle B we can conclude bottle B is poisonous, not A. this way we can use the 18 hrs number. in Your extension, there is no limitation, just use 2019 rats and we can detect within 1 hr and 1 min $\endgroup$ – Rezha Adrian Tanuharja Mar 23 at 8:39
  • $\begingroup$ @RezhaAdrianTanuharja I am sorry, let me edit this. It was a little faulty $\endgroup$ – Nikola Tolzsek Mar 23 at 8:42
  • $\begingroup$ Your issue looks interesting, but some data is missing. 1) You should say that there is a recording (or memorizing) of the tested bottles by each rat (does the order in which the bottles are tested matters ?) 2) Does a rat stops acting at once if it has drank in the poisonous bottle ? 3) Generally speaking, I don't understand indeed the role of time here. 4) I understand that what you call a binary solution could be as well be called a smart selection of subsets ? $\endgroup$ – Jean Marie Mar 23 at 9:17
  • $\begingroup$ @JeanMarie 1) Yes, you have to record it, otherwise, of course you cannot remember it. Actually in my solution, the order does not matter. 2) No it doesn't. 3) Well, as I said, 1 hour means literally nothing. It is just the time for the rats to die must coincide. 4) No, I actually converted the statements to the binary system and solved it. $\endgroup$ – Nikola Tolzsek Mar 23 at 9:21
  • $\begingroup$ Thanks for you answer but I am sorry, it is very hard for me to understand. A re-formulation is necessary, IMHO. A last question : call a rat an "agent" : can we say that the issue boils down to find a "schedule" for the agents ; I mean by that, each agent receives a list of bottles to be tested ? $\endgroup$ – Jean Marie Mar 23 at 9:26
2
$\begingroup$

For the sake of explanation, let us take an example with a small number of bottles, 64, which, moreover is a power of $2$ ($64=2^6$). Let us assume furthermore that the bottles are numbered from 0 to 63.

Here is a solution with 6 rats (please note that $6$ is the exponent of $2$ giving $64$).

This solution is the following schedule given to the 6 rats, under a graphical representation with color red (resp. blue) when rat number $j$ has to test (resp. not to test) bottle number $i$.

enter image description here

Fig. 1 : The $6$ rats' scheduling for the $64$ bottles based on binary representation.

For example, the first rat has to test bottles $32$ to $63$, the second rat bottles from $16$ to $31$ and bottles $48$ to $63$, etc...

It is easy to recognize in the figure the binary numbers with their natural ordering :

$000000$

$000001$

$000010$

$000011$

etc.

The result is to be read on the dead/alive rats :

If one has for example with convention D for dead and A for Alive :

rat 1 : D, rat 2 : A , rat 3 : A, rat 4 : A, rat 5 : D, rat 6 : D

it suffices to convert the sequence DAAADD into 011100, finally giving the decimal number (28) of the poisoned bottle.

Of course, if we have a number of bottles which is not a power of $2$, like $2019$, it suffices to take the power $2^n$ of $2$ which is immediately above, here $2^{11}=2048$ : you will need $\color{red}{11}$ rats, with some "phantom bottles"...

Edit : It remains to prove that this exponent $r$ of $2$ (giving the number of rats to be used) gives the minimal number of rats. This is easy.

Let us take back the initial example. 5 rats cannot be enough because the knowledge of the casualties panel (from case AAAAA to DDDDD) gives the possibility to distinghish $1$ case among $2^5$ cases, which cannot be placed in a bijective manner with the $2^6$ number of bottles.

But there is in fact a little stone in the shoe : the case $AAAAA$ (all alive) cannot occur. Therefore, for example, we can test $65$ people with 6 rats only without going to the next power of two !

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yes, absolutely! This is the correct solution. Have you tried the extension? Because as I saw in your solution, you have not pointed out why 6 is the smallest possible value? I mean, why 5 is not possible? Then, you might not have solved the reversed version, like; if you have 11 rats, can you point out that you can test at most 2048 bottles? $\endgroup$ – Nikola Tolzsek Mar 24 at 1:54
  • $\begingroup$ I agree. I am going to think about it. $\endgroup$ – Jean Marie Mar 24 at 7:31
  • $\begingroup$ I have added an Edit to my answer to make it clear. $\endgroup$ – Jean Marie Mar 24 at 7:44
  • $\begingroup$ I think I have it now (see my changed Edit). $\endgroup$ – Jean Marie Mar 24 at 8:24
  • $\begingroup$ Do you mind if I rewrite that edit to make it clearer? $\endgroup$ – Nikola Tolzsek Mar 24 at 8:37
0
$\begingroup$

So as @Jean Marie has pointed out above, the only remaining part is to prove that if there are at least $2^n +1$ bottles then there cannot be less than or equal to n rats.

If we use n rats, and each rats taste some bottles, then we come up with the following numbering method.

Label each bottle $S=A_1A_2A_3...A_n$. If a bottle S is tasted by the rat number $k$, then $A_k=1$. Otherwise, $A_k=0$.

Thus, we now have at most $2^n$ distinguished values for S, which means that there are two bottles with the same number.

In the worst case, among the two bottles with the same numbers contain the poisoned one, then we cannot determine which one is the "phantom bottle".

Q.E.D

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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