逻辑爆炸的数学题,本人又再次改编了,大家来讨论
国王的仓库有1000桶牛奶,有刺客在其中一桶中放了毒药,这种毒药不论稀释多少倍给老鼠喝了一周之后才能死亡,一周之后国王要用这些牛奶了,因此要在这一周之内找出哪一桶牛奶有毒,至少需要用多少只老鼠做测试?你知道吗,


一个国王有1000瓶红酒,并打算在他的六十大寿时打开来喝。不幸的是,其中有一瓶红酒被人下了毒,凡是沾到毒酒者大约20个小时后开始有异样并马上死亡(只沾到一滴也会死)。由于国王的大寿就在明天(离宴会开始只有24小时),就算有千分之一的可能国王也不想冒这个险,他要在宴会开始之前把毒酒找出来。所以,国王就吩咐侍卫用监牢里的死刑犯来检验毒酒。请问:最少需要多少个死刑犯才能检验出毒


第一个是我第一次看到的,第二个是搜答案看到的


第一个就是只有一次机会,不能一轮一轮,第二个有一段时间差,那第三种就是没有任何时间限制。


讲讲我的想法,第一种用坐标,三维很容易凑出30人这个答案,但是我看到有个不等式是算出1000维只要一只老鼠所以不知道了,第三种嘛,不知道坐标系和二进制哪个更屌
跪求计算机大神开发程序凑数

来自 科创茶话
2016-3-20 20:18:51
1楼
第一个问题,至多需要1000只。至少需要多少只?其实我们可以用二进制来解决,1和0两种状态对应老鼠的死活,刚好。
不如取个整数,有1024桶牛奶,上面都有编号。
这样我们就可以用10位2进制(0-1023),代表这1024种可能性。如果能确定这个二进制的每一位,就能找到对应的牛奶桶。
第一位:混合(0-511)桶,让老鼠测试。如果老鼠测试的结果是死了,那么第一位就是0,否则第一位就是1.
第二位:混合(0-255, 512-767)桶,……那么第二位就是0,否则第二位就是1.
……
第十位:混合所有偶数桶。……那么第十位就是0,否则第十位就是1.
最后将得到一串10位的二进制数,就是有毒牛奶桶的编号。


综上,至少需要10只老鼠。

真正的问题是,没有冰箱的鲜牛奶能放一周?
折叠评论
加载评论中,请稍候...
折叠评论
2楼
第二个问题的答案也是10个犯人。

真正的问题是,这个题目忽视受刑人员的基本人权。
折叠评论
加载评论中,请稍候...
折叠评论
3楼
增加尝试人数可以减少死亡数。
折叠评论
加载评论中,请稍候...
折叠评论
4楼
我来说2句。
第一,这个题描述不严密。国王要用,要用多少桶呢?全部吗?部分吗?
如果是用一部分,那么我有这个办法。把1000桶分成10份。每份100桶。然后分别从这10份中的100桶中分别取样品,然后混合。然后取10只老鼠,其中必然有一组有毒,这样必然死一只老鼠。

然后900桶牛奶就可以用了,剩下再筛查剩余的100桶,由于刚才死了一个老鼠,还剩下9只,所以补充1只。接着,再把这100桶嫌疑有毒的牛奶分成10份,每份10桶。
然后,每桶取样品,分别混合。然后分给10只老鼠,这次,必然会再死一只,然后嫌疑牛奶桶就剩下10桶。老鼠剩下9只,再补充一只老鼠。
然后分别取样品测试,这样必然再死一只。于是就鉴别出来了。这样使用老鼠总共12只。

