毒酒问题(加强版)

mathe · 发表于 2009-6-8 17:32:16

想了一下,shshsh_0510的拆分方法还是挺有用的.不过得到的结果应该是
$f(2x)
mathe 发表于 2009-6-7 19:06

现在感觉shshsh_0510的那个结果:
$f(2x)<=f(x)+2+g(x)$还是对的.
不过复杂度还是$O(log^2(x))$而不是$O(log(x))$.
其道理在于每次对2x桶酒中找两桶毒酒时,我们可以直接让两个人分别喝掉左边和右边的x桶酒.
那么如果只有一个人毒死,那么就转化为f(x)的问题.而且左边和右边死掉的情况不会同时出现.所以f(x)部分对于左边和右边的情况可以用相同的人来测试.
而这种测试会就相当于将2x写成2进制数,这些囚犯都正好喝掉某个比特位为1对应的所有的酒或某个比特位为0对应的所有的酒.
而余下比较复杂的情况是在某一层开始,左边和右边的人同时死去(对应上面的方法,相当于出现比特位为1和0对应的囚徒都死去的最高比特位h).而由这一层开始,我们只需要左边分支,对这个分支采用$g(2^h)$的方案可以得出这个分支中毒酒的位置.而对于右边的分支,在左边分支的结果确定以后,对于所有低比特位就可以直接确定了(如果对某个比特位,只有1或0对应的囚徒死去,两个分支在这个比特位相同;如果同时1和0对应的囚徒死去,两个分支在这个比特位取值相反).

mathe · 发表于 2009-6-8 19:43:41

然后对于每个数字,在表格中找到不小于这个数字的行号最小的格子.那么行号就是这个方法可以提供的最少的囚徒数.不过可惜我没有找到A(n,d,w)的近似公式,不然我们可以对它有更好的了解.
可以看到在同的数目k
mathe 发表于 2009-6-7 18:11

发现我的这个方案中,我们总可以再加一桶酒,所有的人都不喝.
这个对比较小规模问题影响比较明显.比如9个人可以解决13桶问题

mathe · 发表于 2009-6-8 22:15:24

google到一篇很强的文章,对于1000,应该可以消减到31一下:

v5i1r39.pdf (140.75 KB, 下载次数: 206)

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桶酒问题.

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就可以了)

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

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