数学研发论坛

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

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

  [复制链接]
发表于 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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-9 06:50:59 | 显示全部楼层
你找到的这个是不同的问题,叫families cancellative,是一个更弱的问题
AUB=AUC => B=C
不过发现我那个找到的结论上也还有o(1),也就是只有n很大的时候才使用,对于n=1000是多少还要具体构造出来才知道.不过估计要看懂那文章,至少它给出的几个引用论文都要看完才行.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-9 07:54:36 | 显示全部楼层
文章 Union-free Hypergraphs and Probability Theory (Peter Franki and Zoltan Furedi) 中 (19)
给出了$f(4n)>=2^n$的构造,也就是使用40个囚犯可以解决1024桶酒问题.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-9 08:00:13 | 显示全部楼层
42# mathe
看了那个构造确实如此,是个更弱一些的问题
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-9 08:06:57 | 显示全部楼层
43#提到的40个基本上快是极限了,我觉得不会有少于35个的方案,理由如下
首先那个A(n,8,7)已经相当紧密了,然后我们试着向其中再添加一些元素
即使我们能够将一个A(n,6,5)加A(n,4,3)巧妙的加进去,则根据23#的表格,也需要35个,而这似乎不太可能
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-9 08:16:30 | 显示全部楼层
39#的那篇文章的逼近形式有可能得出更好的结果.
不过里面的方法让人看不大懂.
其实用的方法应该同
Union-free Hypergraphs and Probability Theory
中定理II的方法类似.都使用了概率模型.不过两者都挺难看懂.
而39#那个文章中的过程当然更加复杂了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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} }$
就满足条件
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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个集合,它们将满足条件.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-9 14:35:28 | 显示全部楼层
tq.zip (10.45 KB, 下载次数: 6)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-9 14:52:47 | 显示全部楼层
发现这个方法可以找远远更加好的结果(只要增大k就可以了)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-8-21 13:27 , Processed in 0.051139 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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