毒酒问题再来一个有趣的版本

geslon · 发表于 2011-9-8 21:49:39

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

您需要登录才可以下载或查看，没有账号？欢迎注册

×

10个耗子，1000瓶药，其中有2瓶有毒(注意确定是2瓶)，不论剂量喝了就死。所有耗子不必同时喝药，可以多轮实验，最多能保证确定出(即最坏情况)多少瓶无毒的药？

geslon · 发表于 2011-9-14 23:59:15

没人愿意给出一个解吗？似乎我只到900啊。找不到好办法。

geslon · 发表于 2011-9-15 00:00:37

注意，每个耗子只能用一次，不可以喝了不死再喝。那样本题就没有任何意义了。

shshsh_0510 · 发表于 2011-9-16 08:18:23

10次试验，结果为死、活两种状态，故可区分 $2^10$ 种可能由信息论界，应满足 $C(x,2)<2^10$ ，$x<45$, 900不可能

geslon · 发表于 2011-9-17 23:10:53

不不，版主没看明白题意。最简单的，比如将1000桶酒分10组，每组100桶，10只老鼠各喝一组，最多两只老鼠死亡，所以这样就确定了8组肯定是好的，也就是800桶。再优化此方法，我简单找到900桶的解。我的问题是，900是极限吗？

新地平线 · 发表于 2014-1-10 09:15:19

将1000个酒桶分成5分，每份200桶，用4只老鼠试，可以排除600桶，再次分成5分，每份80桶，再次用4只，排除240桶，在分三份53、53、54用两只，至少可以排除53桶，总计排除893桶

新地平线 · 发表于 2015-1-31 15:21:22

将1000个酒桶分成5分，每份200桶，用4只老鼠试，可以排除600桶，再次分成4分，每份100桶，再次用3只，排除200桶，在分4份，每份50只，用3只，至少可以排除100桶，总计排除900桶

咻咻 · 发表于 2015-3-12 18:32:59

可以排除掉 937 桶左右，也就是剩下 1000/16 上取整 = 63 桶

步骤：

每次将未排除的所有酒桶二等分，两只老鼠喝。这个算作一轮。

如果从第一轮开始，前四轮每轮都是一死一活，则未排除酒桶数已经下降为 1000/16 = 63桶以内。

如果第N轮是两死，前面都是一死一活。
容易知道，第N轮，两只老鼠各自喝了 m=1000/（2的N次方）桶。此时可以知道，在两个m桶酒中，各自恰好有一桶毒酒。此时没死的 10-2N个老鼠，等分两拨，各自在m桶酒中用二分法来试毒，可以把毒酒范围再缩小 2的（5-N）次方。
最后，毒酒的范围还是 2 × （1000/（2的N次方）/（2的（5-N）次方））= 1000/16 = 63桶以内

账号		自动登录	找回密码
密码			欢迎注册

[提问] 毒酒问题再来一个有趣的版本

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

评分

点评