今天的趣题来源于 IBM Ponder This 三月份的谜题。
大家应该都听说过这个老题目：有 1000 个一模一样的瓶子，其中有 999 瓶是普通的水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在，你只有 10 只小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？
这个问题的答案也堪称经典：把瓶子从 0 到 999 依次编号，然后全部转换为 10 位二进制数。让第一只老鼠喝掉所有二进制数右起第一位是 1 的瓶子，让第二只老鼠喝掉所有二进制数右起第二位是 1 的瓶子，等等。一星期后，如果第一只老鼠死了，就知道毒药瓶子的二进制编号中，右起第一位是 1 ；如果第二只老鼠没死，就知道毒药瓶子的二进制编号中，右起第二位是 0 ⋯⋯每只老鼠的死活都能确定出 10 位二进制数的其中一位，由此便可知道毒药瓶子的编号了。
现在，有意思的问题来了：如果你有两个星期的时间（换句话说你可以做两轮实验），为了从 1000 个瓶子中找出毒药，你最少需要几只老鼠？注意，在第一轮实验中死掉的老鼠，就无法继续参与第二次实验了。
答案：7 只老鼠就足够了。事实上，7 只老鼠足以从 37 = 2187 个瓶子中找出毒药来。首先，把所有瓶子从 0 到 2186 编号，然后全部转换为 7 位三进制数。现在，让第一只老鼠喝掉所有三进制数右起第一位是 2 的瓶子，让第二只老鼠喝掉所有三进制数右起第二位是 2 的瓶子，等等。一星期之后，如果第一只老鼠死了，就知道毒药瓶子的三进制编号中，右起第一位是 2 ；如果第二只老鼠没死，就知道毒药瓶子的三进制编号中，右起第二位不是 2，只可能是 0 或者 1 ⋯⋯也就是说，每只死掉的老鼠都用自己的生命确定出了，三进制编号中自己负责的那一位是 2 ；但每只活着的老鼠都只能确定，它所负责的那一位不是 2 。于是，问题就归约到了只剩一个星期时的情况。在第二轮实验里，让每只活着的老鼠继续自己未完成的任务，喝掉它负责的那一位是 1 的所有瓶子。再过一星期，毒药瓶子的三进制编号便能全部揭晓了。
类似地，我们可以证明， n 只小白鼠 t 周的时间可以从 (t+1)n 个瓶子中检验出毒药来。
Nice
话说前几天刚刚看到这个问题 不过是国王和士兵版的
科学的力量啊！
屌爆了
那一下的转折还是没有反应过来啊……
啊呀~这个问题的推广版真是进制的妙用啊~
乍一看觉得跟离散数学里面的什么有点相像，一时想不起来。。
老鼠喝那么多水 不会撑死吗?
无责任吐槽：其实应该说，任何喝下毒药的生物都会在一星期之内的任何一个时候死亡
不然总是准确的在一星期之后死的话，一只足够了。。
从另一个角度看也可以的：
1号老鼠喝：1-500号瓶子
2号老鼠喝：1-250号，501-750号
3号老鼠喝：1-125号，251-375号，501-625号，751-875号
依次分下去….
现在发现脑子不够用了
。。。不错，的确是一只老鼠就够了
第一次来说句话。
此题还有一个延伸，我现在还不知道答案，这里请教下：
还是1000个瓶，但是2瓶有毒，10个老鼠，一周时间，最多可以确定多少瓶没有毒？我知道一个可以确定900瓶没毒的方法，但不知道这个是不是最佳的了
我一开始也把这题当“脑筋急转弯”了，如果老鼠准确的在一个星期后死亡的话，一只足够
“任何喝下毒药的生物都会在一星期之后死亡”这个题干没啥意义，反而诱使人想歪，不如直接在问题中表明：“只能做一轮实验”、“只能做两轮实验”
to mingz：那样要多少个星期才能得到结果啊……
to mingz：是我想错了
你的这个想法和 hamming码 如出一辙
忘了说，12楼2瓶有毒10只老鼠那题是高盛的面试题。
有意思，前些天听他们讨论了，看了这篇文章，又有收获，
只用一只的，不知道想的怎么样的歪？
从生物学角度分析一只老鼠就行。。取成年性成熟公老鼠一只，取其睾丸内大量精虫（百万单位总有了吧）。。- -然后把这些精虫平均分成N份（比如文中的1000份），然后放入毒液中。。估计一天就能检测出效果了吧。。检测各个毒液中的精虫活性即可。。（哈哈，我这个是搞笑的哈~）
这种毒药的LD50的倒数等于+∞
这么说1000个星期一只老鼠就能知道哪个瓶子有毒了？怎么做到的能说说不
“不然总是准确的在一星期之后死的话，一只足够了”这个关键在于，准确二字吧，是用时间轴来做标签鉴别吧？
非常好，很好的编码思想啊！
一只老鼠……每分钟给老鼠喝一个瓶子……在开始试验的(10080+x)分钟后死亡，x是瓶子编号……试验需要总时间是1周+16小时40分钟……
太经典了，，，，喜欢
to 22L
不如每秒喝一瓶，试验后（604800+x）秒后死亡，x是瓶子编号
为何这类问题总需转化为二进制才得解？
数学问题按理说应该和进制无关吧？
十进制下有无方案？
另，评论的时候响应奇慢，点击两次以上显示已评论，但是没看见我那层楼？！并且仅是wordpress下的问题
求解
在一轮的情况下其实就是在10个元素的子集个数内都可以
楼上900瓶怎么解的，说说～
为什么又是小白鼠，可怜的小白鼠……用生命换来的只一个编码，在三进制的情况下还不确定……
我只做到840瓶，900瓶的牛人能解释下么~
30楼840瓶的解法已经很对路了，840你是弄一个5*5的矩阵来试的吧，这样每个cell混40瓶，最坏情况下可以确定（25-4）*1000/25=840瓶没毒。你试试6*6的矩阵，比5*5要优，可以确定（36-4）*1000/36=888瓶没毒。另一方面，再升1维，构建4*4*5的一个cube，可以确定（80-8）*1000/80=900瓶没毒.容易看出再升维的话不会比3维更好。我也不清楚900是不是最优解。
我发现弄一个5*5的矩阵可以推出920瓶没毒的。
每个格子放40瓶，5个老鼠喝横行，5只喝竖行。第三排，第二列的40瓶里面有一瓶有毒，就能确认是喝第三排和喝第二列的两只老鼠死掉了，这样可以发现5*5的矩阵中的两处毒药，一共80瓶。所以能够确定920瓶是没毒的。
我发现弄一个5*5的矩阵可以推出920瓶没毒的。
每个格子放40瓶，5个老鼠喝横行，5只喝竖行。第三排，第二列的40瓶里面有一瓶有毒，就能确认是喝第三排和喝第二列的两只老鼠死掉了，这样可以发现5*5的矩阵中的两处毒药，一共80瓶。所以能够确定920瓶是没毒的。
如果推广到三维，3*3*4 ，一个格子可以放28瓶，最后可以确定944瓶没毒的。
不知道有没有问题。
即使老鼠准确的在一个星期后死亡的话，一只也是不够的。
既然死亡时间让你准确算了，那么题目所问的“一星期的时间，如何检验出哪个瓶子里有毒药”同样也是严格的一个星期，多了一秒钟也是错误答案。
所以题目没有任何歧义。
微博营销
承接微博推广，刷粉丝、转发、评论、认证等业务。
QQ 2232388982
粉丝量太少？
转发量太少？
回复量太少？
还没有认证？
专业微博团队一条龙服务，解决您的上述烦恼。
我们团队覆盖
腾讯微博，
新浪微博，
搜狐微博，
网易微博，
凤凰微博，
饭否微博。
现承接个人或企业网路推广业务，老团队，信得过。
QQ 2232388982
@33楼：有问题，对5*5的情况，如果位置（2，2）（3，3）的40瓶内有毒和位置（2，3）（3，2）的40瓶内有毒，会导致同样的4只老鼠老鼠（2，0）（0，3）（3，0）（0，2）死掉，你无法区分究竟是哪个组合，所以5*5只能确定（25-4）*1000/25=840瓶没毒。同样3*3*4也只能确定900瓶没毒
上贴最后一句是4*4*5，只能确定900瓶没毒
@36楼: 2维情况是这样,3维的情况下一个格子所在的三个方向都死了只有两种可能,1这个格子有毒,2这个格子没有毒但是三个方向上各有一瓶毒药,可是毒药一共只有两瓶,不会出现这种情况,所以这个格子一定有毒
如果按照3*3*4这个方向推的话,三维的时候是不能留空的,因为留空的部分会降为2维,存在和2位同样的混淆问题,也就是说只能分成3*3*4,但是可以单独先拿出28瓶来放在外面,不喝,于是剩下972瓶正好等于27*3*3*4,每格27瓶,可验出945瓶无毒,比944多一瓶
我想说，这个题目是没有答案的。你只有一个星期的时间。而老鼠要一个星期死，所以你的时间不够。。
@36楼:5*5分析的很对，谢谢。没明白6*6和4*4*5是怎么来的，按照我的思路，那就分别需要12和13只小白鼠了。
@38楼:@39楼:我觉得你分析的有道理。
@38楼:你把3*3*4 简化成2维，还是会有 36楼所说的4瓶中无法确定2瓶的情况。
@38楼：3*3*4三维情况，最不利会出现2^3=8个无法确定，比如毒药为（1，2，3）和（2，3，4），6只老鼠死亡，有8种可能。
3*3*4方法无法判断比例为8/36，5*5为4/25，所以还不如5*5。当然都应该多留出一份不检测，即无法判断比例为8/37和4/26. 取整缘故，后者39×25=975，留25不测。最多可以得到（25-4）×39+25=894.
@38楼，三维情况下混淆情况也有，最坏有8种可能，所以如果是3*3*4的话，有（36-8）*1000/36=777瓶可以确定没毒，图省事，这里round up or down的问题暂且先不考虑
@41楼，为什么是6*6或者4*4*5，可以先考虑一维的情况，把1000瓶平均分10份，每份混起来，至少可以确定800瓶没毒。如果平均分11份，每份90.9瓶混起来，让10个老鼠喝其中的10份，余下的一份不理，这样至少也可以确定（11-2）*1000/11=818瓶没毒，优于分10份。如果再多分就不行了。同样到2维的话，可以看出6*6优于5*5，三维下4*4*5也优于3*3*4
续44楼，当然6*6的话，每一维只分5只老鼠，余下的空着。三维的话，老鼠按334来分配，每一维还是有一个空位
哦对,3维也是有混淆的
想了一下,如果绕开这个方针的思路,尝试排除混淆如何
3维混淆如果毒瓶在一个平面,那么混淆倍数是x2,如果在不同平面,混淆倍数是x4
3单位立方体下,只考虑4倍混淆情况,毒瓶构成的立方体要么是2*2要么是3*3,2*2时必包含中心,3*3时则是所有顶点,所以9只构成3单位立方体,1只负责喝中心和任一顶点,可以将4倍混淆倍数降低到2倍,就是分27*36+28共28堆,最坏情况下可以识别928瓶
大体思路是部分用来构成方阵部分用来排除混淆,不知道构图是否正确
我尝试了下2维排除混淆的情况,4*4结果太小,4*5貌似无法构图
哦46楼的构图不对,只能减到3倍混淆,那么重新计算一下按照27*35+55分堆,最坏情况下只能识别895瓶,看来要重新搞一下构图
@47楼，我想了很久了，按照这样factorial design的方法，三维4*4*5应该是最佳解，即至少可以确定900瓶梅毒（当然如果取整的话，至少896瓶）。再想得到更优解，可能要考虑别的思路了，但我还没想到
对于“1000个瓶，但是2瓶有毒，10个老鼠，一周时间，最多可以确定多少瓶没有毒？”
从信息论角度分析，1000个瓶，2瓶有毒的情况有C(1000,2)种，如果能确定x瓶无毒，那么在剩下的1000-x瓶中，2瓶有毒的情况有C(1000-x,2)种，故C(1000,2)/C(1000-x,2) < 1024，最大的x整数解968就是理论的上限。当然不一定能找得到对应的方法。
同理也可以得到1000个瓶，但是n瓶有毒，10个老鼠，一周时间，最多可以确定多少瓶没有毒这样的理论值。
@49楼，有趣，从没想到过这个方法，这也是我提出这个问题的初衷，找到自己想不到的思路。不过我对信息论是门外汉，能具体解释一下那个不等式什么意思吗?多谢
to楼上，其实很简单，你去找找关于信息论，信息量的计算方法资料，不难。公式的意思就是：
1000个瓶，2瓶有毒的情况有C(1000,2)种，它包含了
log2( C(1000,2) )比特的未知信息。同样最后确定了x瓶无毒后，剩下的1000-x瓶还包含了
log2( C(1000-x,2) )比特的未知信息。
因此中间少掉的信息，就是我们通过10只老鼠所获得的。每只老鼠只有生死两种状态，所能提供信息量是1比特，所以少掉的信息最多就是10比特。
将log2( C(1000,2) ) – log2( C(1000-x,2) ) <= log2(10)
展开就是上面的不等式了。
确实啊，空位这个设定很精髓！受教了。
最后那个公式有点笔误，应该是
log2( C(1000,2) ) – log2( C(1000-x,2) ) <= 10
那1000瓶毒药，但2瓶有毒，一周时间，需要多少只老鼠才能确定哪两瓶有毒？？怎么设计方案嘞？？？
@43楼：比如毒药为（1，2，3）和（2，3，4），6只老鼠死亡，只能有4种可能吧。
把毒药为（1，2，3）和（2，3，4）想象成一个正方体，8个点组成的正方体只有对角线的两瓶才能让这6只老鼠死亡，而对角线只有4对，也就是说只有4种可能？
@55楼，对角线是只有4对，但你没法确定哪一对是毒药，所以这8瓶都没法确认没毒
第一个链接挂掉了。
这次lz给的答案不是最优解了，其实只需要6只老鼠。从信息论来说，二进制才是最优的，可以最大程度的获得信息。1000进行二进制编码，第一个星期6只老鼠可以确定二进制的前6位，除去死掉的一只，第二星期用5只老鼠确定二进制的后4位。在两星期内N只老鼠可以判定的毒药瓶数为2^（2N-1），同理，t星期内N只老鼠可以判定2^(t*(2N-t+1)/2)瓶。
主要建立老鼠死亡状态和瓶子的一一对应关系。
58楼，你确定第一轮只会死掉一只么。死掉0~6只都是可能的
精彩！
那要是1024个瓶子就不能用二进制算了？
非常厉害！
如果k只老鼠从n瓶药里找s瓶毒药
根据二进制精神应该毒药数目得满足2^k-1<=C(n,s)
然后开始穷举……
毒药分布是Rn空间矢量Ei=(m1,…,mn)，有s个mi=1
老鼠的吃药情况是Rk空间矢量ai=C*Ei，吃那瓶药就Cij=1
存活情况是Rk空间R=(n1,…nk)，ni=ai*E，大于1就取1
问题就是求矩阵C(ci),使得n(ni)=C*m(mi)
emc的面试题
两个星期不是应该可以做8轮实验的吗？9进制的话只要4只老鼠。
惊人的想法
这是决策树吗
这个有学过 蛮不错的
真NB啊，必须MARK
又找到一道，被用来作为笔试，面试的题。。
实际上你知道，我有一个同学给出了更另人称奇的做法
他的解法实在是……
我们当时面对的是国王的1000瓶酒和10个死刑犯，我很快给了那个二进制的做法，但是那个同学说，只要一个死刑犯就足够了
对应到小白鼠上，他的解法是这样的：7*24*60*60=604800
因此每隔10分钟喂小白鼠舔一下，并计时
一个星期后看小白鼠什么时候毒发身亡，于是我们找到了毒药……
这个答案我实在不好评判，但是佩服他的思维，所以来发个贴……
路过膜拜
刚刚想了一下，1000个水瓶里面有n个有毒的话，要多少只老鼠才可以在一周之内找到所有的毒瓶子呢？答案是log_2{1000Cn} 进一。原理是：1000只瓶子里面只有一个有毒的时，我们用老鼠的生死作为一个符号，来分辨1000种不同的情况。现在我们要做的，只是要在1000Cn种不同的情况里面找到其中一种而已。由此可以推导出其他很多情况的公式了吧。。
@48楼 我重新构造了一个结构，三角形，十行，从一到十，每个老鼠喝两条斜线上的瓶子，一共55组，这样最坏情况有6组不能判断，这个比6*6优一点，但也没达到900，这个最多可以分成58组，55个用来排三角形，剩下三组不判断。不知道49楼的968能不能达到
接上，上面的斜线意思是第十行的点朝两个斜方向上的线
000个瓶，但是2瓶有毒，10个老鼠，一周时间，最多可以确定多少瓶没有毒？我知道一个可以确定900瓶没毒的方法，但不知道这个是不是最佳的了
此题还有一个延伸：
还是1000个瓶，但是2瓶有毒，10个老鼠，一周时间，最多可以确定多少瓶没有毒？
最多可以确定998瓶没毒。
@36楼: 非常受启发。另外由于取整缘故，4*4*5 情况下共80组，每组应混合 1000/(4*4*5)=12.5 即13份，最后结果是 1000-13*8=896瓶。
@48楼: 抱歉，刚刚漏看了你已经答过的896的答案了。
在上面的扩展问题中，目前的最好答案是4*4*5的方法896种，将1000瓶分成4*4*5=80组时，
会有40组是13瓶，40组是12瓶，把12瓶的组用x表示，13瓶的组用o表示。将每个4*4的平面如下排布
x x o x
x x o o
o o x o
x o o x
将这个平面叠五层形成的4*4*5分组，任取两行两列两纵相交的8个相交组，总有一组只有12瓶，
那么最坏的情况是能保证1000-(13*7+12)=897瓶是水。
这个思路好费脑，不懂做程序，用程序算或许能更多一些。
这里延伸出一个问题就是
对于一个n维的a1*a2*…*an空间格点，最少挖去多少个格点能使得：
任取两行两列两纵两…相交的2^n个格点中至少有m(1<=m<=2^(n-1))个格点被挖去了。
不错，赞👍