毒酒问题(加强版)

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

mathe

6桶酒4人不够

mathe

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

mathe

8#的结果是不行的.结果会不可判断.
倒是如果三条直线交于一点就可以唯一判断结果了.
由此,如果我们将问题化为对偶问题,就是每条直线上三个点,1000条直线,那么至少需要多少个点呢?
那么这个正好是种树问题每行三颗树1000行的结果.
根据http://mathworld.wolfram.com/Orchard-PlantingProblem.html
我们取$[1/6(k-1)(k-2)]>=1000$的k就可以了.得出79个死囚是可以的.
不过这里,平面约束是没有必要的,所以我们可以将问题改成Packing $K_3$ into $K_n$的问题,结果要稍微好一些.
不过这些结果都同7#的结果很类似,对于n桶酒,大概需要$sqrt(6n)$个死囚.这个看来基本是二维模型的极限了.
不知道如果采用三维模型能够提高到什么程度

mathe

11#里可以利用Packing $K_3$ to $K_n$的结论构造一些解.这个相当于页面
http://www.research.att.com/~njas/codes/Andw/index.html#dist4
中的A(n,4,3)
而同样,如果我们考虑A(n,6,5),A(n,8,7),A(n,10,9),等等,都可以转化为这个问题的解(相当于利用更高阶图的结果)
其中A(n,d,w)表示那些长度为n比特的二进制数的集合的最大元素数目,其中集合中任何两个元素不同比特位数目不小于d,而每个二进制数正好有w比特为1.
那么对于A(n,w+1,w)中的方案(w为奇数),任何两个比特1数目为w的二进制数,不同的位置至少有w+1;也就是相同的比特1最多(w-1)/2个. 对应到本题,让A(n,w+1,w)桶酒让n个囚徒喝,其中n个比特位分别对应n个囚徒.每个二进制数对应一桶酒.每个二进制数上比特1对应的囚徒要喝掉对应的酒.
那么如果某桶酒有毒,那么那个对应的二进制数所有比特1对应的囚徒必然死去.反之如果某桶酒无毒,那么由于只有两桶毒酒,所以这个对应的二进制数最多有2*(w-1)/2=w-1个囚徒死去.
也就是我们可以根据每桶酒对应的二进制数所有比特1对应的囚徒是否全部死去来判断酒是否有毒.
表格中A(n,4,3)仅列到n=64,而对应值为661,也就是说64个囚徒才可以识别661桶酒.
而如果我们查看A(n,6,5),那么可以发现n=48是,A(48,6,5)=1030,也就是说,这个方案中48个囚徒就可以识别1030桶酒.
而表格A(n,8,7)中,n=41时,结果为1095,也就是说41个囚徒就可以了.
而在查看A(n,10,9)中,仅列到n=43,但是结果才841说明再增加w需要囚徒数目又要增加了.
所以我们通过这个方法,可以得出一种41个囚徒解决1000个酒桶的方案.

mathe

看来是错了，但是24一共能表达16种状态，而C（6，2）=15所以肯定4个人是够了的。
是不是将15种组合方式按照二进制分配一下就可以了。没时间考虑了，这几天还去要去工地。
到处瞎逛 发表于 2009-6-6 12:11

虽然能够表达16种状态,但是不一定就能充分利用.
我用计算机穷举过,6个酒桶时4个人是不够的.
同样可以验证,7个酒桶时5个人也不够(不过这个计算量已经非常大了,我的计算机好像花费了1天多时间)

mathe

设n桶中有两桶毒酒需要f(n)人判定，n桶中有1桶毒酒需要g(n)人判定

一个人喝x桶，则可能分为3种情况：
1 此人死，在其喝的x中有2，共C(x,2)种
2 此人死，在其喝的x中有1,共x(n-x)
3 此人不死，在其未喝的n-x中有 ...
shshsh_0510 发表于 2009-6-6 23:58

问题在于要求同时喝酒,而不能第一次判断有了结果以后再做第二次判断.

mathe

看来是错了，但是24一共能表达16种状态，而C（6，2）=15所以肯定4个人是够了的。
是不是将15种组合方式按照二进制分配一下就可以了。没时间考虑了，这几天还去要去工地。
到处瞎逛 发表于 2009-6-6 12:11

