毒酒问题(加强版)

shshsh_0510 · 发表于 2009-6-8 23:41:52

n元集的一个子集族，任意两个的并不相等，求此族中集合最大数f(n).下面文章
http://www.emis.de/journals/EJC/Volume_3/PDF/v3i1r15.pdf
给出了构造（还没仔细看）宣称 f(3m)>m*3^(m-2)
映射到我们的问题，子集族每个集合代表酒桶，由于任两个集合的并不相同，从而可以根据其并判别是哪两个桶
由f(21)=f(3*7)>7*3^(7-2)=1701>1000

就是说21人！！！
2#中已经给出信息论界为19人
另 log2(C(1701, 2))=20.46

mathe · 发表于 2009-6-9 06:50:59

你找到的这个是不同的问题,叫families cancellative,是一个更弱的问题
AUB=AUC => B=C
不过发现我那个找到的结论上也还有o(1),也就是只有n很大的时候才使用,对于n=1000是多少还要具体构造出来才知道.不过估计要看懂那文章,至少它给出的几个引用论文都要看完才行.

mathe · 发表于 2009-6-9 07:54:36

文章 Union-free Hypergraphs and Probability Theory (Peter Franki and Zoltan Furedi) 中 (19)
给出了$f(4n)>=2^n$的构造,也就是使用40个囚犯可以解决1024桶酒问题.

shshsh_0510 · 发表于 2009-6-9 08:00:13

42# mathe
看了那个构造确实如此，是个更弱一些的问题

shshsh_0510 · 发表于 2009-6-9 08:06:57

43#提到的40个基本上快是极限了，我觉得不会有少于35个的方案，理由如下
首先那个A(n,8,7)已经相当紧密了，然后我们试着向其中再添加一些元素
即使我们能够将一个A(n,6,5)加A(n,4,3)巧妙的加进去，则根据23#的表格，也需要35个，而这似乎不太可能

mathe · 发表于 2009-6-9 08:16:30

39#的那篇文章的逼近形式有可能得出更好的结果.
不过里面的方法让人看不大懂.
其实用的方法应该同
Union-free Hypergraphs and Probability Theory
中定理II的方法类似.都使用了概率模型.不过两者都挺难看懂.
而39#那个文章中的过程当然更加复杂了

mathe · 发表于 2009-6-9 08:23:18

43#中结果的构造方法倒是很简单.
我们将长度为n的0,1向量看成$F_{2^n}$中的数.
而记$I=(1,1,...,1)$也就是所有n个分量都是1的数.
对于4n个囚犯,可以分成4组X,Y,Z,W,每组n个囚犯
分别做$F_{2^n}$到各组n各囚犯构成集合的一一映射映射$g_1:F_{2^n} |->2^X,g_2:F_{2^n} |->2^Y,g_3:F_{2^n} |->2^Z,g_4:F_{2^n} |->2^W$
于是集合
${ g_1(a) uu g_2(I-a) uu g_3(a^3) uu g_4(I-a^3) | a in F_{2^n} }$
就满足条件

mathe · 发表于 2009-6-9 12:25:31

现在基本理解39#楼方法的想法了.
我现在估算了一下,如果将39#楼的方法采用到1000个囚犯问题.
那么应该可以用39个囚犯解决1398桶左右的酒.
具体产生方法如下,对于39个元素的集合,拆分成15个元素的集合X和24个元素的集合Y.
对X中元素每三三分组成5组.并且每组中三个元素分别标上0,1,2三个数
然后如下选择X中的一些子集:
5组中任意选择1组,将三个元素全部选入,余下4组每组选择一个元素,但是要求所有选择的元素对应数字之和为3的倍数.
这样的子集总共有$5*3^3=135$个.
然后对于每个这样的子集,随机产生14个Y中子集,要求Y中每个元素被选中的概率为0.3.
这样我们可以构造出共135*14=1890个子集.
然后在其中遍历所有三个集合的组合A,B,C判断是否有$A uu B=A uu C$,同样遍历四个集合的组合A,B,C,D判断是否有$A uu B = C uu D$,如果出现这样的组合,从中任意淘汰一个集合.
我计算结果从概率上来说,平均来说淘汰后剩余大概为1398个集合,它们将满足条件.

mathe · 发表于 2009-6-9 14:35:28

tq.zip (10.45 KB, 下载次数: 6)
写了个程序,实现上面的算法,得到一个39个囚犯1706桶酒的解(随机结果,重新运行结果会不同)
对于输出结果,每行代表一桶酒的喝法,有两个16进制数构成,前面一个15比特,后面一个24比特

mathe · 发表于 2009-6-9 14:52:47

发现这个方法可以找远远更加好的结果(只要增大k就可以了)

账号		自动登录	找回密码
密码			欢迎注册

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