The question is: in bottles, there exists a bottle which is poisonous. We can use rats to find. Any rat drinks a poisonous water even mixed will die. If it doesn't die, it can be reused. We need to find out the minimum times of experiments if we can do all the tests for rats parallelly.
The final answer of bottles and rats is
The prove of this is easy.
First consider the lower bound of the question.
Label all the rats from to . With experiments, the possible outcome is , for a specific rat may die at the th experiments or never dies. Thus, there are possibilities.
So, every possible outcome must match at most one kind of bottle, which means So, The difficult part is the construction of the lower bound.
We can use mathematical induction to derive this.
We skip the base and it is quite easy to derive by the readers.
We start by assuming for any pair , when and both not greater than and , but not both equal to and .
Consider which equals and the binomial theorem, it equals to .
We can divide the first test by label the groups binary from to . In every group, add distinct bottles where is the number of of the label. By binomial theorem, all bottle are assigned into a group.
The maximum times of this method is because all the rats died when , but we only assigned bottle. So we find the poisonous bottle.
If , we just assign some empty group and make up to .