老鼠与毒药问题

问题描述

有1000个一模一样的瓶子，其中999瓶中装的是普通的水，一瓶是毒药，水和毒药只能通过老鼠来分辨，喝下毒药的老鼠会在一个星期后死亡（刚好一个星期）。现在你有一个星期时间，请问至少需要多少只老鼠才能确定出哪个瓶子装的是毒药？

思路

解决这个问题前可以先考虑把问题简化。
老鼠的数量明显少于瓶子数量，可以先求出n只老鼠可以鉴别多少瓶的液体。

解题过程

假设老鼠死亡状态为1，活着为0。

①当n = 1时，老鼠有两个状态，0和1，一只老鼠可以鉴别至多两个瓶子的液体；
②当n = 2时，老鼠有四个状态，00,01,10,11。
假设有老鼠甲和老鼠乙。两只老鼠明显可以鉴别三瓶液体。那我们试一下是否可以鉴别四瓶液体。假设有A、B、C、D四瓶液体。甲乙两只老鼠刚好有四个状态，四个状态跟四瓶液体一一对应的话就能根据老鼠状态来判断那一瓶是毒药。如下：

根据上面的表格，让老鼠甲喝瓶子C、D里的液体，老鼠乙喝瓶子B、D里的液体，如果老鼠甲死亡，则C瓶装的是毒药，如果老鼠乙死亡，则瓶子B装的是毒药，两只都死则D是毒药，都没死则A是毒药。

这样的鉴定思路是每只老鼠喝1/2个瓶子里面的液体，每只老鼠所选的瓶子又跟另外一只有一半的交集，这样就产生了四种可能。而产生每种可能的瓶子只有一个，如产生11的瓶子只有D。就能判断出是哪一个瓶子装的是毒药。

四个瓶子的液体鉴定完成。
因为两只老鼠只有四个状态，如果瓶子数量有五个的话则不能通过两只老鼠来判断。不信可以自己试一下。

③当n = 3时，老鼠总共有8个状态：000,001,010,011,100,101,110,111。根据n = 2的规律，可以知道3只老鼠总共可以鉴别8瓶液体。

结论

根据前面的三种情况可以得出规律，n只老鼠能鉴别的瓶子数m是这n只老鼠的两个状态的排列组合，即m = 2ⁿ。

现在可以求出原问题的解了，根据题意能得出m <= 2ⁿ，当m = 1000时，求出 n为7 n为10。即至少需要 7只 10只老鼠才能鉴别出哪个瓶子装的是毒药。

推演

如果你有两个星期时间，那么至少需要多少只老鼠才能找出毒药？（待解）