毒酒问题(加强版)

shshsh_0510

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

shshsh_0510

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

shshsh_0510

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

8#的结果是不行的，考虑连接矩阵

        1        2        3        4        5        6
a        1        1        1                       
b        1                        1                1
c                1                        1        1
d                        1        1        1       
易看出（1，2）和（2，6）都是abc死
同意mathe，这是组合问题，所以组合几何肯定优于射影几何，当然更优于欧式几何
这几天太忙，没功夫想这个又忍不住想想，呵呵，还是看你们解吧

shshsh_0510

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

一个人喝x桶，则可能分为3种情况：
1 此人死，在其喝的x中有2，共C(x,2)种
2 此人死，在其喝的x中有1,共x(n-x)
3 此人不死，在其未喝的n-x中有2，共C(n-x,2)种
区分1、2顶多再一个人试（实际上可能还用不着），所以如简单的令n=2x  （实际可以更效率些，令C(x,2)+x(n-x)=C(n-x,2) ），则有
f(2x)<=1+max( 1+f(x)+g(x), f(x) )=2+f(x)+g(x)
易知g(x)是log阶的，于是得到一个log阶的构造

shshsh_0510

问题在于要求同时喝酒,而不能第一次判断有了结果以后再做第二次判断.
mathe 发表于 2009-6-7 05:15

当然同时喝酒
下面是用这个想法的28个人32桶的连接矩阵

shshsh_0510

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

shshsh_0510

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

shshsh_0510

不好意思，原来没注意15#已经讲解过原理了，感谢mathe的再次解说

shshsh_0510

29#给出的是一个上界，这个问题需要下界，对于A(n,d,w)的上下界可参照
下界：http://www.research.att.com/~njas/codes/Andw/index.html
上界：http://webfiles.portal.chalmers.se/s2/research/kit/bounds/cw.html
没仔细看，不知mathe的上界对其是否有改善
另外对于1000瓶酒，感觉用Constant-weight code的方法，41就是极限了，用A(n,10,9)已经不如A(n,8,7)了，所以知道更多的A(n,d,w)也没有用了

shshsh_0510

39# mathe


呵呵，还是你快。
我找到erdos那个但没能超过41