直接证明4个人不能达到6桶酒的目标也不难.
对于4个人,所有子集有16种.
但是如果6桶酒的某一个组合(i,j)被映射到空集,那么就说明如果i,j都是毒酒,所有的人都不会死,也就是说所有的人都没有喝i,j这两桶酒.于是,如果毒酒是(i,k),那么只有喝了桶k里的酒的人会死去,我们无法区分(i,k)和(j,k).所以必然没有组合被映射到空集.
而对于6桶酒中的某两个组合(i,j)和(s,t),如果分别被映射到单元素集{u},{v}.
也就是如果i,j两桶有毒,只有第u个人死去;如果s,t两桶酒有毒,只有第v个人死去
而i,j,s,t中,最多两个数相同,也就是至少包含了3桶酒.
如果i,j,s,t四个数都不相同,很容易得出矛盾.
于是我们得出i,j,s,t中有一个数相同,表明这桶酒没有人喝过,不凡设j=t,也就是第j桶酒没有人喝.u喝了i,v喝了s.
同样,对于余下两个人构成的单元数集{w},{x},我们还可以找到三个数(三桶酒)i',j',s',其中w喝了i',x喝了s',j'没有人喝.于是j=j'.
于是我们得出5桶酒已经有了分配情况.j每人喝,i只有u喝了,s只有v喝了,i'只有w喝了,s'只有x喝了.
容易看出余下那桶酒无论如何分配,总会出现不可以识别的情况

mathe

还是感觉不对.不知道你怎么能够构造出来的.
而且你上面的数据也挺难验证的,最好你自己可以检验一下.
如果成立,也就是说任意不同两列的并得到的值全部必须不同.

mathe

将我15#方法的结果整理一下.那些对应的A(...)下界表格如下:

	A(n,4,3)	A(n,6,5)	A(n,8,7)	A(n,10,9)	A(n,12,11)	A(n,14,13)	A(n,16,15)
6	4.a
7	7.SS
8	8.c	2	1
9	12.s	3	1
10	13.s	6.s	1
11	17.s	11.c	2
12	20.s	12.c	3	1
13	26.c	18.s	4	1
14	28.s	28.s	8.s	2	1
15	35.s	42.s	15.c	3	1
16	37.s	48.s	16.c	4	1	1
17	44.s	68.SS	24.ec	6	2	1
18	48.s	69AC	33s	10.s	3	1	1
19	57.c	76c	52s	19.c	3	1	1
20	60.s	84c	80.s	20c	5	2	1
21	70.s	108Nu	120.s	27pc	7	3	1
22	73.s	132m	176.s	35pc	12.s	3	1
23	83.s	147t2	253.s	45pc	23.c	4	2
24	88.s	168s	253	56c	24c	6	3z13
25	100.c	210.s	254x2	72ec	36ec	8	?
26	104.c	260.s	257y	91Nu	39q2	14.s	4z13
27	117.s	260	278y	118Nu	54c	27.s	5z13
28	121.z3	280Nu	296y	132pc	65Nu	28c	7z13
29	134.z3	234s	300xr	96s	47s	19z13	8Gj
30	140.z3	272Gj	327xr	65z13	58s	22z13	15z13
31	155.z3	311xG	362xr	77z13	72s	30z13	15Gj
32	160.z3	337xG	403xr	167s	87s	33z13	19z13
33	176.z3	302s	442xr	198s	106s	?	?
34	181.z3	334s	494xr	232s	129s	?	?
35	197.z3	367s	555xr	273s	155s	?	?
36	204.z3	402s	622xr	320s	?	?	?
37	222.z3	441s	696xr	372s	?	?	?
38	228.z3	480s	785xr	430s	?	?	?
39	247.z3	523s	869xr	493s	?	?	?
40	253.z3	569s	965xr	570s	?	?	?
41	272.z3	616s	1095xr	651s	?	?	?
42	280.z3	666s	1206xr	742s	?	?	?
43	301.z3	720s	1344xr	841s	?	?	?
44	308.z3	777s	1471xr	?	?	?	?
45	330.z3	836s	1632xr	?	?	?	?
46	337.z3	898s	1795xr	?	?	?	?
47	359.z3	962s	1976xr	?	?	?	?
48	368.z3	1030s	?	?	?	?	?
49	392.z3	1100s	?	?	?	?	?
50	400.z3	1173s	?	?	?	?	?
51	425.z3	1250s	?	?	?	?	?
52	433.z3	1332s	?	?	?	?	?
53	458.z3	1414s	?	?	?	?	?
54	468.z3	1501s	?	?	?	?	?
55	495.z3	1591s	?	?	?	?	?
56	504.z3	1686s	?	?	?	?	?
57	532.z3	1782s	?	?	?	?	?
58	541.z3	1884s	?	?	?	?	?
59	569.z3	1992s	?	?	?	?	?
60	580.z3	2100s	?	?	?	?	?
61	610.z3	2215s	?	?	?	?	?
62	620.z3	2333s	?	?	?	?	?
63	651.z3	3906s	7182s	?	?	?	7707s
64	661.z3	?	8064s	?	?	?	?