毒酒问题(加强版)
http://tieba.baidu.com/f?kz=587967375国王为10天后的生日宴会准备了1000桶酒，不幸的是，其中两桶被下了毒。为了确定两桶毒酒，有人提议用死刑犯试毒。毒的潜伏期为10天。有趣且有一定的难度
问:至少需要多少个死刑犯才能确保找出毒酒？方案如何实行？
（最新结果在 https://bbs.emath.ac.cn/thread-1511-18-1.html, 计算机搜索现在已知最优结果为27个死刑犯 ）
本题对应OEIS的链接为 A054961
并且提供了A054961不等价解的数目在A304041
有些意思，
对于任意2子集都存在集合，其并集是此2子集的补
由信息论易得要X>log2(C(1000,2))=18.9
具体构造还得再想想 确实蛮有意思的。
我只会从简单的来。
如果有3桶酒，就安排两个2人各选一桶试喝，余下那桶是否有毒得看10天后他们死不死；
如果有4桶酒，那就再安排一个人试喝；
如果有5桶酒，继续再增加一个人试喝；
如果有6桶酒，用4个死囚犯足够了吗？ 6桶酒4人不够 只是一个很粗糙的下界
向gxq一人一桶好像都是挺难突破的，想用一些已有的BIBD,但都超不过这个
有空再想 对于比较大的数目,突破一人一桶是很简单的.败毒上已经有人给出一种模型比如有$n^2$桶,那么
我们可以将它们排成$n**n$方阵,然后选n个人喝掉每一行,再另外选n个人喝掉每一列.
那么这时通常的结果是有两个选择行喝两个选择列的囚徒倒下,对应4个桶(分布在一个矩形的4个顶点,实际上应该选择一条对角线上的两个顶点).
为了能够区分这些这些顶点,我们最差情况在选择$2*n-1$个囚徒,让它们按斜线分配酒就可以了.这种方案只需要$4n-1$个囚犯可以区分$n^2$个酒桶.
而我们还可以将这个方案试着向高维推广 看如图形状的图,所有酒桶放在点上,每个囚徒喝一行直线.那么6a+3个囚徒可以识别$3a^2+3a+1$个酒桶 本帖最后由 到处瞎逛 于 2009-6-6 08:29 编辑
首先从二维的角度来考虑是46个人。
因为46条直线有1035个交点。
所以46个人可以通过其交点确定1036瓶酒到底是哪一瓶有毒。
我不能上传图片，它总是提示我图片格式不对，但是我就是很普通的png的格式。
所以不大好说明这个问题。
比如6瓶酒。4个人就可以了。http://www.mathchina.com/cgi-bin/attachment.cgi?forum=12&topic=700&postno=110&name=1_1244224552&type=.gif
喝的方法是a（1，2，3）
b（1,4,6）
c(2,5,6)
d(3,4,5)。
推广到三维，也就是求空间直线交点的问题。在往高维，复杂了，我猜想如下计算：
http://www.mathchina.com/cgi-bin/attachment.cgi?forum=12&topic=700&postno=110&name=1_1244247702&type=.gif
应该最少需要20个人。
头脑有点晕晕的，上面的图里面式子可能有些表达细节上的错误，但是应该就是那个意思了。 8# 到处瞎逛
你的浏览器可是 IE8？
不能上传图片的问题，前不久有人反馈过，
最终的原因却是 IE8 默认关闭了本地文件上传权限以提高安全性，
只要在其设定中再勾选一下即可，见：http://bbs.emath.ac.cn/viewthread.php?tid=1326&page=2&fromuid=8#pid17689 还真是这个原因。
我的IE是8.0的，现在好了，能上传文件了。