毒酒问题(加强版)

mathe

http://tieba.baidu.com/f?kz=587967375

国王为10天后的生日宴会准备了1000桶酒，不幸的是，其中两桶被下了毒。为了确定两桶毒酒，有人提议用死刑犯试毒。毒的潜伏期为10天。

问:至少需要多少个死刑犯才能确保找出毒酒？方案如何实行？


（最新结果在 https://bbs.emath.ac.cn/thread-1511-18-1.html, 计算机搜索现在已知最优结果为27个死刑犯 ）

本题对应OEIS的链接为 A054961
并且提供了A054961不等价解的数目在A304041

Rime997

mathe 发表于 2009-6-11 08:45
这下在Sloane网站中找到位置了:
https://oeis.org/A054961
根据A054961,有

您好！想问一下为什么这个问题和“N个二进制码两两按位或不相同，编码最短几位”这个问题是等价的？

SunGame

这道题难就难在两瓶毒酒。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位二进制数，确定两桶酒是哪两桶。  

毒酒滴冻鸭

aimisiyou 发表于 2020-3-24 11:05
嗯，是我转换错误了，把12转化为0001100了。不知能不能利用矩阵递推构造法？随机算法的运算量太大了。

七人测十坛有一个很直观的方案，不过貌似跟站主这里的方案结构不同。

直观方案是：把九坛酒按3x3矩阵摆放，然后三人分别试三行，三人分别试三列，一人试正对角线。

1. aaa
   
2. bbb
   
3. ccc
   
4. 
   
5. def
   
6. def
   
7. def
   
8. 
   
9. g..
   
10. .g.
    
11. ..g

复制代码

八人试十三坛貌似也有几何结构上对称的方案，不过不太记得了，有空再研究一下。。。

其实真正厉害的是九人试十七坛，因为那个不能有一坛没人试，所以结构非常难组织出来，除了编程估计只有超级天才才能凭空用人脑设计出来。。。

aimisiyou

毒酒滴冻鸭 发表于 2020-3-24 10:16
你可能看错或理解错了？该矩阵对应的二进位配毒表如下：

如果是第5、9坛（12、54）有毒，死况为：死活 ...

嗯，是我转换错误了，把12转化为0001100了。不知能不能利用矩阵递推构造法？随机算法的运算量太大了。

毒酒滴冻鸭

aimisiyou 发表于 2020-3-13 15:30
7人识别10坛酒的矩阵不正确(00   03  05   09     12    24   38    48    54     62)，若出现（死，活 ...

你可能看错或理解错了？该矩阵对应的二进位配毒表如下：

1. .......
   
2. .....11
   
3. ....1.1
   
4. ...1..1
   
5. ..1..1.
   
6. .1..1..
   
7. .111...
   
8. 1..1...
   
9. 1.1.1..
   
10. 11...1.

复制代码

如果是第5、9坛（12、54）有毒，死况为：死活死活死死活；如果是第8、9坛（48、54）有毒，死况为：死活死死死活活。两者是能被分辨的。

aimisiyou

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

mathe 发表于 2019-12-24 08:02
你的链接无法访问。
手工构造本论坛应该只达到33人，我觉得很难进一步改进。
可以查看 https://emathgrou ...

7人识别10坛酒的矩阵不正确(00   03  05   09     12    24   38    48    54     62)，若出现（死，活，死，死，死，活 ，活）的结果，无法判断是第5坛酒和第9坛酒有毒，还是第8坛酒和第9坛酒有毒。

mathe

https://quuxplusone.github.io/blog/code/2020-01-10-wolfy-out.txt
记录了一些两瓶以及更多毒酒问题的记录，昨天将我们的数据也添加了

https://quuxplusone.github.io/bl ... -sheep-with-tables/

mathe

你的链接无法访问。
手工构造本论坛应该只达到33人，我觉得很难进一步改进。
可以查看 https://emathgroup.github.io/blog/two-poisoned-wine ，这里面的内容整理过了，看起来更加方便些，当然细节还得从本论坛找。