数学研发论坛

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

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

  [复制链接]
 楼主| 发表于 2018-5-7 11:17:47 | 显示全部楼层
A054961问题对于较小的项同样我们可以把所有不等价的解找出
n=0: 只有1个解 {0}
n=1: 只有1个解 {1 0}
n=2: 只有1个解 {2 1 0}
n=3: 只有1个解 {4 2 1 0}
n=4: 只有1个解 {8 4 2 1 0}
n=5:    有2个解{10 8 4 2 1 0}  {12 11 c 6 9 0}
n=6:    有2个解{30 a 5 2c 23 19 16 0} {2 1 24 18 32 29 e 15}
n=7:    有3个解{9 5 3 18 44 22 68 34 52 0} {21 22 18 14 a 5 70 49 46 0} {40 21 22 18 14 a 5 70 49 46}
n=8:    有2个解{c0 30 9 6 a8 92 85 64 51 4a 23 1c 0} {2 1 c0 24 18 8c 70 a2 91 4a 45 16 29}
n=9: 只有1个解{100 21 18 6 1c0 85 43 68 b0 54 8a 115 10b 164 1a2 2d 33}
结果在: A304041
而对应的不使用等价关系的所有解的数目在A054962

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-8-22 07:37:15 | 显示全部楼层
发现在 https://pastebin.com/4yDd1XvG 有人宣称用28个囚犯解决了1000瓶酒

点评

其实我在想……如果国王生日在20天之后呢……如果已知还会有另一个人在9.9天之后再对某一桶酒下毒呢  发表于 2019-8-22 10:03
我觉得不存在本质的区别,说明人家也找出了很不错的算法  发表于 2019-8-22 09:06
可是……1L的结果说,27个就够了啊……  发表于 2019-8-22 08:22
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-12-23 16:50:55 | 显示全部楼层
在另外一个论坛发现了这个问题,搜了一下居然回来了哈哈

那边有人同样给出了27个人的构造方法
因为我好久没关注数学相关东西了就先不在这里叙述
过段时间先爬完本帖再说
传送门:https://bbs.nga.cn/read.php?tid=19718634&_ff=-7
(楼主是我)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-12-24 08:02:32 | 显示全部楼层
你的链接无法访问。
手工构造本论坛应该只达到33人,我觉得很难进一步改进。
可以查看 https://emathgroup.github.io/blog/two-poisoned-wine ,这里面的内容整理过了,看起来更加方便些,当然细节还得从本论坛找。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-1-12 07:58:46 | 显示全部楼层
https://quuxplusone.github.io/blog/code/2020-01-10-wolfy-out.txt
记录了一些两瓶以及更多毒酒问题的记录,昨天将我们的数据也添加了

https://quuxplusone.github.io/bl ... -sheep-with-tables/
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-3-13 15:30:10 | 显示全部楼层
本帖最后由 aimisiyou 于 2020-3-13 18:24 编辑
mathe 发表于 2019-12-24 08:02
你的链接无法访问。
手工构造本论坛应该只达到33人,我觉得很难进一步改进。
可以查看 https://emathgrou ...


7人识别10坛酒的矩阵不正确(00   03  05   09     12    24   38    48    54     62),若出现(死,活,死,死,死,活 ,活)的结果,无法判断是第5坛酒和第9坛酒有毒,还是第8坛酒和第9坛酒有毒。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-3-13 19:19:02 | 显示全部楼层
本帖最后由 aimisiyou 于 2020-3-13 20:12 编辑

8人识别13坛酒的矩阵也不正确(00  03  0C  15  26 38  49  52  60  8A  90  A1  C4)。若出现(活,死,死,活,死,死,死,死)的情况,将无法判断是第5坛酒和第7坛酒有毒,还是第4坛酒和第9坛酒有毒。若出现(活,活,活,死,死,死,死,死)的情况,也无法判断哪两坛酒有毒(可能是第1坛和第4坛,或者第2坛和第4坛,或者第3坛和第4坛)。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-3-24 10:16:50 | 显示全部楼层
aimisiyou 发表于 2020-3-13 15:30
7人识别10坛酒的矩阵不正确(00   03  05   09     12    24   38    48    54     62),若出现(死,活 ...

你可能看错或理解错了?该矩阵对应的二进位配毒表如下:
  1. .......
  2. .....11
  3. ....1.1
  4. ...1..1
  5. ..1..1.
  6. .1..1..
  7. .111...
  8. 1..1...
  9. 1.1.1..
  10. 11...1.
复制代码

如果是第5、9坛(12、54)有毒,死况为:死活死活死死活;如果是第8、9坛(48、54)有毒,死况为:死活死死死活活。两者是能被分辨的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-3-24 11:05:25 | 显示全部楼层
本帖最后由 aimisiyou 于 2020-3-24 11:09 编辑
毒酒滴冻鸭 发表于 2020-3-24 10:16
你可能看错或理解错了?该矩阵对应的二进位配毒表如下:

如果是第5、9坛(12、54)有毒,死况为:死活 ...


嗯,是我转换错误了,把12转化为0001100了。不知能不能利用矩阵递推构造法?随机算法的运算量太大了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-4-2 11:14:35 | 显示全部楼层
本帖最后由 毒酒滴冻鸭 于 2020-4-2 11:16 编辑
aimisiyou 发表于 2020-3-24 11:05
嗯,是我转换错误了,把12转化为0001100了。不知能不能利用矩阵递推构造法?随机算法的运算量太大了。


七人测十坛有一个很直观的方案,不过貌似跟站主这里的方案结构不同。

直观方案是:把九坛酒按3x3矩阵摆放,然后三人分别试三行,三人分别试三列,一人试正对角线。

  1. aaa
  2. bbb
  3. ccc

  4. def
  5. def
  6. def

  7. g..
  8. .g.
  9. ..g
复制代码


八人试十三坛貌似也有几何结构上对称的方案,不过不太记得了,有空再研究一下。。。

其实真正厉害的是九人试十七坛,因为那个不能有一坛没人试,所以结构非常难组织出来,除了编程估计只有超级天才才能凭空用人脑设计出来。。。

点评

谢谢站主的鲜花奖励!  发表于 2020-4-7 10:53
刚好抢到200楼了,不知站主会否奖励一下?(吐舌)  发表于 2020-4-2 11:21

评分

参与人数 1鲜花 +12 收起 理由
mathe + 12

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2020-8-15 22:29 , Processed in 0.065108 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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