对"二分法不是最快的"存疑.
设有水 n 瓶,小白鼠 m 只.
每次试毒能够提供 1bit 的信息,它最多只能够使得可能情况数量的最大可能值变成原来的一半. 而任何一次能够提供有用信息的试毒都存在小白鼠死亡的可能性,所以为保证能够分辨出有毒的那瓶水,试毒次数至多为 m 次. 因此对于 n > 2^m,此题无解. 对于 n <= 2^m,试毒次数 q 必有 ceil(log_2(n)) <= q <= m, 其中 ceil(x) 表示不小于 x 的最小整数.
下面构造使得 q = ceil(log_2(n)) (记作 Q) 的方法.
将毒药按自然数由小到大编号,并写成二进制. 显然二进制位数不超过 Q. 对第 k 次试毒 (k = 1, 2, 3, ..., Q-1),选取二进制编号的 2^(Q-1) 位 (即从右往左第 Q-1 位) 为 1 的瓶子,将其中液体在试管中混合,进行试毒. 若有毒,写作 1,反之写作 0. 将各次结果从右往左写,测试完毕后读取写出的数,它就是有毒的瓶子对应的二进制编号.
因此,现在我们得出,这个方法的试毒的最大次数次数最少. (因为不存在试毒次数一定小于该方法的方法)