毒酒问题(加强版)

毒酒滴冻鸭

说说我想到的17人试出64桶中2桶毒酒的方法：

首先留1桶全部不喝，剩下63桶排成7x9方阵。7横行坐标只需6人试（126,135,234,147,257,367），9直列坐标只需7人试（123,456,789,147,258,369,159），这样可以试出横行和直列坐标各1或2个。

如果横行或直列坐标其中只有1个，那么答案立刻出来了，否则我们有2x2的两个对角可能性。

那么我们再i派4人事先这样试酒：

040123321
104012332
210401233
321040123
332104012
233210401
123321040

这样就可识别任何2x2对角。。。所以合共用了6+7+4=17人。。。

毒酒滴冻鸭

楼上是二维的方法，其实三维的方法也可达致17人，如下：

还是留1桶全部不喝，剩下63桶排成7x3x3立体方阵。7横行坐标只需6人试（126,135,234,147,257,367），3直列和3平层各用3人试，这样可以试出横行、直列、平层坐标各1或2个。

另外3直列和3平层组成的3x3方阵（每个元素包含7横行共7桶酒），我们只需1人试对角线：
100
010
001

而7横行和3直列、3平层分别组成的两个7x3方阵（每个元素包含3桶酒），我们各派2人如下试对角线：
0001212
0120021
0212100

如此合共用了6+3+3+1+2+2=17人。。。

毒酒滴冻鸭

如果增加一人至18人，那么上面这系统最多可试出82桶酒中的两桶毒酒（当然用随机算法算出的结果可能远远不止此数），方法就是二维排成9x9方阵（7+7+4=18）或四维的3x3x3x3方阵（共有C(4,2)=6个复合3x3方阵要试对角线，所以所需人数=4*3+6*1=18）。

所以很好奇，用mathe站主的随机解法15、16、17、18人分别可以达致怎样的数量？

mathe

现在感觉73#的方案有问题，以110#中例子，如果是第一行第三行，第二列和最后一列，得到四个交点有三个分在同一组，所以无法区分，有问题

mathe

7楼的方法可以在3倍的h(37)个人识别1028桶，估计h(37)=13,如果这样得出39人方案，不知道推广到三维会如何，应该可以考虑正八面体结构

mathe

两瓶毒酒只能在四桶中对角出现，所以73#的方案没有问题

毒酒滴冻鸭

以下是用三人确定4x13矩阵对角线的系统：

0 000 123 123 123
0 123 000 231 312
0 231 312 000 231
0 312 231 312 000

建构方法看似很简单但是很容易触礁，如果想照板煮碗套用到5x21或6x31的话会死得很难看。。。

ahyyz2008

好贴，涨姿势了，这么牛逼的解法，我还真没见过，佩服众位大神

mathe

毒酒滴冻鸭 发表于 2014-11-20 16:40
请问64桶酒，其中两瓶有毒，16人能试出来吗？我只能想到17人的解法。。。

另外16桶酒，最少应该确定是9 ...

16 人可以识别出正好包含两瓶毒酒的67瓶酒，这是用计算机随机搜索找到的
288 9040 7008 9490 4270 1220 2401 805 c201 1449 a810 c836 395 a08e 5920 64 d21 4560 820 81 1018 90a 8402 c4a4 d012 1550 a06 4290 821a 22c4 1380 4848 f40 20a2 c150 a211 8644 7804 a106 4063 8882 29 3803 2017 2152 c302 4328 2430 4411 6c40 3980 6622 1406 3045 2168 8c0 9c08 e009 3214 46a 400e 584 61c0 c52 d14 50c2 a224

mathe

在人数比较少时，两瓶毒酒问题的搜索算法竟然可以和果树问题非常类似。
双方问题最关键的都是搜索过程会出现大量同构的树，如果不过滤掉这些同构的树会导致大量重复搜索
所以我采用果树问题中类似算法，采用bliss库来过滤同构的树，得出8个人的确只能最多验证13瓶正好包含两瓶毒酒情况，其中有两种不同的验证方法。
不过输出记号和本贴的其它部分不同，采用类似果树问题中方法，分别用字母A,B,C,D等代表第0，1，2，3比特是1（也就是字母出现对应比特为1，不出现，对应比特为0),而特殊的，所以比特都是0的情况用当个字母O代替，那么8个验证13瓶本质上只有两组解:
G H BD AF CE ABC DEF AEG BFG CDG ADH BEH CFH
O BD AF CE GH ABC DEF AEG BFG CDG ADH BEH CFH
其中第二种方案去掉O,对应8个人验证12瓶包含一瓶或两瓶毒酒的情况