毒酒问题(加强版)

mathe

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

shshsh_0510

有些意思，
对于任意2子集都存在集合，其并集是此2子集的补
由信息论易得要X>log2(C(1000,2))=18.9
具体构造还得再想想

gxqcn

确实蛮有意思的。

我只会从简单的来。
如果有3桶酒，就安排两个2人各选一桶试喝，余下那桶是否有毒得看10天后他们死不死；
如果有4桶酒，那就再安排一个人试喝；
如果有5桶酒，继续再增加一个人试喝；
如果有6桶酒，用4个死囚犯足够了吗？

mathe

6桶酒4人不够

shshsh_0510

只是一个很粗糙的下界
向gxq一人一桶好像都是挺难突破的，想用一些已有的BIBD,但都超不过这个
有空再想

mathe

对于比较大的数目,突破一人一桶是很简单的.败毒上已经有人给出一种模型比如有$n^2$桶,那么
我们可以将它们排成$n**n$方阵,然后选n个人喝掉每一行,再另外选n个人喝掉每一列.
那么这时通常的结果是有两个选择行喝两个选择列的囚徒倒下,对应4个桶(分布在一个矩形的4个顶点,实际上应该选择一条对角线上的两个顶点).
为了能够区分这些这些顶点,我们最差情况在选择$2*n-1$个囚徒,让它们按斜线分配酒就可以了.这种方案只需要$4n-1$个囚犯可以区分$n^2$个酒桶.
而我们还可以将这个方案试着向高维推广

zed

看如图形状的图,所有酒桶放在点上,每个囚徒喝一行直线.那么6a+3个囚徒可以识别$3a^2+3a+1$个酒桶

到处瞎逛

首先从二维的角度来考虑是46个人。

因为46条直线有1035个交点。

所以46个人可以通过其交点确定1036瓶酒到底是哪一瓶有毒。

我不能上传图片，它总是提示我图片格式不对，但是我就是很普通的png的格式。

所以不大好说明这个问题。

比如6瓶酒。4个人就可以了。

喝的方法是a（1，2，3）
b（1,4,6）
c(2,5,6)
d(3,4,5)。

推广到三维，也就是求空间直线交点的问题。在往高维，复杂了，我猜想如下计算：


应该最少需要20个人。
头脑有点晕晕的，上面的图里面式子可能有些表达细节上的错误，但是应该就是那个意思了。

gxqcn

8# 到处瞎逛

你的浏览器可是 IE8？

不能上传图片的问题，前不久有人反馈过，
最终的原因却是 IE8 默认关闭了本地文件上传权限以提高安全性，
只要在其设定中再勾选一下即可，见：http://bbs.emath.ac.cn/viewthrea ... ;fromuid=8#pid17689

到处瞎逛

还真是这个原因。
我的IE是8.0的，现在好了，能上传文件了。