以上就是我的答案。不知道对不对?
折叠评论
加载评论中,请稍候...
折叠评论
俗世怂人(作者)
5楼
注意注意,毒药发作是有时间期限的,要用酒也是有时间期限的。
如果说只用一桶,那最简单了,就用一只,死了不喝,没死喝。但是是要把有毒的确切是哪一桶找回来
折叠评论
加载评论中,请稍候...
折叠评论
俗世怂人(作者)
6楼
引用 novakon:
第一个问题,至多需要1000只。至少需要多少只?其实我们可以用二进制来解决,1和0两种状态对应老鼠的死活,刚好。
不如取个整数,有1024桶牛奶,上面都有编号。
这样我们就可以用10位2进制(0-1023),代表这1024种可能性。如果...
我主要是想问,如果用坐标,很容易就能用不等式来做A1A2A3A4...An=1000,求个A1加到AN的最小值,但是这样很容易算出最小是n分之(1000的n次方根,虽然我不会算,但是我会验证你的10是不是最小,带入10 ,显然不对)
折叠评论
加载评论中,请稍候...
折叠评论
俗世怂人(作者)
7楼
再说一遍有三种变形第一个就是只有一次机会,不能一轮一轮,第二个有一段时间差,那第三种就是没有任何时间限制
折叠评论
加载评论中,请稍候...
折叠评论
8楼
哦。我错了,至少用1只。
用1只去随机尝试,如果刚好喝到毒牛奶,那么就算鉴定出来了,这是最少的老鼠只数。虽然成功率低了点。



我这个是按照题意最优的答案,因为他只是问最少能鉴定出来毒牛奶的老鼠只数啊。我这个就是最少的可能性的答案。


假如他换个问法,问,必然可以鉴定出来结果的,那我的答案就是18只了。
折叠评论
加载评论中,请稍候...
折叠评论
俗世怂人(作者)
9楼
引用 x6x:
哦。我错了,至少用1只。
用1只去随机尝试,如果刚好喝到毒牛奶,那么就算鉴定出来了,这是最少的老鼠只数。虽然成功率低了点。
请用合理的逻辑也就是说,这个方法能100%的检测出
折叠评论
加载评论中,请稍候...
折叠评论
俗世怂人(作者)
10楼
引用 x6x:
哦。我错了,至少用1只。
用1只去随机尝试,如果刚好喝到毒牛奶,那么就算鉴定出来了,这是最少的老鼠只数。虽然成功率低了点。



