这是一个传播得非常广的问题：有1000瓶液体，其中一瓶是毒药，其他的都是清水。毒药看上去和水一样，只能用老鼠来试验。老鼠在喝了毒药以后一个星期后一天内的任意时刻死亡。最少需要多少只老鼠才能找到毒药？

n瓶液体当中一瓶有毒，总共有n种可能，用集合N表示。一只老鼠的试验以后的生死可以用0、1表示，r只老鼠的生死是一个0、1串，总共有2的r次方中结果，用集合R表示。

我们要找到一个实验方法f，把N中元素分别映射到R上。并且N中的两个元素不能对应R中的同一个元素。

也就是说，第1瓶有毒和第2瓶有毒这两种可能，不能在我们做完实验以后，得到老鼠的生死是一致的。

所以R中的元素至少N中的元素相等。因此2的r次方大于等于n,  r >= log(n)。

回到这个问题上来，理论上，我们需要10只老鼠才能找出隐藏的毒药。

具体来说应该怎么操作呢，也就是我们要寻找一种算法。以及这种算法是否能只用10只老鼠就找到1000当中的毒药呢？

如果有一只老鼠，我们可以让它喝一半的药水。它的生死就能确定毒药在哪一半。

例如n = 8。

              000 001 010 011 100 101 110 111

老鼠a                                 1     1     1     1

老鼠a和右边的药水，如果毒药在右半边，老鼠死；否则，老鼠活。

也就是用二进制去编码药水一只老鼠的生死可以指示这一瓶毒药某一位的状况

              000 001 010 011 100 101 110 111

老鼠a                                  1     1     1     1

        c              1            1           1            1

如果是1000瓶药水，依次用二进制表示。依照上面的方式我们可以用10只老鼠来找到唯一的毒药。

这个问题还有一些变化。

如果1000瓶液体当中有两瓶毒药，最少需要的老鼠是多少呢，应该如何操作？

根据前面的方法，我们先计算理论上的下界。

毒药的分布总共有C(1000,2)中情况，我们最少需要19只老鼠。

具体如何操作呢？

首先把毒药平均分成两组，如何确定毒药在哪一组呢？

例如：

A:   000 001 010 011

B:   100 101 110 111

一只老鼠是不够的

我们用两只老鼠a,b。a喝下A组，b喝下B组。

如果两只老鼠全部死去，我们可以确定毒药分别在A、B当中。如果老鼠只有一只死去，我们可以确定两瓶毒药在同一组里

也就是说通过上诉方法，我们可以确定毒药编号的二进制表示的第1位的状况（都是1，都是0，分别是0、1）

这个方法能否确定第2位的状态呢？

答案是能。

但是存在一个问题。

如果第1位分别是0、1，第2位也分别是0、1，那么这两个瓶的编号是00、11，还是01、10呢？

如何解决这个问题呢？

如果我们知道两瓶毒药的编号的第1位是不同的

例如：

A:   000 001 010 011

B:   100 101 110 111

如果我们有两周试验的机会，可以第一周先用2对老鼠（为什么是2对？）找到毒药编号哪一位是不同的。在知道哪一位不同以后，在第二周用2对老鼠得到两瓶毒药的其他位值。也就是说我们可以用2*log2(n/2)+2*log(n/2) 只老鼠在两轮试验的情况下找到两瓶毒药

但是我们只允许有1轮试验时间，如何解决呢？

既然不能猜，我们就全押好了。

对于n=8的情况，两瓶毒药的编号，可能在1、2、3位不同。总是有一位不同，也有可能好几位不同。

我们先押第1位不同，也就是两瓶毒药分别在A、B组当中：

A:   000 001 010 011

B:   100 101 110 111

用2对老鼠分别测试A、B组毒药。

再押第2位不同，两瓶毒药分别在C、D组中：

C: 000 001 100 101  

D: 010 011 110 111

也是用两对老鼠

再押第3位不同，分别在E、F组：

E: 000 010 100 110

F: 001 011 101 111

那么这样测试的结果会如何呢？

假设两瓶毒药编号在第3位相同。

比如是010， 100，那么E、F两组测试的结果是F组的老鼠全部存活下来；

如果是011， 111，那么E、F两组的测试结果是E组的老鼠全部存活。

所以第3位不相同的假设是不成立的。

也就是说哪一位如果是相同的，针对那一位做的实验会出现一组当中全部存活的情况。因此这两组针对这一位的实验是无效的。

如果两瓶毒药在第1位是不同的，

例如毒药编号是011、100，那么A、B组当中都会出现死亡，那么第1位不同的假设是成立的，我们可以得到各个位的值。

综上所述在猜测某一位不同时，我们需要2*log(n/2)只老鼠；要押中所有位的话，我们需要log(n)*2*log(n/2)只老鼠。

也就是说，如果n=1000，有两瓶毒药。用上述方法，我们需要（10*2*9）180只老鼠，才能找出毒药编号。

离我们的下界19有些远。

老鼠毒药问题