毒酒问题(加强版)

毒酒滴冻鸭

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

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

毒酒滴冻鸭

楼上是二维的方法，其实三维的方法也可达致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人。。。

毒酒滴冻鸭

说说我想到的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人。。。

毒酒滴冻鸭

mathe站长请看：

按照73#楼的方法，如果是14x14方阵：

01234567654321
10123456765432
21012345676543
32101234567654
43210123456765
54321012345676
65432101234567
76543210123456
67654321012345
56765432101234
45676543210123
34567654321012
23456765432101
12345676543210

那么试对角线的这7个人最多有4人会死，例如第45横行，第13直列。。。这样的情况不能当7桶中2桶有毒那样优化吧？

毒酒滴冻鸭

tannis_jin 发表于 2009-6-16 20:34
将之前的平面方案推广到立体：
列成10×10×10的方阵。
行，列，高各派8人（应该能更少）

我认为这个10人确定对角线的假设并不严谨，目测最少也需要15、16人的样子。

可以从4x4x4立方阵看看，4人是不可能确定的，最少也要6人。。。

毒酒滴冻鸭

请问64桶酒，其中两瓶有毒，16人能试出来吗？我只能想到17人的解法。。。

另外16桶酒，最少应该确定是9人了吧？

知道1000桶酒的目前已知最优解为32人，但是我之前着力研究1024桶酒的问题，目前应该还是33人吧？（电脑随机解法）

我比较有兴趣研究人脑能直观看出来的解法，目前最多能想到36人。。。74#楼mathe站主说的33人解法貌似不行，因为tannis_jin那个32*32对角线分16种情况，不可能用9人识别，因为这16种情况最少有1人死最多有4人死，而C(16,4)=1820已经大于2^9=512。。。

realnumber

比如国王共16桶酒，其中2桶毒，分成ABCD四组，依次为A1,A2,A3,A4,B1,B2,B3,.....,D3,D4
4+4=8人，其中4人分别喝A,B,C,D四组的酒，另四人分别喝1，2，3，4的酒（每人都喝了原始的四桶混合的酒）
10天后，ABCD至少死2个（比如AC），2桶毒酒就在这2组，1234也至少死2个(比如1，4)。
那么毒酒是A1A4C1C4;我错了，还是区分不出来。

realnumber

mathe 发表于 2014-5-28 21:58
你需要的是4桶有一桶或俩桶有毒情况的分析，三人不够，需4人

4人的话，按上面步骤20人就能区分1032桶中的2桶毒酒。
我再想想：应该还能减1人，也就是19人；或104楼方案增1人，16人。

mathe

你需要的是4桶有一桶或俩桶有毒情况的分析，三人不够，需4人

realnumber

这样可不可以，有没按题目规则来？目前结果是14人。
4桶中2桶毒酒，区分需要3人。
那么把1032桶酒，等分成256个小组，每小组4桶，依次标记为1，2，3，4，所有标记为1的256桶取样混合后让一人喝下，2，3也一样，需要3人，标记为4的256桶不需要取样喝。这样256个小组每组4桶酒取样混合，形成新的256桶酒。
现在的问题就是：已经预计消耗3人和区分新的256桶酒（最多含2桶毒酒）
再重复一次以上步骤，得6人和区分64桶酒（最多含2桶毒酒，可以满足10日一次鉴别要求，都事先标记好，后面同），继续重复一次，9人和区分16桶酒，再次，12人和区分4桶，15人。

如果是3桶中2桶毒酒，区分需要2人。按以上办法，需要14人区分\(3^7=2187\)桶酒（其中2桶毒）。