|
发布时间: 2009-6-5 14:11
正文摘要:http://tieba.baidu.com/f?kz=587967375 国王为10天后的生日宴会准备了1000桶酒，不幸的是，其中两桶被下了毒。为了确定两桶毒酒，有人提议用死刑犯试毒。毒的潜伏期为10天。 问:至少需要多少个死刑犯才能确保找出 ... |
| 这道题难就难在两瓶毒酒。1000桶酒可以用十位二进制数来表示。这十位分成5段两位二进制数，每一段可以分成四部分，用3个囚犯试第0，1，2部分，如果2个囚犯中毒，则第3部分无毒，否则是未定状态。为了把这5段的连接关系确定，又要在间隔处左右各取1位二进制数，间隔段0的D0=A0^A1,D1=A2，间隔段1的D0=A3,D1=A4^A9,间隔段2的D0=A0^A5,D1=A6,间隔段3的D0=A7,D1=A8^A9，又用3名囚犯，5段加4段再乘以3，总共27名囚犯。至于第3部分状态未定时，只要一级一级下去，在哪一级出现2名囚犯中毒，就可以确定前面的所有未定状态。最多到最后一级，总归可以确定。这样就能得到10位二进制数，确定两桶酒是哪两桶。 |
本帖最后由 毒酒滴冻鸭 于 2020-4-2 11:16 编辑 aimisiyou 发表于 2020-3-24 11:05 七人测十坛有一个很直观的方案，不过貌似跟站主这里的方案结构不同。 直观方案是：把九坛酒按3x3矩阵摆放，然后三人分别试三行，三人分别试三列，一人试正对角线。
八人试十三坛貌似也有几何结构上对称的方案，不过不太记得了，有空再研究一下。。。 其实真正厉害的是九人试十七坛，因为那个不能有一坛没人试，所以结构非常难组织出来，除了编程估计只有超级天才才能凭空用人脑设计出来。。。 |
本帖最后由 aimisiyou 于 2020-3-24 11:09 编辑 毒酒滴冻鸭 发表于 2020-3-24 10:16 嗯，是我转换错误了，把12转化为0001100了。不知能不能利用矩阵递推构造法？随机算法的运算量太大了。 |
aimisiyou 发表于 2020-3-13 15:30 你可能看错或理解错了？该矩阵对应的二进位配毒表如下：
如果是第5、9坛（12、54）有毒，死况为：死活死活死死活；如果是第8、9坛（48、54）有毒，死况为：死活死死死活活。两者是能被分辨的。 |
|
本帖最后由 aimisiyou 于 2020-3-13 20:12 编辑 8人识别13坛酒的矩阵也不正确(00 03 0C 15 26 38 49 52 60 8A 90 A1 C4)。若出现（活，死，死，活，死，死，死，死）的情况，将无法判断是第5坛酒和第7坛酒有毒，还是第4坛酒和第9坛酒有毒。若出现（活，活，活，死，死，死，死，死）的情况，也无法判断哪两坛酒有毒（可能是第1坛和第4坛，或者第2坛和第4坛，或者第3坛和第4坛）。 |
本帖最后由 aimisiyou 于 2020-3-13 18:24 编辑 mathe 发表于 2019-12-24 08:02 7人识别10坛酒的矩阵不正确(00 03 05 09 12 24 38 48 54 62)，若出现（死，活，死，死，死，活 ，活）的结果，无法判断是第5坛酒和第9坛酒有毒，还是第8坛酒和第9坛酒有毒。 |
|
https://quuxplusone.github.io/blog/code/2020-01-10-wolfy-out.txt 记录了一些两瓶以及更多毒酒问题的记录，昨天将我们的数据也添加了 https://quuxplusone.github.io/bl ... -sheep-with-tables/ |
|
你的链接无法访问。 手工构造本论坛应该只达到33人，我觉得很难进一步改进。 可以查看 https://emathgroup.github.io/blog/two-poisoned-wine ，这里面的内容整理过了，看起来更加方便些，当然细节还得从本论坛找。 |
|
在另外一个论坛发现了这个问题，搜了一下居然回来了哈哈 那边有人同样给出了27个人的构造方法 因为我好久没关注数学相关东西了就先不在这里叙述 过段时间先爬完本帖再说 传送门：https://bbs.nga.cn/read.php?tid=19718634&_ff=-7 （楼主是我） |
小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )
GMT+8, 2024-4-20 07:44 , Processed in 0.047059 second(s), 20 queries .
Powered by Discuz! X3.5
© 2001-2024 Discuz! Team.