我这个是按照题意最优的答案,因为他只是问最少能鉴定出来毒牛奶的老鼠只数啊。我这个就是最少的可能性的答...
18太多了,沙发10只一次解决了
折叠评论
加载评论中,请稍候...
折叠评论
11楼
引用 俗世怂人:
我主要是想问,如果用坐标,很容易就能用不等式来做A1A2A3A4...An=1000,求个A1加到AN的最小值,但是这样很容易算出最小是n分之(1000的n次方根,虽然我不会算,但是我会验证你的10是不是最小,带入10 ,显然不对)
我完全不明白你在讲什么。
折叠评论
加载评论中,请稍候...
折叠评论
2016-3-21 02:24:21
12楼
novakon的答案是正确的。
我来给大家做一下简单的推理。假设有十六桶奶,其中一桶有毒。
那么16log2=4只需要四只老鼠就可以一次试出。具体做法如下
把所有奶按照二进制编号从0000到1111共16桶
把所有编号第一位为一的奶取一滴放在一个新桶里。一共八滴。具体为1000 1001  1010 1011 1100 1101 1110 1111即第九至第十六桶奶
再把所有第二位为一的奶取一滴放在一起。以此类推。
最后配出四桶奶。
分别喂四只老鼠。
假如第一只和第二只死了,那么放在一起就是1100,也就是第1100转二进制+1即第13桶奶有毒。
推广到1024桶的情况是一样的。1000桶的话只需要跳过不存在的奶就行。
至于喝酒的问题,也是一样的解
折叠评论
加载评论中,请稍候...
折叠评论
俗世怂人(作者)
13楼
引用 novakon:
我完全不明白你在讲什么。
比如说二维就是1000桶尽可能拍成正方形那么一批老鼠一行行吃,一批一列列吃),三维就是螺一个正方体,加入第三批老鼠一层层吃,那如果排成四维的,五维,甚至更高的有没有可能呢,我觉得后面的有点想像困难了。所以我不知道这个行不行
折叠评论
加载评论中,请稍候...
折叠评论
14楼
引用 novakon:
第一个问题,至多需要1000只。至少需要多少只?其实我们可以用二进制来解决,1和0两种状态对应老鼠的死活,刚好。
不如取个整数,有1024桶牛奶,上面都有编号。
这样我们就可以用10位2进制(0-1023),代表这1024种可能性。如果...
好厉害,没想到, 还有更少的答案吗?
折叠评论
加载评论中,请稍候...
折叠评论
15楼
引用 俗世怂人:
比如说二维就是1000桶尽可能拍成正方形那么一批老鼠一行行吃,一批一列列吃),三维就是螺一个正方体,加入第三批老鼠一层层吃,那如果排成四维的,五维,甚至更高的有没有可能呢,我觉得后面的有点想像困难了。所以我不知道这个行不行
厉害 这也是一种解,而且只需要20只老鼠操作也简单
折叠评论
加载评论中,请稍候...
折叠评论
俗世怂人(作者)
16楼
第二个问题可以吧NOVAKON的后几位设置为时间,那么可以再减少几只
折叠评论
加载评论中,请稍候...
折叠评论
17楼
引用 俗世怂人:
比如说二维就是1000桶尽可能拍成正方形那么一批老鼠一行行吃,一批一列列吃),三维就是螺一个正方体,加入第三批老鼠一层层吃,那如果排成四维的,五维,甚至更高的有没有可能呢,我觉得后面的有点想像困难了。所以我不知道这个行不行
你的这个思路是正确的,如果推广到10维,就和我的方法原理上一致了。我把1024桶排成了10维立方体,从10个方向吃过去,每个方向有两列。由于每个方向上的两列,只有其中一列含有有毒牛奶,所以每一个方向(维度)上只需要一只老鼠就可以测试出两列中的哪一列含有毒牛奶。10个方向(维度)总共就需要10只。
折叠评论
加载评论中,请稍候...
折叠评论
俗世怂人(作者)
18楼
引用 novakon:
你的这个思路是正确的,如果推广到10维,就和我的方法原理上一致了。我把1024桶排成了10维立方体,从10个方向吃过去,每个方向有两列。由于每个方向上的两列,只有其中一列含有有毒牛奶,所以每一个方向(维度)上只需要一只老鼠就可以测试出两列中...
原来如此超过10维已经没有意义了,其实我在思考第二题24小时要用20小时会死,时想到将服用时间也做一个标记作为一个维度,那时我就想到了其实你的二进制和我的应该是一样的了
折叠评论
加载评论中,请稍候...
折叠评论
19楼
引用 novakon:
第一个问题,至多需要1000只。至少需要多少只?其实我们可以用二进制来解决,1和0两种状态对应老鼠的死活,刚好。
不如取个整数,有1024桶牛奶,上面都有编号。
这样我们就可以用10位2进制(0-1023),代表这1024种可能性。如果...
极寒地区,哈哈
折叠评论
加载评论中,请稍候...
折叠评论
20楼
标题太夸张了,逻辑没有爆炸。这道题目难不倒理工科本科生。
我是学通信工程的,首先想到的是用信息论来解题。

为楼主补充一些定义:我们假设牛奶每次只能取一桶,国王拒绝多桶牛奶混合。无法通过除了老鼠试验之外的其他措施确定是否有毒。
国王想要获得信息,确认哪一份牛奶有毒药。一只老鼠只能提供很少一些信息,不足以进行判断。需要多个老鼠,才能凑齐需要的信息量。



