毒酒问题--求解惑
关于精华帖【毒酒问题】，我刚刚开始关注和尝试研究这个问题，有几个想法不知道对不对。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 于 2011-8-16 00:59 编辑
$19$人确实有可能，但如果你算一下可行的概率，就发现这个概率几乎是$0$：
$19$人有可行方案的概率为$1/10^179377$。
$20$、$21$、$22$、$23$人有可行方案的概率仍然接近$0$。
$24$人有可行方案的概率很大，几乎是$1$，但由于可行方案所占的比例几乎是$0$，我们很难找到它们。
当人数增加至$32$人时，可行方案所占的比例是$1/4119363614315$。
这么低的概率都被mathe找到了，说明要不就是mathe的运气特别好，要不就是mathe有很好的构造答案的技巧。 Fans超版，弱弱的问一下：你的可行方案概率是怎么算出来的？
可行方案概率和可行方案所占比例，这两个分别是什么数学意义？ 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人鉴别毒酒。 我用的就是另外一个链接中39#文章中方法对于固定部分稍微改变一下然后余下用随机方法得到的。能够算到32人有一定的运气因素，1000桶酒是现在能够得出的最优结果，实际上平均结果估计也就900多一些。
而33人那个算法就相对比较容易得出，实际上33人用这个算法现在已经可以达到1196桶酒。
而至于是否存在31人的方案，我相信应该会存在，只是这种算法基本上也无能为力了，需要更加好的构造方法才行。比如可以尝试部分构造以后，余下部分用计算机穷举或启发算法搜索，应该会有更好的结果。实际上，如果用现在的算法9个囚徒只能找到13桶酒（实际上13桶酒8个囚徒就够了，说明这个算法离最优解还是有一定距离的）
至于xbtianlang 提到的问题，显然为了减少囚徒数目，必然会增加死亡的数目。从概率上来说，如果为囚徒总数目最少，平均每个人喝酒数目应该在喝掉总数的$1-{sqrt(2)}/2$和$1/3$之间为最佳，所以死亡概率必然不低 OEIS上有没有这样一个数列：用$a(n)$表示$n$个囚徒最多可以区分多少桶酒？
如果没有，希望能创建一个。 OEIS上有没有这样一个数列：用$a(n)$表示$n$个囚徒最多可以区分多少桶酒？
如果没有，希望能创建一个。
KeyTo9_Fans 发表于 2011-8-20 23:16 http://bbs.emath.ac.cn/images/common/back.gif
http://bbs.emath.ac.cn/viewthread.php?tid=1511&page=7&fromuid=20#pid19550
A054961
页:
[1]