数学研发论坛

 找回密码
 欢迎注册
楼主: mathe

[讨论] 毒酒问题(加强版)

  [复制链接]
发表于 2009-6-7 16:23:05 | 显示全部楼层
本帖最后由 shshsh_0510 于 2009-6-7 16:25 编辑

此法在$n=2^10$时为107似乎不如那个排成方阵的
但n比较大时就有优势了,比如$n=2^50=1125899906842624$
此时仅需2547,要远小于$(1125899906842624)^(1/2)$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-7 17:22:01 | 显示全部楼层
还是感觉不对.不知道你怎么能够构造出来的.
而且你上面的数据也挺难验证的,最好你自己可以检验一下.
如果成立,也就是说任意不同两列的并得到的值全部必须不同.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-7 18:01:02 | 显示全部楼层
将我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.a
77.SS
88.c21
912.s31
1013.s6.s1
1117.s11.c2
1220.s12.c31
1326.c18.s41
1428.s28.s8.s21
1535.s42.s15.c31
1637.s48.s16.c411
1744.s68.SS24.ec621
1848.s69AC33s10.s311
1957.c76c52s19.c311
2060.s84c80.s20c521
2170.s108Nu120.s27pc731
2273.s132m176.s35pc12.s31
2383.s147t2253.s45pc23.c42
2488.s168s25356c24c63z13
25100.c210.s254x272ec36ec8?
26104.c260.s257y91Nu39q214.s4z13
27117.s260278y118Nu54c27.s5z13
28121.z3280Nu296y132pc65Nu28c7z13
29134.z3234s300xr96s47s19z138Gj
30140.z3272Gj327xr65z1358s22z1315z13
31155.z3311xG362xr77z1372s30z1315Gj
32160.z3337xG403xr167s87s33z1319z13
33176.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???7707s
64661.z3?8064s????
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-7 18:11:14 | 显示全部楼层
然后对于每个数字,在表格中找到不小于这个数字的行号最小的格子.那么行号就是这个方法可以提供的最少的囚徒数.不过可惜我没有找到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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-7 19:06:10 | 显示全部楼层
想了一下,shshsh_0510的拆分方法还是挺有用的.不过得到的结果应该是
$f(2x)<=f(x)+2+2g(x)$.
而对应的复杂度应该在$O(log^2(x))$
其最大的好处是给出了一个非常漂亮的复杂度估计式.
但是对于上面表格列出的数据没有改善作用.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-7 19:23:47 | 显示全部楼层
根据那个表格上的页面,构造41个囚徒解决1000个酒桶问题,我们需要参考文章:
http://www.emis.de/journals/EJC/Volume_13/PDF/v13i1a2.pdf
附件是同一个文件.
v13i1a2.pdf (118.82 KB, 下载次数: 10)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-7 20:58:47 | 显示全部楼层
25#mathe的计算是对的,20#我那个矩阵的检测n中有一个的部分有错,但比较容易改且不影响结论
11# mathe 的方法我没太明白,为什么问题就变成了“Packing K3 into Kn”?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-8 06:57:17 | 显示全部楼层
先不要管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对应的囚徒是否全部死去来判断酒是否有毒.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-8 07:09:08 | 显示全部楼层
关于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)!}$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-8 07:20:55 | 显示全部楼层
虽然上面只是一个上界,但是我感觉应该同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)$

评分

参与人数 1威望 +3 收起 理由
gxqcn + 3 mathe 化简公式的水平实在是高。

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-6-18 19:10 , Processed in 0.069729 second(s), 21 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表