这是离散变量信息熵(信息量)的计算公式。假设变量X有i个符号x1~xi,第i个符号xi出现的概率为P(xi)。b与信息量的单位有关,b=2时信息量单位为比特bit
国王想知道的答案,可以表示为一个坐标变量X,取值范围整数1-1000。这样就是1000个符号,每个等概率1/1000
因此国王需要的信息量H(X)=-1000*1/1000*log2(1/1000)=9.9658bit
每个老鼠的情况记为变量Y,取值0无毒,1有毒,概率各50%,因此每个老鼠能提供的信息量H(Y)=1bit
H(X)/H(Y)=9.965,取最小正整数10,即最小10只老鼠。
至于怎么安排试验,题目没问,我这里也不写了。
以上的计算不需要考虑试验过程。不管过程如何,信息量的限制是突破不了的。
反之,如果信息量足够了,合理安排过程(可能非常复杂),总是可以解出结果的。


扩展2个鬼畜问题:
如果每年这样做1000次试验,平均每次消耗多少只老鼠?
如果国王允许用多桶牛奶合并得到1桶可用的牛奶,平均每次又会消耗多少只老鼠?
+1  学术分    虎哥   2016-03-21   终于有人推导理论极限了。
折叠评论
加载评论中,请稍候...
折叠评论
俗世怂人(作者)
21楼
引用 warmonkey:
标题太夸张了,逻辑没有爆炸。这道题目难不倒理工科本科生。
我是学通信工程的,首先想到的是用信息论来解题。

为楼主补充一些定义:我们假设牛奶每次只能取一桶,国王拒绝多桶牛奶混合。无法通过除了老鼠试验之外的其他措施确定是否有毒。
国王...
感谢版主为我等高中生打开了新世界的大门
折叠评论
加载评论中,请稍候...
折叠评论
22楼
第一题1K桶奶的问题可以倒过来想,就是多少个老鼠的不同死法能有1K种以上,10只编号的老鼠会有1024种死法(全不死1种,死一只10种,死两只45种... ...)死法一共是2^(老鼠个数)种死法,每一种死法对应一桶牛奶,所以需要10只老鼠
折叠评论
加载评论中,请稍候...
折叠评论
23楼
如果刺客在其中10瓶下了毒会怎么样?
折叠评论
加载评论中,请稍候...
折叠评论
24楼
还有第二题,第二题第一批中毒毒发时间和宴会时间有时间差,(楼主应该明确毒药的精确度,例如假设毒药精确到小时,那么实验每一小时可进行一次,宴会之前20-23小时之间能收集四次实验结果,也就是刚开始能分别隔一小时进行四次试验)可以利用这段时间差将实验分批进行,如果每个老鼠都是能显示是否中毒又不死的体制,那么四批实验就需要3只老鼠就够了,但是问题在于中毒老鼠以后无法再进行是否有毒的显示,需要重新计算,结果应该在3-10之间,这个计算让我有点懵逼,求帮忙。
折叠评论
加载评论中,请稍候...
折叠评论
2016-3-22 08:15:41
25楼
引用 碧浪格拉斯:
我想问一下,假设有4桶牛奶,按照您的方法,搞成二进制就是2位,难道用2只最少就能分辨有毒的那个吗?
桶分为A、B、C、D,老鼠分为一号二号,一号喝A、B的混合物,二号喝A、C的混合物,
那么若一号死二号没死,就是B有毒
一号死二号死就是A有毒
一号没死,二号死就是C有毒,
一号二号都没死就是D有毒
综上所述,两只老鼠能唯一确定4个桶中哪个桶有毒
折叠评论
加载评论中,请稍候...
折叠评论
26楼
对于第二题有时间差的,如果说从毒发到宴会能收集5次数据(20-24),每小时收集一次,那么总体需要4只老鼠就够了,每只老鼠对应6种状态,分别是没死、20小时时死、21小时时死、22小时时死、23小时时死、24小时时死。那么四只老鼠所能对应的桶数为6^4=1296,满足题的桶数,综上所述,如果分5次喂,每隔一小时喂一次,再分5次收集数据,那么需要4只老鼠就够了

