本帖最后由 shshsh_0510 于 2009-6-7 16:25 编辑
此法在$n=2^10$时为107似乎不如那个排成方阵的
但n比较大时就有优势了，比如$n=2^50=1125899906842624$
此时仅需2547，要远小于$(1125899906842624)^(1/2)$
还是感觉不对.不知道你怎么能够构造出来的.
而且你上面的数据也挺难验证的,最好你自己可以检验一下.
如果成立,也就是说任意不同两列的并得到的值全部必须不同.
将我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)64.a77.SS88.c21912.s311013.s6.s11117.s11.c21220.s12.c311326.c18.s411428.s28.s8.s211535.s42.s15.c311637.s48.s16.c4111744.s68.SS24.ec6211848.s69AC33s10.s3111957.c76c52s19.c3112060.s84c80.s20c5212170.s108Nu120.s27pc7312273.s132m176.s35pc12.s312383.s147t2253.s45pc23.c422488.s168s25356c24c63z1325100.c210.s254x272ec36ec8?26104.c260.s257y91Nu39q214.s4z1327117.s260278y118Nu54c27.s5z1328121.z3280Nu296y132pc65Nu28c7z1329134.z3234s300xr96s47s19z138Gj30140.z3272Gj327xr65z1358s22z1315z1331155.z3311xG362xr77z1372s30z1315Gj32160.z3337xG403xr167s87s33z1319z1333176.z3302s442xr198s106s??34181.z3334s494xr232s129s??35197.z3367s555xr273s155s??36204.z3402s622xr320s???37222.z3441s696xr372s???38228.z3480s785xr430s???39247.z3523s869xr493s???40253.z3569s965xr570s???41272.z3616s1095xr651s???42280.z3666s1206xr742s???43301.z3720s1344xr841s???44308.z3777s1471xr????45330.z3836s1632xr????46337.z3898s1795xr????47359.z3962s1976xr????48368.z31030s?????49392.z31100s?????50400.z31173s?????51425.z31250s?????52433.z31332s?????53458.z31414s?????54468.z31501s?????55495.z31591s?????56504.z31686s?????57532.z31782s?????58541.z31884s?????59569.z31992s?????60580.z32100s?????61610.z32215s?????62620.z32333s?????63651.z33906s7182s???7707s64661.z3?8064s????
然后对于每个数字,在表格中找到不小于这个数字的行号最小的格子.那么行号就是这个方法可以提供的最少的囚徒数.不过可惜我没有找到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
想了一下,shshsh_0510的拆分方法还是挺有用的.不过得到的结果应该是
$f(2x)<=f(x)+2+2g(x)$.
而对应的复杂度应该在$O(log^2(x))$
其最大的好处是给出了一个非常漂亮的复杂度估计式.
但是对于上面表格列出的数据没有改善作用.
根据那个表格上的页面,构造41个囚徒解决1000个酒桶问题,我们需要参考文章:
http://www.emis.de/journals/EJC/Volume_13/PDF/v13i1a2.pdf
附件是同一个文件.
文章里面应该提到一个Lexicographic code(字典顺序编码),
而产生这个数据需要使用reverse lexicographic code (反字典顺序编码)
25#mathe的计算是对的，20#我那个矩阵的检测n中有一个的部分有错，但比较容易改且不影响结论
11# mathe 的方法我没太明白，为什么问题就变成了“Packing K3 into Kn”？
先不要管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对应的囚徒是否全部死去来判断酒是否有毒.
关于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)!}$
虽然上面只是一个上界,但是我感觉应该同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)$