10000桶酒,其中1桶是毒酒;48小时后要举行酒会…. 小白鼠试毒酒问题

问题描述

10000桶酒,其中1桶是毒酒;48小时后要举行酒会;毒酒喝下去会在之后的第23-24小时内毒死人;国王决定用囚犯来试酒,不介意囚犯死多少,只要求用最少的囚犯来测试出哪一桶是毒酒,问最少需要多少囚犯才能保证找出毒酒?
BTW:
1. 毒酒喝到就必死,一点点都不行,一个毒酒分子的剂量喝到了都必死好嘛。。。
2. 大家看清题啊,2天内必须找出来,还有1天的毒发周期,找不出来国王的酒会没法办了
3. 死的人是没办法继续验酒的
4. 必须验出具体是哪一桶酒,其他9999桶酒酒会上都会被喝掉,少一桶都不行,不然酒不够,酒会上和酒会后国王请来的贵宾不允许出任何事故
5. 方案必须能保证到最后一定能验出来,毕竟任何极端情况都有可能,绝对不能靠运气,国王的酒会输不起,只有2天时间

先看个简单例子

有8个一模一样的瓶子,其中7瓶是普遍的水,有一瓶是毒药。任何喝下的生物都会在一星期之后死亡。现在,你只有3只小白鼠和一星期时间,如果检验出哪个瓶子里有毒药?

解决方法

其实就是利用3只小白鼠来混合喝不同的水,以实现找出毒药的问题。

三只小白鼠标号为1、2、3。

八瓶水按二进制进行编号:

000
001
010
011
100
101
110
111

我让标号为1的小白鼠喝最低为1的水,即001、011、101、111
标号为2的小白鼠喝次低位为1的水,即010、011、110、111
标号为3的小白鼠喝最高位为1的水,即100、101、110、111

设一星期后小白鼠死亡为1,活着为0,则标号321的小白鼠状态即是有毒的水
如三只小白鼠都活着,则000是有毒的水,3号小白鼠死了,其它小白鼠活着则100是有毒的水。

同理,我们可以用n个小白鼠来一次验证2的n次方瓶水。

小白鼠试毒酒

小白鼠试毒酒

回到原题

一定要注意友情提示(BTW,by the way)里所说的
1. 毒酒喝到就必死,一点点都不行,一个毒酒分子的剂量喝到了都必死好嘛。。。
1000万桶毒酒嘛,为了混合让不同的人喝,这只是个前提
2. 大家看清题啊,2天内必须找出来,还有1天的毒发周期,找不出来国王的酒会没法办了
3. 死的人是没办法继续验酒的
4. 必须验出具体是哪一桶酒,其他9999桶酒酒会上都会被喝掉,少一桶都不行,不然酒不够,酒会上和酒会后国王请来的贵宾不允许出任何事故
5. 方案必须能保证到最后一定能验出来,毕竟任何极端情况都有可能,绝对不能靠运气,国王的酒会输不起,只有2天时间
第2、3、4、5条,要求1天内必须所有的酒都试完,第二天是毒发周期用来检验结果,所以是不能使用二分法的,第5条也规定一定要检测出来,也就是要考虑最坏的情况

错误的解法

既然是这样,第一天有24小时,10000/24=416.666667,取417,也就是每一个小时要验证417瓶酒才能完成这个任务,设2的n次方>=417,n为9。

操作如下:

  1. 将1000瓶酒分组,每组417,可能最后一组少一些,每组酒都用二进制进行编号并进行记录
  2. 9个囚犯编号1-9,每次都喝一点酒二制编号对应的第1-9位为1的酒,并进行记录
  3. 第二天,第k时有囚犯死亡,则根据23-24时的发作时间向前推导出那一组酒y,设囚犯死亡为1,不死亡为0,则编号1-9的囚犯生存状态,对应二制编号的1-9进行0或1的标记,最后得出二进制t,则y组编号为t的酒就是毒酒。

错误的原因

这种解法的原因,是对时间的利用不充分。开始的小白鼠的简单案例是没有时间概念的,就是一次要检测出来,所以引入了二进制的标记位的概念。

最优解法

但这个题,从0时刻到24时刻,可以实验25次。对一个人来说,它的实验刻度就是25。

其实每个人可以看作是一个维度,那需要几个维度来确定那瓶酒有毒呢?

25的n次方要大于等于10000,n=3。

比较直观通俗的解释就是:
把酒桶排成25*25*25(XYZ)的阵列,每个小时让三个囚犯每人喝一整平面 (XY、XZ、YZ)的混合酒,三个囚犯必须都会死,记录死时的xyz值,其坐值就是有毒的酒。

未经允许不得转载:开心猿社区 » 10000桶酒,其中1桶是毒酒;48小时后要举行酒会…. 小白鼠试毒酒问题

赞 (1)

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址