以上思路借鉴于群里大神
折叠评论
加载评论中,请稍候...
折叠评论
27楼
引用 usafn6132:
对于第二题有时间差的,如果说从毒发到宴会能收集5次数据(20-24),每小时收集一次,那么总体需要4只老鼠就够了,每只老鼠对应6种状态,分别是没死、20小时时死、21小时时死、22小时时死、23小时时死、24小时时死。那么四只老鼠所能对应的...
关键是增加每只老鼠能提供的信息量,定位毒药位置需要的信息量是固定的,能变化的只有老鼠了。
折叠评论
加载评论中,请稍候...
折叠评论
28楼
如果用不等式解的话当是A^n>=M,其中A代表一个事件的结果可能情况,在这里表示一只老鼠死或不死两种情况,则A取2,n表示事件的个数,这里实指使用老鼠的个数,M表示n个事件所产生的结果总数,这里带入酒的桶数1000,由于n要取正整数,所以得到n等于10.
折叠评论
加载评论中,请稍候...
折叠评论
29楼
引用 warmonkey:
关键是增加每只老鼠能提供的信息量,定位毒药位置需要的信息量是固定的,能变化的只有老鼠了。
不大明白,不过如果进行多次分批采集数据,每只老鼠提供的信息量会增加吧?
折叠评论
加载评论中,请稍候...
折叠评论
30楼
引用 usafn6132:
不大明白,不过如果进行多次分批采集数据,每只老鼠提供的信息量会增加吧?
老鼠死/活,只有2个状态0/1,信息量1bit

你说的方法,换个解释:
老鼠死的时间,相当于增加了4个状态,0(活)/1/2/3/4/5,总共有6个状态,信息量2.585bit

前面计算需要9.9685bit信息量才能定位毒酒
不同老鼠死亡没有相关性,互信息为0
9.9685/2.585=3.856,即4只老鼠
折叠评论
加载评论中,请稍候...
折叠评论
31楼
引用 warmonkey:
老鼠死/活,只有2个状态0/1,信息量1bit

你说的方法,换个解释:
老鼠死的时间,相当于增加了4个状态,0(活)/1/2/3/4/5,总共有6个状态,信息量2.585bit

前面计算需要9.9685bit信息量才能定位毒酒
不同老鼠...
哦哦,是的,感觉这种算法好厉害
折叠评论
加载评论中,请稍候...
折叠评论
32楼
引用 usafn6132:
哦哦,是的,感觉这种算法好厉害
如果死掉的时间不是很精确,有可能发生混淆。那可以用概率分布算出实际信息量,进而给出无偏差判断的方法[s::lol] 不过那个就太复杂了

这个其实跟通信是一样的,信号有噪声干扰,有可能发生误码,需要各种纠错算法……
折叠评论
加载评论中,请稍候...
折叠评论
33楼
第一种情况,时间有限制,所以要一次性能检测出1000瓶中哪个有毒。
最多老鼠要用1000只,每个瓶子都对应一只。
要想减少老鼠使用就要给瓶子分组,把分组的瓶子混合后给一只老鼠。
并且要保证每个瓶子被混合2次,这样才能毒死2只老鼠,确认唯一的毒瓶子。

这样最优方法 1000瓶子 分32组,每组32个瓶子(部分31瓶),  这样分组2次。

那么结果就是最少需要64只老鼠. 其中2只会被毒死。
折叠评论
加载评论中,请稍候...
折叠评论
34楼


   试样总量   维度   每个维度需要的老鼠   进一法取整
   1000   1   1000   1000
   1000   2   31.6227766   32
   1000   3   10   10
   1000   4   5.623413252   6
   1000   5   3.981071706   4
   1000   6   3.16227766   4
   1000   7   2.682695795   3
   1000   8   2.371373706   3
   1000   9   2.15443469   3
   1000   10   1.995262315   2
   1000   11   1.873817423   2
   1000   12   1.77827941   2
   1000   13   1.70125428   2
   1000   14   1.637893707   2
   1000   15   1.584893192   2
   1000   16   1.539926526   2
   1000   17   1.501310729   2
   1000   18   1.467799268   2
   1000   19   1.438449888   2
   1000   20   1.412537545   2
         ……  
         ……  
         ……  
   1000   1000   1.006931669   2




