趣题:老鼠与毒药问题的推广

    今天的趣题来源于 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 个瓶子中检验出毒药来。

87 条评论

  • Proton

    话说前几天刚刚看到这个问题 不过是国王和士兵版的

  • aihorn_mac

    科学的力量啊!

  • mewing

    屌爆了
    那一下的转折还是没有反应过来啊……

  • Vera

    啊呀~这个问题的推广版真是进制的妙用啊~
    乍一看觉得跟离散数学里面的什么有点相像,一时想不起来。。

  • pl

    老鼠喝那么多水 不会撑死吗?

  • yh

    无责任吐槽:其实应该说,任何喝下毒药的生物都会在一星期之内的任何一个时候死亡
    不然总是准确的在一星期之后死的话,一只足够了。。

  • mingz

    从另一个角度看也可以的:
    1号老鼠喝:1-500号瓶子
    2号老鼠喝:1-250号,501-750号
    3号老鼠喝:1-125号,251-375号,501-625号,751-875号
    依次分下去….

  • wuyongzhouling

    现在发现脑子不够用了

  • 青山客

    。。。不错,的确是一只老鼠就够了

  • 荷尔萌

    第一次来说句话。

  • yac

    此题还有一个延伸,我现在还不知道答案,这里请教下:
    还是1000个瓶,但是2瓶有毒,10个老鼠,一周时间,最多可以确定多少瓶没有毒?我知道一个可以确定900瓶没毒的方法,但不知道这个是不是最佳的了

  • Gavin

    我一开始也把这题当“脑筋急转弯”了,如果老鼠准确的在一个星期后死亡的话,一只足够

    “任何喝下毒药的生物都会在一星期之后死亡”这个题干没啥意义,反而诱使人想歪,不如直接在问题中表明:“只能做一轮实验”、“只能做两轮实验”

    to mingz:那样要多少个星期才能得到结果啊……

  • Gavin

    to mingz:是我想错了

    你的这个想法和 hamming码 如出一辙

  • yac

    忘了说,12楼2瓶有毒10只老鼠那题是高盛的面试题。

  • gad

    有意思,前些天听他们讨论了,看了这篇文章,又有收获,
    只用一只的,不知道想的怎么样的歪?

  • D-Horse

    从生物学角度分析一只老鼠就行。。取成年性成熟公老鼠一只,取其睾丸内大量精虫(百万单位总有了吧)。。- -然后把这些精虫平均分成N份(比如文中的1000份),然后放入毒液中。。估计一天就能检测出效果了吧。。检测各个毒液中的精虫活性即可。。(哈哈,我这个是搞笑的哈~)

  • biohu

    这种毒药的LD50的倒数等于+∞

  • Marco

    这么说1000个星期一只老鼠就能知道哪个瓶子有毒了?怎么做到的能说说不

  • 看看

    “不然总是准确的在一星期之后死的话,一只足够了”这个关键在于,准确二字吧,是用时间轴来做标签鉴别吧?

  • Booster

    非常好,很好的编码思想啊!

  • farseerfc

    一只老鼠……每分钟给老鼠喝一个瓶子……在开始试验的(10080+x)分钟后死亡,x是瓶子编号……试验需要总时间是1周+16小时40分钟……

  • 雷神

    太经典了,,,,喜欢

  • exp618

    to 22L
    不如每秒喝一瓶,试验后(604800+x)秒后死亡,x是瓶子编号

  • kkcocogogo

    为何这类问题总需转化为二进制才得解?
    数学问题按理说应该和进制无关吧?
    十进制下有无方案?

  • kkcocogogo

    另,评论的时候响应奇慢,点击两次以上显示已评论,但是没看见我那层楼?!并且仅是wordpress下的问题
    求解

  • sai

    在一轮的情况下其实就是在10个元素的子集个数内都可以

  • 杨梦达

    楼上900瓶怎么解的,说说~

  • error 404

    为什么又是小白鼠,可怜的小白鼠……用生命换来的只一个编码,在三进制的情况下还不确定……

  • Peter Pan

    我只做到840瓶,900瓶的牛人能解释下么~

  • yac

    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是不是最优解。

  • LaoLiulaoliu

    我发现弄一个5*5的矩阵可以推出920瓶没毒的。
    每个格子放40瓶,5个老鼠喝横行,5只喝竖行。第三排,第二列的40瓶里面有一瓶有毒,就能确认是喝第三排和喝第二列的两只老鼠死掉了,这样可以发现5*5的矩阵中的两处毒药,一共80瓶。所以能够确定920瓶是没毒的。

  • LaoLiulaoliu

    我发现弄一个5*5的矩阵可以推出920瓶没毒的。
    每个格子放40瓶,5个老鼠喝横行,5只喝竖行。第三排,第二列的40瓶里面有一瓶有毒,就能确认是喝第三排和喝第二列的两只老鼠死掉了,这样可以发现5*5的矩阵中的两处毒药,一共80瓶。所以能够确定920瓶是没毒的。
    如果推广到三维,3*3*4 ,一个格子可以放28瓶,最后可以确定944瓶没毒的。
    不知道有没有问题。

  • morrowind

    即使老鼠准确的在一个星期后死亡的话,一只也是不够的。
    既然死亡时间让你准确算了,那么题目所问的“一星期的时间,如何检验出哪个瓶子里有毒药”同样也是严格的一个星期,多了一秒钟也是错误答案。
    所以题目没有任何歧义。

  • 广告可耻,屁民可怜。

    微博营销

    承接微博推广,刷粉丝、转发、评论、认证等业务。
    QQ 2232388982

    粉丝量太少?
    转发量太少?
    回复量太少?
    还没有认证?
    专业微博团队一条龙服务,解决您的上述烦恼。
    我们团队覆盖
    腾讯微博,
    新浪微博,
    搜狐微博,
    网易微博,
    凤凰微博,
    饭否微博。
    现承接个人或企业网路推广业务,老团队,信得过。
    QQ 2232388982

  • yac

    @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瓶没毒

  • yac

    上贴最后一句是4*4*5,只能确定900瓶没毒

  • liushuoshu

    @36楼: 2维情况是这样,3维的情况下一个格子所在的三个方向都死了只有两种可能,1这个格子有毒,2这个格子没有毒但是三个方向上各有一瓶毒药,可是毒药一共只有两瓶,不会出现这种情况,所以这个格子一定有毒

  • liushuoshu

    如果按照3*3*4这个方向推的话,三维的时候是不能留空的,因为留空的部分会降为2维,存在和2位同样的混淆问题,也就是说只能分成3*3*4,但是可以单独先拿出28瓶来放在外面,不喝,于是剩下972瓶正好等于27*3*3*4,每格27瓶,可验出945瓶无毒,比944多一瓶

  • 熊猫

    我想说,这个题目是没有答案的。你只有一个星期的时间。而老鼠要一个星期死,所以你的时间不够。。

  • LaoLiulaoliu

    @36楼:5*5分析的很对,谢谢。没明白6*6和4*4*5是怎么来的,按照我的思路,那就分别需要12和13只小白鼠了。
    @38楼:@39楼:我觉得你分析的有道理。

  • LaoLiulaoliu

    @38楼:你把3*3*4 简化成2维,还是会有 36楼所说的4瓶中无法确定2瓶的情况。

  • orcwind

    @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.

  • yac

    @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

  • yac

    续44楼,当然6*6的话,每一维只分5只老鼠,余下的空着。三维的话,老鼠按334来分配,每一维还是有一个空位

  • liushuoshu

    哦对,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貌似无法构图

  • liushuoshu

    哦46楼的构图不对,只能减到3倍混淆,那么重新计算一下按照27*35+55分堆,最坏情况下只能识别895瓶,看来要重新搞一下构图

  • yac

    @47楼,我想了很久了,按照这样factorial design的方法,三维4*4*5应该是最佳解,即至少可以确定900瓶梅毒(当然如果取整的话,至少896瓶)。再想得到更优解,可能要考虑别的思路了,但我还没想到

  • morrowind

    对于“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个老鼠,一周时间,最多可以确定多少瓶没有毒这样的理论值。

  • yac

    @49楼,有趣,从没想到过这个方法,这也是我提出这个问题的初衷,找到自己想不到的思路。不过我对信息论是门外汉,能具体解释一下那个不等式什么意思吗?多谢

  • morrowind

    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)
    展开就是上面的不等式了。

  • Peter Pan

    确实啊,空位这个设定很精髓!受教了。

  • morrowind

    最后那个公式有点笔误,应该是
    log2( C(1000,2) ) – log2( C(1000-x,2) ) <= 10

  • billbargens

    那1000瓶毒药,但2瓶有毒,一周时间,需要多少只老鼠才能确定哪两瓶有毒??怎么设计方案嘞???

  • LaoLiulaoliu

    @43楼:比如毒药为(1,2,3)和(2,3,4),6只老鼠死亡,只能有4种可能吧。
    把毒药为(1,2,3)和(2,3,4)想象成一个正方体,8个点组成的正方体只有对角线的两瓶才能让这6只老鼠死亡,而对角线只有4对,也就是说只有4种可能?

  • wyhao31

    @55楼,对角线是只有4对,但你没法确定哪一对是毒药,所以这8瓶都没法确认没毒

  • LenenTom

    第一个链接挂掉了。

  • mathxingkong

    这次lz给的答案不是最优解了,其实只需要6只老鼠。从信息论来说,二进制才是最优的,可以最大程度的获得信息。1000进行二进制编码,第一个星期6只老鼠可以确定二进制的前6位,除去死掉的一只,第二星期用5只老鼠确定二进制的后4位。在两星期内N只老鼠可以判定的毒药瓶数为2^(2N-1),同理,t星期内N只老鼠可以判定2^(t*(2N-t+1)/2)瓶。

  • 杨军军

    主要建立老鼠死亡状态和瓶子的一一对应关系。

  • Peter Pan

    58楼,你确定第一轮只会死掉一只么。死掉0~6只都是可能的

  • 我快疯掉了

    那要是1024个瓶子就不能用二进制算了?

  • 过客

    非常厉害!

  • albine

    如果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的面试题

  • giant

    两个星期不是应该可以做8轮实验的吗?9进制的话只要4只老鼠。

  • 水人业美

    这是决策树吗

  • trek jerseys

    这个有学过 蛮不错的

  • MForever

    真NB啊,必须MARK

  • hlily

    又找到一道,被用来作为笔试,面试的题。。

  • Shalaey

    实际上你知道,我有一个同学给出了更另人称奇的做法
    他的解法实在是……
    我们当时面对的是国王的1000瓶酒和10个死刑犯,我很快给了那个二进制的做法,但是那个同学说,只要一个死刑犯就足够了
    对应到小白鼠上,他的解法是这样的:7*24*60*60=604800
    因此每隔10分钟喂小白鼠舔一下,并计时
    一个星期后看小白鼠什么时候毒发身亡,于是我们找到了毒药……
    这个答案我实在不好评判,但是佩服他的思维,所以来发个贴……

  • jun

    刚刚想了一下,1000个水瓶里面有n个有毒的话,要多少只老鼠才可以在一周之内找到所有的毒瓶子呢?答案是log_2{1000Cn} 进一。原理是:1000只瓶子里面只有一个有毒的时,我们用老鼠的生死作为一个符号,来分辨1000种不同的情况。现在我们要做的,只是要在1000Cn种不同的情况里面找到其中一种而已。由此可以推导出其他很多情况的公式了吧。。

  • tw

    @48楼 我重新构造了一个结构,三角形,十行,从一到十,每个老鼠喝两条斜线上的瓶子,一共55组,这样最坏情况有6组不能判断,这个比6*6优一点,但也没达到900,这个最多可以分成58组,55个用来排三角形,剩下三组不判断。不知道49楼的968能不能达到

  • tw

    接上,上面的斜线意思是第十行的点朝两个斜方向上的线

  • cervelo

    000个瓶,但是2瓶有毒,10个老鼠,一周时间,最多可以确定多少瓶没有毒?我知道一个可以确定900瓶没毒的方法,但不知道这个是不是最佳的了

  • 小池

    此题还有一个延伸:
    还是1000个瓶,但是2瓶有毒,10个老鼠,一周时间,最多可以确定多少瓶没有毒?
    最多可以确定998瓶没毒。

  • bian

    @36楼: 非常受启发。另外由于取整缘故,4*4*5 情况下共80组,每组应混合 1000/(4*4*5)=12.5 即13份,最后结果是 1000-13*8=896瓶。

  • bian

    @48楼: 抱歉,刚刚漏看了你已经答过的896的答案了。

  • zhanpin

    在上面的扩展问题中,目前的最好答案是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瓶是水。

    这个思路好费脑,不懂做程序,用程序算或许能更多一些。

  • zhanpin

    这里延伸出一个问题就是
    对于一个n维的a1*a2*…*an空间格点,最少挖去多少个格点能使得:
    任取两行两列两纵两…相交的2^n个格点中至少有m(1<=m<=2^(n-1))个格点被挖去了。

发表评论