Transforming a combinatorics question to a binary system question.

Question

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$?

Answer 1

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$.

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 !

Answer 2

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