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

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

  [复制链接]
发表于 2014-1-2 21:38:38 | 显示全部楼层
大家玩10滴水游戏么  据说要用遗传算法   谁可以编程找最优解
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-1-2 21:43:09 | 显示全部楼层
我觉得30人可以  10人放X轴上  10人放Y轴上  10人放Z轴上,每人喝100桶    一桶毒酒死会毒死3人  两桶毒死最多6人    XYZ坐标确定了就确定酒桶位置了

补充内容 (2014-1-3 18:41):
页数太多,没有注意  看看我发的帖子,扩展到多维空间

点评

这个问题6楼就指出来了。发表意见前最好先看下人家是怎么说的  发表于 2014-1-3 17:23
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-1-3 19:00:59 | 显示全部楼层
mathe 发表于 2009-6-5 17:47
对于比较大的数目,突破一人一桶是很简单的.败毒上已经有人给出一种模型比如有$n^2$桶,那么
我们可以将它们 ...

搞编程的呀,我不怎么会编程跟模拟  算算这样,假如不知道1000里面有多少桶毒酒,那么最少需要多少人将所有毒酒试出来?是不是需要1000人才保险呢
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-5-28 21:54:42 | 显示全部楼层
本帖最后由 realnumber 于 2014-5-28 22:14 编辑

这样可不可以,有没按题目规则来?目前结果是14人。
4桶中2桶毒酒,区分需要3人。
那么把1032桶酒,等分成256个小组,每小组4桶,依次标记为1,2,3,4,所有标记为1的256桶取样混合后让一人喝下,2,3也一样,需要3人,标记为4的256桶不需要取样喝。这样256个小组每组4桶酒取样混合,形成新的256桶酒。
现在的问题就是:已经预计消耗3人和区分新的256桶酒(最多含2桶毒酒)
再重复一次以上步骤,得6人和区分64桶酒(最多含2桶毒酒,可以满足10日一次鉴别要求,都事先标记好,后面同),继续重复一次,9人和区分16桶酒,再次,12人和区分4桶,15人。

如果是3桶中2桶毒酒,区分需要2人。按以上办法,需要14人区分\(3^7=2187\)桶酒(其中2桶毒)。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2014-5-28 21:58:40 来自手机 | 显示全部楼层
你需要的是4桶有一桶或俩桶有毒情况的分析,三人不够,需4人

点评

不好意思,想错了  发表于 2014-5-29 16:13
确实有问题,修改在106楼  发表于 2014-5-29 07:28
当作有2桶毒的最差情况好了。也许我没看懂题目? 假定国王有4桶酒,其中2桶毒。需要3人,一人尝一桶.对吗?错的话,我题目理解错了。  发表于 2014-5-28 22:04
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-5-29 07:27:46 | 显示全部楼层
mathe 发表于 2014-5-28 21:58
你需要的是4桶有一桶或俩桶有毒情况的分析,三人不够,需4人

4人的话,按上面步骤20人就能区分1032桶中的2桶毒酒。
我再想想:应该还能减1人,也就是19人;或104楼方案增1人,16人。

点评

不好意思错了,看107,特殊举了下  发表于 2014-5-29 16:11
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-5-29 16:10:47 | 显示全部楼层
比如国王共16桶酒,其中2桶毒,分成ABCD四组,依次为A1,A2,A3,A4,B1,B2,B3,.....,D3,D4
4+4=8人,其中4人分别喝A,B,C,D四组的酒,另四人分别喝1,2,3,4的酒(每人都喝了原始的四桶混合的酒)
10天后,ABCD至少死2个(比如AC),2桶毒酒就在这2组,1234也至少死2个(比如1,4)。
那么毒酒是A1A4C1C4;我错了,还是区分不出来。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-11-20 16:40:27 | 显示全部楼层
请问64桶酒,其中两瓶有毒,16人能试出来吗?我只能想到17人的解法。。。

另外16桶酒,最少应该确定是9人了吧?

知道1000桶酒的目前已知最优解为32人,但是我之前着力研究1024桶酒的问题,目前应该还是33人吧?(电脑随机解法)

我比较有兴趣研究人脑能直观看出来的解法,目前最多能想到36人。。。74#楼mathe站主说的33人解法貌似不行,因为tannis_jin那个32*32对角线分16种情况,不可能用9人识别,因为这16种情况最少有1人死最多有4人死,而C(16,4)=1820已经大于2^9=512。。。

点评

@mathe 就是看了那个方法啊,难道16桶酒中最多4桶有毒也可以用9人识别出来?!  发表于 2014-11-20 19:53
看73#的方法  发表于 2014-11-20 17:35

评分

参与人数 1金币 +20 收起 理由
gxqcn + 20 首贴奖励,欢迎常来。

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-11-20 16:45:04 | 显示全部楼层
tannis_jin 发表于 2009-6-16 20:34
将之前的平面方案推广到立体:
列成10×10×10的方阵。
行,列,高各派8人(应该能更少)

我认为这个10人确定对角线的假设并不严谨,目测最少也需要15、16人的样子。

可以从4x4x4立方阵看看,4人是不可能确定的,最少也要6人。。。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-11-20 20:38:29 | 显示全部楼层
mathe站长请看:

按照73#楼的方法,如果是14x14方阵:

01234567654321
10123456765432
21012345676543
32101234567654
43210123456765
54321012345676
65432101234567
76543210123456
67654321012345
56765432101234
45676543210123
34567654321012
23456765432101
12345676543210

那么试对角线的这7个人最多有4人会死,例如第45横行,第13直列。。。这样的情况不能当7桶中2桶有毒那样优化吧?

点评

16个人我估计够了,但是处理这个问题的代码都是很久以前写的,现在找不大了,所以具体数据我现在也无法给出  发表于 2014-11-22 08:07
另外能否告知64桶酒所需人数是否16或更少?万分感谢!  发表于 2014-11-21 08:14
感谢站长的解释。。。原来之前想多了,这个对角线系统里每桶毒酒只有一人试,所以最多只死2人。。。但是最少只死1人或全部不死(例如1,2行1,2列),所以9人不能应付16桶酒,必须用上10人?  发表于 2014-11-21 08:13
如果是14*14方阵,那么是解决196桶酒的问题。如果45行和13列有毒,那么就已经确定了四个同中分别由两桶会有毒,而按对角线方向,它们分别分在1,2,3,4四个不同的鸡尾酒中,也就是说,这4种鸡尾酒有且只有两种会有   发表于 2014-11-20 20:59
32^2=1024个桶中只有两桶有毒,按对角线方向是使用一个32*32的方阵,可以调成16种鸡尾酒,其中最多两种鸡尾酒有毒。然后16种鸡尾酒,我们不需要16人,而只需要9人(在根据16桶酒的方案品尝鸡尾酒的鸡尾酒)来判断而   发表于 2014-11-20 20:57
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-29 04:07 , Processed in 0.044102 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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