毒酒问题--求解惑

geslon

关于精华帖【毒酒问题】，我刚刚开始关注和尝试研究这个问题，有几个想法不知道对不对。 1，如果是1000桶里面仅有1桶毒酒，就需要10个人就够了。（这个估计诸位达人早就有结论了。）因为2^10=1024大于1000，所以每桶酒编一个号码从1到1000，并转换成10位数的二进制编码，第一个囚犯喝所有第一位是1的桶，第二号喝所有第二位是1的桶，…………，最后就能确定是哪一桶有毒。（哈哈，如果有囚犯喝多了醉死或者撑死怎么办？？？） 2，如果是1000桶里有两桶毒酒，就有C(1000,2)种组合，这个数小于2^19。也就是说，理论上19是可能的（18绝对不可能）。但是我们也发现，由于利用上有重复，目前我们发现的最好结果是math今天刚发的32人的方案。能有这么多的冗余么？

KeyTo9_Fans

$19$人确实有可能，但如果你算一下可行的概率，就发现这个概率几乎是$0$： $19$人有可行方案的概率为$1/10^179377$。 $20$、$21$、$22$、$23$人有可行方案的概率仍然接近$0$。 $24$人有可行方案的概率很大，几乎是$1$，但由于可行方案所占的比例几乎是$0$，我们很难找到它们。 当人数增加至$32$人时，可行方案所占的比例是$1/4119363614315$。 这么低的概率都被mathe找到了，说明要不就是mathe的运气特别好，要不就是mathe有很好的构造答案的技巧。

geslon

Fans超版，弱弱的问一下：你的可行方案概率是怎么算出来的？ 可行方案概率和可行方案所占比例，这两个分别是什么数学意义？

xbtianlang

1000份酒，分给32人喝。每份酒分给不同的若干人喝，每个人喝若干份不同的酒。 其中，分给6人喝的有20份，依次是 7: 78, 8: 178, 9: 228, 10: 231, 11: 151, 12: 73, 13: 30, 14: 10 ,15: 1 每个人喝酒的份数为： 1: 315 2: 327 3: 358 4: 328 5: 345 6: 327 7: 322 8: 325 9: 353 10: 290 11: 335 12: 375 13: 226 14: 238 15: 264 16: 272 17: 356 18: 249 19: 209 20: 186 21: 294 22: 285 23: 286 24: 295 25: 309 26: 294 27: 286 28: 308 29: 302 30: 289 31: 290 32: 296 由此可见，十天后这32人中的大部分将会死去（如果是999人喝，最多死2人），这个代价有点大。 现在问题是，这些数据是否可以再优化，尽量使死人的概率降低（每个人喝的份数尽量少）？！是否可用31人鉴别毒酒。

mathe

我用的就是另外一个链接中39#文章中方法对于固定部分稍微改变一下然后余下用随机方法得到的。能够算到32人有一定的运气因素，1000桶酒是现在能够得出的最优结果，实际上平均结果估计也就900多一些。 而33人那个算法就相对比较容易得出，实际上33人用这个算法现在已经可以达到1196桶酒。 而至于是否存在31人的方案，我相信应该会存在，只是这种算法基本上也无能为力了，需要更加好的构造方法才行。比如可以尝试部分构造以后，余下部分用计算机穷举或启发算法搜索，应该会有更好的结果。实际上，如果用现在的算法9个囚徒只能找到13桶酒（实际上13桶酒8个囚徒就够了，说明这个算法离最优解还是有一定距离的） 至于xbtianlang 提到的问题，显然为了减少囚徒数目，必然会增加死亡的数目。从概率上来说，如果为囚徒总数目最少，平均每个人喝酒数目应该在喝掉总数的$1-{sqrt(2)}/2$和$1/3$之间为最佳，所以死亡概率必然不低

KeyTo9_Fans

OEIS上有没有这样一个数列：用$a(n)$表示$n$个囚徒最多可以区分多少桶酒？ 如果没有，希望能创建一个。

mathe

OEIS上有没有这样一个数列：用$a(n)$表示$n$个囚徒最多可以区分多少桶酒？ 如果没有，希望能创建一个。 KeyTo9_Fans 发表于 2011-8-20 23:16

http://bbs.emath.ac.cn/viewthrea ... fromuid=20#pid19550 A054961