命题一

华罗庚杯竞赛题（小学中年级组）
有7瓶药水，其中一瓶有毒，小白鼠喝毒药水后1小时后死亡，现有3只小白鼠和1小时时间，请找出毒药水？

逻辑推理法

方法一

把瓶子从1-7编号
A鼠喝：1+2+3
B鼠喝：3+4+5
C鼠喝：5+6+1

A死，2有毒；
B死，4有毒；
C死，6有毒；
AB死，3有毒；
AC死，1有毒；
BC死，5有毒；
三鼠都没死，7有毒

思考

这种分法规律是什么？

方法二

A鼠喝 1，2，3，4 瓶；
B鼠喝 1，2，5，6 瓶；
C鼠喝 1，3，5，7 瓶。

一周后，假设发生：第一只老鼠死了：毒药在前 4 瓶（ 1, 2, 3, 4）；第二只老鼠活着：毒药在（ 3, 4）；第三只老鼠死了：第 3 瓶。

思考

这种分法规律是依据句二分法的思想，当次分组取上次每组的前一半。

二进制编码法

把瓶子从1-7编号；
3只老鼠编号A-B；
用1表示有毒，0表示无毒；

瓶子编号：

让三只老鼠分别喝二进制编号同位，且值是1的瓶子。
（从左边开始）
A喝第一位都是1的瓶子：4567；
B喝第二位都是1的瓶子：2367；
B喝第三位都是1的瓶子：1357；

比如结果是：
A老鼠死了，那么4567其中有一瓶肯定是毒药，由于他们第一位都是1，所以有毒那瓶第一位肯定是1；
B老鼠没死，那么2367肯定都不是毒药，由于他们第二位都是1，所以有毒那瓶第二位肯定是0；
C老鼠死了，同理有毒那瓶第三位肯定是1；

由此得出有毒瓶子的编号是：101，也就是5号瓶子有毒。

大家应该都听说过这个老题目：有 1000 个一模一样的瓶子，其中有 999 瓶是普通的水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在，你只有 10 只小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？ 这个问题的答案也堪称经典：把瓶子从 0 到 999 依次编号，然后全部转换为 10 位二进制数。让第一只老鼠喝掉1到1000所有二进制数右起第一位是 1 的瓶子，让第二只老鼠喝掉所有二进制数右起第二位是 1 的瓶子，等等。一星期后，如果第一只老鼠死了，就知道毒药瓶子的二进制编号中，右起第一位是 1 ；如果第二只老鼠没死，就知道毒药瓶子的二进制编号中，右起第二位是 0 ……每只老鼠的死活都能确定出 10 位二进制数的其中一位，由此便可知道毒药瓶子的编号了。 现在，有意思的问题来了：如果你有两个星期的时间（换句话说你可以做两轮实验），为了从 1000 个瓶子中找出毒药，你最少需要几只老鼠？注意，在第一轮实验中死掉的老鼠，就无法继续参与第二次实验了。 答案：7 只老鼠就足够了。事实上，7 只老鼠足以从 3^7 = 2187 个瓶子中找出毒药来。首先，把所有瓶子从 0 到 2186 编号，然后全部转换为 7 位三进制数。现在，让第一只老鼠喝掉所有三进制数右起第一位是 2 的瓶子，让第二只老鼠喝掉所有三进制数右起第二位是 2 的瓶子，等等。一星期之后，如果第一只老鼠死了，就知道毒药瓶子的三进制编号中，右起第一位是 2 ；如果第二只老鼠没死，就知道毒药瓶子的三进制编号中，右起第二位不是 2，只可能是 0 或者 1 ……也就是说，每只死掉的老鼠都用自己的生命确定出了，三进制编号中自己负责的那一位是 2 ；但每只活着的老鼠都只能确定，它所负责的那一位不是 2 。于是，问题就归约到了只剩一个星期时的情况。在第二轮实验里，让每只活着的老鼠继续自己未完成的任务，喝掉它负责的那一位是 1 的所有瓶子。再过一星期，毒药瓶子的三进制编号便能全部揭晓了。 类似地，我们可以证明， n 只小白鼠 t 周的时间可以从 (t+1)^n 个瓶子中检验出毒药来。 总结：时间换取资源(老鼠)。 出处：http://www.nowamagic.net/librarys/veda/detail/1834

命题二

李永乐老师视频
烧脑面试题：老鼠和毒药问题怎么解？二进制和易经八卦有啥关系？李永乐老师告诉你。
有100瓶药水，其中一瓶有毒，小白鼠喝毒药水后1周后死亡，现在问，给你一周时间至少需要多少只小白鼠才能找出那一瓶是毒药水？

借助命题一的二进制编码法，转化下问题就是 0和1，至少需要多少位能表示出100种不同状态？
因此至少需要7只小老鼠。

思考

不管是用什么方法，基本思路就是排除法，排除法的核心在于分组，保证组之间能够相互推断。