仔细想了一下,如旁边这个表。
这个就是用维度来解决的方法。
1维需要1000只,这个就不用讨论了。
2维是做成正方形,每条边放32只,多余的位放空。32*2=64只
3维是立方体,正好每条边10只老鼠。10*3=30只
以此类推,10维的时候要每个维度2只老鼠,也就是2*10=20只。
再往下计算,到1000维也需要放2只老鼠到每个维度。

[修改于 4 年前 - 2016-03-22 21:58:41]

折叠评论
加载评论中,请稍候...
折叠评论
35楼
再看看二进制的解法,牛奶编号1~1024,其中1001~1024为空。
0 000 000 000
0 000 000 001   第1桶取一部分给低位的老鼠;
0 000 000 010   第2桶取一部分给第二位的老鼠;
0 000 000 011  第3桶取一部分给低两位的老鼠;
0 000 000 100  第4桶取一部分给第三位的老鼠;
0 000 000 101  第5桶取一部分给标记为1的老鼠;
0 000 000 110  第6桶取一部分给标记为1的老鼠;
0 000 000 111  第7桶取一部分给标记为1的老鼠;
0 000 001 000  第8桶取一部分给标记为1的老鼠;
…………
…………
…………


以此类推,最后数死老鼠的位就知道是第几桶牛奶有毒了。
折叠评论
加载评论中,请稍候...
折叠评论
2016-3-23 10:34:09
36楼
引用 warmonkey:
标题太夸张了,逻辑没有爆炸。这道题目难不倒理工科本科生。
我是学通信工程的,首先想到的是用信息论来解题。

为楼主补充一些定义:我们假设牛奶每次只能取一桶,国王拒绝多桶牛奶混合。无法通过除了老鼠试验之外的其他措施确定是否有毒。
国王...
你好  羡慕你的数学功底,如果刺客在10罐牛奶里面下了毒是不是该这样算呢?
-1000*(1/100)*log(1/100)/log(2)≈66.439
最少需要67个老鼠,但是具体怎么操作,这又是个问题了。

[修改于 4 年前 - 2016-03-23 11:16:05]

折叠评论
加载评论中,请稍候...
折叠评论
37楼
第一个问题,实际上可以转化为n维空间来处理。在n维空间,唯一确定空间的一个点,需要n个参数。所以,这个题可以转化为m的n次方大于等于1000,求min(m+n),在本题中,可以得出,最小的m+n=9(4的5次方=1024),所有,有9个人就够了。
第二个问题,如果时间精确的话,一个人就够了。这个人每隔时间t喝一滴n号瓶子的酒,只要1000t<24-10,那么,只要计算这个人什么时间死亡,就可以得出到底是哪瓶酒有毒。
折叠评论
加载评论中,请稍候...
折叠评论
38楼
引用 novakon:
第一个问题,至多需要1000只。至少需要多少只?其实我们可以用二进制来解决,1和0两种状态对应老鼠的死活,刚好。
不如取个整数,有1024桶牛奶,上面都有编号。
这样我们就可以用10位2进制(0-1023),代表这1024种可能性。如果...
太6
折叠评论
加载评论中,请稍候...
折叠评论
39楼
有错误。

[修改于 4 年前 - 2016-03-23 15:33:17]

折叠评论
加载评论中,请稍候...
折叠评论

想参与大家的讨论?现在就 登录 或者 注册

插入资源
全部
图片
视频
音频
附件
全部
未使用
已使用
正在上传
空空如也~
上传中..{{f.progress}}%
处理中..
上传失败,点击重试
{{f.name}}
空空如也~
(视频){{r.oname}}
{{selectedResourcesId.indexOf(r.rid) + 1}}
ID:{{user.uid}}
{{user.username}}
{{user.info.certsName}}
{{user.description}}
{{format("YYYY/MM/DD", user.toc)}}注册,{{fromNow(user.tlv)}}活动
{{submitted?"":"投诉"}}
请选择违规类型:
{{reason.description}}
支持的图片格式:jpg, jpeg, png