毒酒问题(加强版)

shshsh_0510

此法在$n=2^10$时为107似乎不如那个排成方阵的
但n比较大时就有优势了，比如$n=2^50=1125899906842624$
此时仅需2547，要远小于$(1125899906842624)^(1/2)$

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	?	?	?	?

mathe

然后对于每个数字,在表格中找到不小于这个数字的行号最小的格子.那么行号就是这个方法可以提供的最少的囚徒数.不过可惜我没有找到A(n,d,w)的近似公式,不然我们可以对它有更好的了解.
可以看到在同的数目k<=10时,这个方法不能给出比n=k-1更好的结果.
但是在k=63时n可以达到7707
k        n
12        9
13        10
17        11
20        12
26        13
28        14
42        15
48        16
68        17
69        18
76        19
84        20
120        21
176        22
253        23
254        25
257        26
278        27
296        28
300        29
327        30
362        31
403        32
442        33
494        34
555        35
622        36
696        37
785        38
869        39
965        40
1095        41
1206        42
1344        43
1471        44
1632        45
1795        46
1976        47

mathe

想了一下,shshsh_0510的拆分方法还是挺有用的.不过得到的结果应该是
$f(2x)<=f(x)+2+2g(x)$.
而对应的复杂度应该在$O(log^2(x))$
其最大的好处是给出了一个非常漂亮的复杂度估计式.
但是对于上面表格列出的数据没有改善作用.

mathe

根据那个表格上的页面,构造41个囚徒解决1000个酒桶问题,我们需要参考文章:
http://www.emis.de/journals/EJC/Volume_13/PDF/v13i1a2.pdf
附件是同一个文件.
v13i1a2.pdf (118.82 KB, 下载次数: 10)

2009-6-7 19:23 上传

点击文件名下载附件

文章里面应该提到一个Lexicographic code(字典顺序编码),
而产生这个数据需要使用reverse lexicographic code (反字典顺序编码)

shshsh_0510

25#mathe的计算是对的，20#我那个矩阵的检测n中有一个的部分有错，但比较容易改且不影响结论
11# mathe 的方法我没太明白，为什么问题就变成了“Packing K3 into Kn”？

mathe

先不要管Packing K3 into Kn 问题,直接采用A(n,d,w),注意下面这段话.

其中A(n,d,w)表示那些长度为n比特的二进制数(0开始的数是允许的)的集合的最大元素数目,要求满足集合中任何两个元素不同比特位数目不小于d,而每个二进制数正好有w比特为1. (也就是任意两个数相同比特位最多为w-d/2)"
那么对于A(n,w+1,w)中的方案(w为奇数),任何两个比特1数目为w的二进制数,不同的位置至少有w+1;也就是相同的比特1最多(w-1)/2个.
对应到本题,让A(n,w+1,w)桶酒分配给n个囚徒喝,其中n个比特位分别对应n个囚徒.A(n,w+1,w)中每个二进制数对应一桶酒.每个二进制数上比特1对应的囚徒要喝掉对应的酒.
那么如果某桶酒有毒,那么那个对应的二进制数所有比特1对应的囚徒必然死去.反之如果某桶酒无毒,那么由于总共只有两桶毒酒,所以这个无毒酒对应的二进制数最多有2*(w-1)/2=w-1个囚徒死去,也就是是说至少有一个囚徒没有死.
也就是我们可以根据每桶酒对应的二进制数所有比特1对应的囚徒是否全部死去来判断酒是否有毒.

mathe

关于A(n,w+1,w)的数目(w奇数),可惜我没有找到很好的下界.但是我们可以很容易给出一个下界.
我们对于n比特中的任意$(w-1)/2$比特,所有这$(w-1)/2$比特都为1的数字当中,余下的$(w+1)/2$比特必然互不相同,所以最多${2n}/{w+1}$个.n比特选择$(w-1)/2$有$C_n^{{w-1}/2}$种选择,而每个w比特数中选择${w-1}/2$比特有$C_w^{{w-1}/2}$比特.可以得到
$A(n,w+1,w)<={2n}/{w+1}*{C_n^{{w-1}/2}}/{C_w^{{w-1}/2}}$
记w=2t+1,得到$A(n,2t+2,2t+1)<={n*n!t!}/{(n-t)!(2t+1)!}$

mathe

虽然上面只是一个上界,但是我感觉应该同A(n,2t+2,2t+1)的真实值相差不远.那么让我们采用这个数据来估计这种方案能够达到的效果.对于给定的n我们要选择t使得A(n,2t+2,2t+1)最大,于是要求
${A(n,2t+2,2t+1)}/{A(n,2t,2t-1)}$接近1,也就是${(n-t-1)}/{2(2t+1)}=1$,也就是大概$t={n-3}/5$
而得到的结果是n个囚徒大概可以检测$A(n,2t+2,2t+1)={n*n!*t!}/{(n-t)!(2t+1)!}~=e*n*sqrt({nt}/{(n-t)(2t+1)})*{n^n*t^t}/{(n-t)^(n-t)(2t+1)^(2t+1)}$
即结果约为$e*n*sqrt(8/5)*(5/4)^n$
也就是$n~=C*log(k)/log(1.25)$