毒酒问题(加强版)

倪举鹏

大家玩10滴水游戏么  据说要用遗传算法   谁可以编程找最优解

倪举鹏

我觉得30人可以  10人放X轴上  10人放Y轴上  10人放Z轴上，每人喝100桶    一桶毒酒死会毒死3人  两桶毒死最多6人    XYZ坐标确定了就确定酒桶位置了

补充内容 (2014-1-3 18:41):
页数太多，没有注意  看看我发的帖子，扩展到多维空间

倪举鹏

mathe 发表于 2009-6-5 17:47
对于比较大的数目,突破一人一桶是很简单的.败毒上已经有人给出一种模型比如有$n^2$桶,那么
我们可以将它们 ...

搞编程的呀，我不怎么会编程跟模拟  算算这样，假如不知道1000里面有多少桶毒酒，那么最少需要多少人将所有毒酒试出来？是不是需要1000人才保险呢

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桶毒）。

mathe

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

realnumber

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

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

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;我错了，还是区分不出来。

毒酒滴冻鸭

请问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。。。

毒酒滴冻鸭

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

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

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

毒酒滴冻鸭

mathe站长请看：

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

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

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