首先，感谢此文章作者，我只是做了一个自己看着舒服的整理，然后发出来保存下
作者：点赞狂魔刀锋君已放弃治疗
链接：https://www.jianshu.com/p/5afa6f3a5ec4
來源：简书
简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。
下面开始正文
首先来看一系列问题：
1、有 1000 个一模一样的瓶子，其中有 999 瓶是普通的水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在，你只有 10 只小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？
2、有11瓶酒，只有一瓶有毒。喝酒之后，三天会死，只有三天时间。请问至少需要多少只老鼠，可以找出9瓶没有毒的酒？
3、有100只一模一样的瓶子，编号1-100。其中99瓶是水，一瓶是看起来像水的毒药。只要老鼠喝下一小口毒药，一天后则死亡。现在，给你2天的时间，请你告诉我，你至少需要多少只老鼠，才能检验出哪个号码瓶子里是毒药？
4、有1000瓶水，其中两瓶是毒药，喝了毒药1天死，给1天时间，需要多少老鼠？
解题之前，来看一个概念：
一条信息的信息量大小和它的不确定性有直接的关系。比如说，我们要搞清楚一件非常非常不确定的事，或是我们一无所知的事情，就需要了解大量的信息。相反，如果我们对某件事已经有了较多的了解，我们不需要太多的信息就能把它搞清楚。所以，从这个角度，我们可以认为，信息量的度量就等于不确定性的多少。
信息熵
回到这些问题：
问题1：
由于每个瓶子一样，只有一个有毒，我们可以认为是一个等概率的情景，即每个瓶子有毒的可能性都是1/1000，按上面那里计算，信息熵就是
H=−∑1 1000 log11000 = log1000
即需要这么多的信息量。那么每只老鼠会死的概率为1/2，把10只老鼠编号，得到的死生的情况总共有1024种，每种的概率为1/1024，所以可以提供的信息量为log1024，是超过的，所以10个理论上是有可能可以解决的。（这个只是算出一个下界，然后要保证老鼠们的死是互不干扰的，即每个老鼠死的概率就是1/2而不会因为其他的老鼠的死生而出现变化，而每个位用一个老鼠控制刚刚好可以解决这个问题）
问题2：
问题2本质上与问题1是一样的，只是原本的11瓶需要4位来确认，而只需要确定9瓶的话，3位就可以了
问题3：
根据可以继续折腾老鼠这个理念，一个老鼠在两天的过程之后，有三种情况：生死，生生，死死（死生……第一天死了第二天当然不可能活过来）。于是有三种情况，每种概率相等都是1/3,于是一只老鼠可以提供log3的信息量。于是就可以做了，需要的老鼠数目的下界是log100log3=log3100向上取整，即最少需要5个。根据我们上面的想法，其实这个就是一个三进制的方法可以解决。
具体来说是这样，我们有5个位，把每个瓶子编码成3进制，即00000,00001,00002,00010,……这样子，第一天的时候让每个老鼠都喝对应的位为2的水，如果都没死，那么每个位要么是0,要么是1,剩下一天可以解决；如果万一死了几个，那么没关系，毒药对应的位就是2了，所以那一个位也不用再测了。而为什么用3进制，这个就是因为上面的信息熵的结果的推论了。
问题4：
此题目是一个拓展，网上也没有什么定论，网上常见的问题方式是，10只老鼠最多可以确定几瓶无毒？因为1000瓶有两瓶总共有(2100)，那么设可以测出有x瓶无毒，那么就还有1000-x瓶不确定，其中两瓶毒，用信息论的说法就是
log(21000)−log(21000−x)<=10log2
解出来x的理论上限是968。
目前最佳的方案好像是用4×4×5的一个方案，具体可以参见M67大神这篇文章的评论区。在知乎上面也讨论了这个问题，大家可以去看下，我弃疗了
网友评论