数学研发论坛

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

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

  [复制链接]
 楼主| 发表于 2009-6-6 11:23:00 | 显示全部楼层
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)$个死囚.这个看来基本是二维模型的极限了.
不知道如果采用三维模型能够提高到什么程度
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-6 11:51:17 | 显示全部楼层
8#的结果是不行的.结果会不可判断.
倒是如果三条直线交于一点就可以唯一判断结果了.
由此,如果我们将问题化为对偶问题,就是每条直线上三个点,1000条直线,那么至少需要多少个点呢?
那么这个正好是种树问题每行三颗 ...
mathe 发表于 2009-6-6 11:23


可以唯一确定,不需要三条直线相交。
你可以仔细想一下看看,因为任何一个点都是由两条直线唯一确定的,也就是说任何一点有毒所对应的abcd的死亡状态是唯一。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-6 11:55:09 | 显示全部楼层
喝的方法是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,这是组合问题,所以组合几何肯定优于射影几何,当然更优于欧式几何
这几天太忙,没功夫想这个又忍不住想想,呵呵,还是看你们解吧
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-6 12:11:26 | 显示全部楼层
本帖最后由 到处瞎逛 于 2009-6-6 12:53 编辑
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

看来是错了,但是24一共能表达16种状态,而C(6,2)=15所以肯定4个人是够了的。
是不是将15种组合方式按照二进制分配一下就可以了。没时间考虑了,这几天还去要去工地。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-6 21:13:23 | 显示全部楼层
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个酒桶的方案.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-6 21:18:02 | 显示全部楼层
看来是错了,但是24一共能表达16种状态,而C(6,2)=15所以肯定4个人是够了的。
是不是将15种组合方式按照二进制分配一下就可以了。没时间考虑了,这几天还去要去工地。
到处瞎逛 发表于 2009-6-6 12:11

虽然能够表达16种状态,但是不一定就能充分利用.
我用计算机穷举过,6个酒桶时4个人是不够的.
同样可以验证,7个酒桶时5个人也不够(不过这个计算量已经非常大了,我的计算机好像花费了1天多时间)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-6 23:58:00 | 显示全部楼层
本帖最后由 shshsh_0510 于 2009-6-6 23:59 编辑

设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阶的构造
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-7 05:15:22 | 显示全部楼层
设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

问题在于要求同时喝酒,而不能第一次判断有了结果以后再做第二次判断.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-7 05:44:32 | 显示全部楼层
看来是错了,但是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喝了.
容易看出余下那桶酒无论如何分配,总会出现不可以识别的情况
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-7 16:18:39 | 显示全部楼层
问题在于要求同时喝酒,而不能第一次判断有了结果以后再做第二次判断.
mathe 发表于 2009-6-7 05:15

当然同时喝酒
下面是用这个想法的28个人32桶的连接矩阵
1.jpg
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-9-15 13:53 , Processed in 0.065336 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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