还是没弄明白，这种题为什么可以使用二进制的编码方式来解答？
有人提到了二分法，因为老鼠只有2种状态。

假如我们有10个小球，其中有一个是异常的，其他9个都是一样的，我们怎么才能通过最少的称量来确定是哪一个异常，是重还是轻？这个时候我们就可以使用三分法了，为什么？因为天平有三个state， 平衡，左倾，右倾，使得我们”有可能“ 将问题规模缩小为1/3， 事实上，确实可以实现将问题规模缩小到1/3。

其他的都是直接给出了答案，不是在解答，这个回答为什么二进制可以来解答这个问题：

这个问题下，大都是通过二进制编码的方式解答。我换个思路，不用二进制，尝试用逻辑分析的角度解释。最后说明此解法和二进制编码法的关系。 Q1：为什么 10 个白鼠能分辨 1000 瓶液体？ （先假设老鼠喝毒药之后立刻死，而不是一周后，稍后解释原因）我们让第一只老鼠喝一点前 500 瓶液体，如果它死了，那么毒药就在前 500 瓶里。下面，将存在毒药的 500 瓶一分为二，再拿一只老鼠来试验：我们再次精确把毒药限制在 250 瓶中。继续下去，每次取一半做实验，我们将依次精确到 125 瓶（第三只），精确到 62 /(或) 63 瓶（第四只），31 / 32 瓶（第五只），15 / 16 瓶（第六只），7 / 8 瓶（第七只），3 / 4 瓶（第八只），1 / 2（第九只，这次可能一举就确认，如果恰好出现在只有 1 瓶的那个分块中，饶过一只可怜的小白鼠，否则就需要再实验一次决定），1 瓶（第十只）。 因为每次老鼠实验都能排除一半的可能，因此，10 只老鼠，最多可以分辨 2^10 个可能，即 1024 瓶液体。 Q2：上面这个假设没有考虑到“只能观察一次”这个前提，即不允许我们每次实验一下，观察并排除一半，再循环实验。用什么方式让这种分辨在一次观察中就解决呢？ （考虑 3 只老鼠，8 (2^3) 瓶液体的情况）我们让第一只老鼠喝一点 1，2，3，4 前四瓶的液体；第二只喝一点 1，2，5，6 瓶；第三只老鼠喝一点 2，4，6，8 瓶。 一周后，假设发生：第一只老鼠死了：毒药在前 4 瓶（ 1, 2, 3, 4）；第二只老鼠活着：毒药在（ 3, 4）；第三只老鼠死了：第 4 瓶。 这个方法本质是确保每只老鼠能继续细分上一只老鼠的结果。即，第一只老鼠帮我们区分出了是前四还是后四，下一次我们需要区分在毒药在前四瓶中的前二还是后二（或者后四的前二还是后二）。在 Q1 立即死亡的假设中，我们在知道是前四还是后四之后，再让下一只老鼠实验前四的前两个或者后四的前两个；但是在题设延迟死亡的假设中，我们无法立刻知道，那么，干脆就让下一只把前四中的前二，和后四中的前二都喝掉——这样我们无论如何都能知道结果了。 Q3：推广到更多毒药要老鼠怎么喝呢？ 如题设，1000 瓶的情况，我们让每只老鼠都喝一半总样本的液体，即 500 瓶。第一只喝掉前 500 瓶；第二只每隔 250 瓶喝接下来的 250 瓶，即 1 ~ 250, 501 ~ 750；第三只每隔 125 瓶喝 125 瓶，即 1 ~ 125, 251 ~ 375, 501 ~ 625, 751 ~ 875；第四只每隔 62 瓶喝 63 瓶（或每隔 63 瓶喝 62 瓶）；直到第十只，每隔 1 瓶喝 1 瓶，即都喝奇数（或偶数）瓶。 比如只有第 1, 2, 3, 4, 5, 6, 7, 8, 9 只死亡的情况（除了第 10 只其他都死了），我们能依次精确到毒药存在于以下范围的瓶子中，1 ~ 500, 1 ~ 250, 1 ~ 125, 1 ~ 63, 1 ~ 32, 1 ~ 16, 1 ~ 8, 1 ~ 4, 1 ~ 2, 2。得出第 2 瓶是毒药的结果。 Q4：这和二进制的解法有什么区别？ 没区别。二进制解法中，第一只老鼠，即负责个位的那个老鼠，就是每隔 1 瓶就喝一个：因为二进制逢 2 归 0；第 3 只老鼠，即负责百位的老鼠，每隔 2^(3-1) = 4 瓶喝 4 个：二进制百位隔 4 个保持一样；第 n 只老鼠，即负责从各位数第 n 位的老鼠，每隔 2^(n-1) 瓶喝 2^(n-1) 个。其实和上述用逻辑的方式喝法没有区别。

为什么这问题能和二进制扯上关系？

我们知道在搜索算法里，二分法是最快的解决方案。这种问题如果用逻辑法，怎么分组，有没有套路？

参考

你只有 10 只小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？