致被毒死的老鼠君
笔试面试的时候，题目总是一些悲伤的故事。
比如不断往下掉的蚂蚁君，永远只能相撞而不能在一起
比如A君兴高采烈买卡片而老板阴笑数钱（老板进了一批货，总共有5种卡片，每种都有很多很多，A君去买卡片，拿到任一种卡片的概率相等，问A君平均要买多少张卡片才能集齐所有卡片）其实是一种经典概率问题“赠券收集问题”
比如被医生告知患有癌症，但是其实患癌症的概率极低的担惊受怕的Z君
出题者们总是说着这些那些悲伤的故事，然后让我们忍着痛苦回答题目。
他们天天虐人，时不时搞下蚂蚁，然后现在终于轮到了老鼠君。
大家都知道，老鼠的作用很多，比如拿来解剖，比如拿来烹饪，比如拿来试毒。
首先是问题一：
有 1000 个一模一样的瓶子，其中有 999 瓶是普通的水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在，你只有 10 只小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？
当然，这个问题应该很多人都知道。1000个瓶子的编号可以编码成为2进制，然后由若干个老鼠去试。具体来说，1000个，用2^10=1024,超过1000,那我们用10个2进制位来编码瓶子编号，然后拿十个老鼠，每个老鼠控制一个位，比如让一个老鼠把所有的某一个位为1的瓶子的水都喝掉，就是说第一个老鼠，喝掉所有的第一位为1的水。如果死了，那么证明此位为1,不死证明此位为0,即如果十个老鼠是“死生死生死生死生死生”，那么对应的编号就是“1010101010”，即有毒的水的编号。
那么如果我不是要找出有毒的那瓶，而是要找出无毒的若干瓶的话，应该怎么做呢？
问题二，我第一次见到是在“待字闺中”微信公众号：
有11瓶酒，只有一瓶有毒。喝酒之后，三天会死，只有三天时间。请问至少需要多少只老鼠，可以找出9瓶没有毒的酒？
这道题目的思路跟上面一样，比较阴险的地方是找出9瓶无毒的而不是找出有毒的那瓶。11瓶找9瓶，我们知道11瓶可以通过4个位来确定，而因为可以有两瓶不需确定，所以其实我们只需要3个位置，即确认了有毒的酒的编号的某三个位，由于剩下的一个位只是0和1,所以就有两瓶无法确定，剩下9瓶无毒，举个例子，比如我们后三位确认为“011”，那么只有可能“1011,0011”这两瓶有可能有毒，其他都是无毒的。
那么其实做实验那个人不是拖延症患者，其实时间没有那么紧呢？
上面这俩还是算正常的题目，然后现在开始坑爹了。
问题三：
有100只一模一样的瓶子，编号1-100。其中99瓶是水，一瓶是看起来像水的毒药。只要老鼠喝下一小口毒药，一天后则死亡。现在，给你2天的时间，请你告诉我，你至少需要多少只老鼠，才能检验出哪个号码瓶子里是毒药？
本来只有一天的时间的，现在有了2天。这个只意味着一件事情，第一天存活的老鼠君第二天还可以拿来折磨！
如果说第一题还可以用直觉来做的话，那么这一题直觉什么的就很难想到了，有些人说可以用2进制的那个答案除以2,答案也跟我待会要说的方法一样，那我只能说，是巧合……
在正式说之前，要先说明下这个问题需要用到的数学工具：信息熵。一说到信息论，顿时觉得有点高端大气上档次的感觉。
通俗的讲，信息是对事物运动状态或存在方式的不确定性的描述。而香农提出的信息量公式：
H=−∑ipilogpi
其中i是指可能发生的事件……具体解释可参看维基。根据香农的信息概念，信息能消除不确定性，而解题的时候，就是消除不确定性，得到确定的答案。如果一个事件的不确定性即熵有这么多，那么根据题目所限制的手段，最多能够得到多少信息量？是否超过本来的不确定性？能不能解？就是这么一个问题。插入一句，天平称球问题其实也可以通过这个算出一个下界，因为天平有三种状态，左倾，右倾或者平衡，所以一次称量提供的信息量为log3，然后blablabla……
扯远了，我们先用信息熵的做法做一下问题一，由于每个瓶子一样，只有一个有毒，我们可以认为是一个等概率的情景，即每个瓶子有毒的可能性都是1/1000，按上面那里计算，信息熵就是
H=−∑11000log11000=log1000
即需要这么多的信息量。那么每只老鼠会死的概率为1/2，把10只老鼠编号，得到的死生的情况总共有1024种，每种的概率为1/1024，所以可以提供的信息量为log1024，是超过的，所以10个理论上是有可能可以解决的。（这个只是算出一个下界，然后要保证老鼠们的死是互不干扰的，即每个老鼠死的概率就是1/2而不会因为其他的老鼠的死生而出现变化，而每个位用一个老鼠控制刚刚好可以解决这个问题）
我们看到问题三，根据可以继续折腾老鼠这个理念，一个老鼠在两天的过程之后，有三种情况：生死，生生，死死（死生……第一天死了第二天当然不可能活过来）。于是有三种情况，每种概率相等都是1/3,于是一只老鼠可以提供log3的信息量。于是就可以做了，需要的老鼠数目的下界是log100log3=log3100向上取整，即最少需要5个。根据我们上面的想法，其实这个就是一个三进制的方法可以解决。
具体来说是这样，我们有5个位，把每个瓶子编码成3进制，即00000,00001,00002,00010,……这样子，第一天的时候让每个老鼠都喝对应的位为2的水，如果都没死，那么每个位要么是0,要么是1,剩下一天可以解决；如果万一死了几个，那么没关系，毒药对应的位就是2了（第一天死掉的老鼠君们，你们的死不会白费！），所以那一个位也不用再测了。而为什么用3进制，这个就是因为上面的信息熵的结果的推论了。
这个问题的推广问题是，有n瓶水，1瓶有毒，有i天时间，喝了毒水一天死，有k个老鼠，n的最大值可以取多少？
因为i天之后老鼠有可能有(i+1)种状态，分别是第一天死，第二天死，……，第i天死，以及在出题者无尽的折腾下存活。那么就是一个i+1进制的问题了，所以n最大可以有(i+1)k。
有些大神，比如Matrix67，比如玛丽大叔，在问题三的时候仍然可以用无比牛逼的直觉去解决，然后到了下面这个问题的时候，终于还是没辙了。
问题四：
有1000瓶水，其中两瓶是毒药，喝了毒药1天死，给1天时间，需要多少老鼠？
网上也没有什么定论，网上常见的问题方式是，10只老鼠最多可以确定几瓶无毒？因为1000瓶有两瓶总共有(2100)，那么设可以测出有x瓶无毒，那么就还有1000-x瓶不确定，其中两瓶毒，用信息论的说法就是
log(21000)−log(21000−x)<=10log2
解出来x的理论上限是968，不过想了很久我都没有想到什么好的方案……上网查之发现也是众说纷纭，各路英豪均没有具体的实施手段，目前最佳的方案好像是用4×4×5的一个方案，具体可以参见M67大神这篇文章的评论区。在知乎上面也讨论了这个问题（虽然貌似涉及人权……），在下的能力无法解决如此高端的问题了……
最后吐槽一下问题，作为一个下毒的问题，居然无视毒量，随便都可以死；话说，如果要说毒量的话，那一个老鼠死掉还真有可能是因为水肿而死而不是被毒死……
