数学研发论坛

 找回密码
 欢迎注册
查看: 38338|回复: 269

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

  [复制链接]
发表于 2009-6-5 14:11:44 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
http://tieba.baidu.com/f?kz=587967375

国王为10天后的生日宴会准备了1000桶酒,不幸的是,其中两桶被下了毒。为了确定两桶毒酒,有人提议用死刑犯试毒。毒的潜伏期为10天。
精华

问:至少需要多少个死刑犯才能确保找出毒酒?方案如何实行?


(最新结果在 https://bbs.emath.ac.cn/thread-1511-18-1.html, 计算机搜索现在已知最优结果为27个死刑犯 )

本题对应OEIS的链接为 A054961
并且提供了A054961不等价解的数目在A304041
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-5 16:15:34 | 显示全部楼层
有些意思,
对于任意2子集都存在集合,其并集是此2子集的补
由信息论易得要X>log2(C(1000,2))=18.9
具体构造还得再想想
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-5 16:38:44 | 显示全部楼层
确实蛮有意思的。

我只会从简单的来。
如果有3桶酒,就安排两个2人各选一桶试喝,余下那桶是否有毒得看10天后他们死不死;
如果有4桶酒,那就再安排一个人试喝;
如果有5桶酒,继续再增加一个人试喝;
如果有6桶酒,用4个死囚犯足够了吗?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-5 17:11:56 | 显示全部楼层
6桶酒4人不够
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-5 17:39:33 | 显示全部楼层
只是一个很粗糙的下界
向gxq一人一桶好像都是挺难突破的,想用一些已有的BIBD,但都超不过这个
有空再想
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-5 17:47:46 | 显示全部楼层
对于比较大的数目,突破一人一桶是很简单的.败毒上已经有人给出一种模型比如有$n^2$桶,那么
我们可以将它们排成$n**n$方阵,然后选n个人喝掉每一行,再另外选n个人喝掉每一列.
那么这时通常的结果是有两个选择行喝两个选择列的囚徒倒下,对应4个桶(分布在一个矩形的4个顶点,实际上应该选择一条对角线上的两个顶点).
为了能够区分这些这些顶点,我们最差情况在选择$2*n-1$个囚徒,让它们按斜线分配酒就可以了.这种方案只需要$4n-1$个囚犯可以区分$n^2$个酒桶.
而我们还可以将这个方案试着向高维推广
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-5 22:18:28 | 显示全部楼层
看如图形状的图,所有酒桶放在点上,每个囚徒喝一行直线.那么6a+3个囚徒可以识别$3a^2+3a+1$个酒桶
r.GIF
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-6 01:44:51 | 显示全部楼层
本帖最后由 到处瞎逛 于 2009-6-6 08:29 编辑

首先从二维的角度来考虑是46个人。

因为46条直线有1035个交点。

所以46个人可以通过其交点确定1036瓶酒到底是哪一瓶有毒。

我不能上传图片,它总是提示我图片格式不对,但是我就是很普通的png的格式。

所以不大好说明这个问题。

比如6瓶酒。4个人就可以了。

喝的方法是a(1,2,3)
b(1,4,6)
c(2,5,6)
d(3,4,5)。

推广到三维,也就是求空间直线交点的问题。在往高维,复杂了,我猜想如下计算:


应该最少需要20个人。
头脑有点晕晕的,上面的图里面式子可能有些表达细节上的错误,但是应该就是那个意思了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-6 09:15:26 | 显示全部楼层
8# 到处瞎逛

你的浏览器可是 IE8?

不能上传图片的问题,前不久有人反馈过,
最终的原因却是 IE8 默认关闭了本地文件上传权限以提高安全性,
只要在其设定中再勾选一下即可,见:/viewthrea ... ;fromuid=8#pid17689
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-6 09:52:42 | 显示全部楼层
还真是这个原因。
我的IE是8.0的,现在好了,能上传文件了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2018-7-21 01:48 , Processed in 0.077713 second(s), 19 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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