毒酒问题(加强版)

mathe

8#的结果是不行的.结果会不可判断.
倒是如果三条直线交于一点就可以唯一判断结果了.
由此,如果我们将问题化为对偶问题,就是每条直线上三个点,1000条直线,那么至少需要多少个点呢?
那么这个正好是种树问题每行三颗树1000行的结果.
根据http://mathworld.wolfram.com/Orchard-PlantingProblem.html
我们取$[1/6(k-1)(k-2)]>=1000$的k就可以了.得出79个死囚是可以的.
不过这里,平面约束是没有必要的,所以我们可以将问题改成Packing $K_3$ into $K_n$的问题,结果要稍微好一些.
不过这些结果都同7#的结果很类似,对于n桶酒,大概需要$sqrt(6n)$个死囚.这个看来基本是二维模型的极限了.
不知道如果采用三维模型能够提高到什么程度

到处瞎逛

8#的结果是不行的.结果会不可判断.
倒是如果三条直线交于一点就可以唯一判断结果了.
由此,如果我们将问题化为对偶问题,就是每条直线上三个点,1000条直线,那么至少需要多少个点呢?
那么这个正好是种树问题每行三颗 ...
mathe 发表于 2009-6-6 11:23

可以唯一确定，不需要三条直线相交。
你可以仔细想一下看看，因为任何一个点都是由两条直线唯一确定的，也就是说任何一点有毒所对应的abcd的死亡状态是唯一。

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，这是组合问题，所以组合几何肯定优于射影几何，当然更优于欧式几何
这几天太忙，没功夫想这个又忍不住想想，呵呵，还是看你们解吧

到处瞎逛

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 发表于 2009-6-6 11:55

看来是错了，但是2⁴一共能表达16种状态，而C（6，2）=15所以肯定4个人是够了的。
是不是将15种组合方式按照二进制分配一下就可以了。没时间考虑了，这几天还去要去工地。

mathe

11#里可以利用Packing $K_3$ to $K_n$的结论构造一些解.这个相当于页面
http://www.research.att.com/~njas/codes/Andw/index.html#dist4
中的A(n,4,3)
而同样,如果我们考虑A(n,6,5),A(n,8,7),A(n,10,9),等等,都可以转化为这个问题的解(相当于利用更高阶图的结果)
其中A(n,d,w)表示那些长度为n比特的二进制数的集合的最大元素数目,其中集合中任何两个元素不同比特位数目不小于d,而每个二进制数正好有w比特为1.
那么对于A(n,w+1,w)中的方案(w为奇数),任何两个比特1数目为w的二进制数,不同的位置至少有w+1;也就是相同的比特1最多(w-1)/2个. 对应到本题,让A(n,w+1,w)桶酒让n个囚徒喝,其中n个比特位分别对应n个囚徒.每个二进制数对应一桶酒.每个二进制数上比特1对应的囚徒要喝掉对应的酒.
那么如果某桶酒有毒,那么那个对应的二进制数所有比特1对应的囚徒必然死去.反之如果某桶酒无毒,那么由于只有两桶毒酒,所以这个对应的二进制数最多有2*(w-1)/2=w-1个囚徒死去.
也就是我们可以根据每桶酒对应的二进制数所有比特1对应的囚徒是否全部死去来判断酒是否有毒.
表格中A(n,4,3)仅列到n=64,而对应值为661,也就是说64个囚徒才可以识别661桶酒.
而如果我们查看A(n,6,5),那么可以发现n=48是,A(48,6,5)=1030,也就是说,这个方案中48个囚徒就可以识别1030桶酒.
而表格A(n,8,7)中,n=41时,结果为1095,也就是说41个囚徒就可以了.
而在查看A(n,10,9)中,仅列到n=43,但是结果才841说明再增加w需要囚徒数目又要增加了.
所以我们通过这个方法,可以得出一种41个囚徒解决1000个酒桶的方案.

mathe

看来是错了，但是24一共能表达16种状态，而C（6，2）=15所以肯定4个人是够了的。
是不是将15种组合方式按照二进制分配一下就可以了。没时间考虑了，这几天还去要去工地。
到处瞎逛 发表于 2009-6-6 12:11

虽然能够表达16种状态,但是不一定就能充分利用.
我用计算机穷举过,6个酒桶时4个人是不够的.
同样可以验证,7个酒桶时5个人也不够(不过这个计算量已经非常大了,我的计算机好像花费了1天多时间)

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阶的构造

mathe

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

一个人喝x桶，则可能分为3种情况：
1 此人死，在其喝的x中有2，共C(x,2)种
2 此人死，在其喝的x中有1,共x(n-x)
3 此人不死，在其未喝的n-x中有 ...
shshsh_0510 发表于 2009-6-6 23:58

问题在于要求同时喝酒,而不能第一次判断有了结果以后再做第二次判断.

mathe

看来是错了，但是24一共能表达16种状态，而C（6，2）=15所以肯定4个人是够了的。
是不是将15种组合方式按照二进制分配一下就可以了。没时间考虑了，这几天还去要去工地。
到处瞎逛 发表于 2009-6-6 12:11

直接证明4个人不能达到6桶酒的目标也不难.
对于4个人,所有子集有16种.
但是如果6桶酒的某一个组合(i,j)被映射到空集,那么就说明如果i,j都是毒酒,所有的人都不会死,也就是说所有的人都没有喝i,j这两桶酒.于是,如果毒酒是(i,k),那么只有喝了桶k里的酒的人会死去,我们无法区分(i,k)和(j,k).所以必然没有组合被映射到空集.
而对于6桶酒中的某两个组合(i,j)和(s,t),如果分别被映射到单元素集{u},{v}.
也就是如果i,j两桶有毒,只有第u个人死去;如果s,t两桶酒有毒,只有第v个人死去
而i,j,s,t中,最多两个数相同,也就是至少包含了3桶酒.
如果i,j,s,t四个数都不相同,很容易得出矛盾.
于是我们得出i,j,s,t中有一个数相同,表明这桶酒没有人喝过,不凡设j=t,也就是第j桶酒没有人喝.u喝了i,v喝了s.
同样,对于余下两个人构成的单元数集{w},{x},我们还可以找到三个数(三桶酒)i',j',s',其中w喝了i',x喝了s',j'没有人喝.于是j=j'.
于是我们得出5桶酒已经有了分配情况.j每人喝,i只有u喝了,s只有v喝了,i'只有w喝了,s'只有x喝了.
容易看出余下那桶酒无论如何分配,总会出现不可以识别的情况

shshsh_0510

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

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