毒酒问题再来一个有趣的版本
10个耗子，1000瓶药，其中有2瓶有毒(注意确定是2瓶)，不论剂量喝了就死。所有耗子不必同时喝药，可以多轮实验，最多能保证确定出(即最坏情况)多少瓶无毒的药？ 没人愿意给出一个解吗？似乎我只到900啊。找不到好办法。 注意，每个耗子只能用一次，不可以喝了不死再喝。那样本题就没有任何意义了。 10次试验，结果为 死、活 两种状态 ，故可区分 $2^10$ 种可能
由信息论界 ，应满足 $C(x,2)<2^10$ ，$x<45$, 900不可能 不不，版主没看明白题意。
最简单的，比如将1000桶酒分10组，每组100桶，10只老鼠各喝一组，最多两只老鼠死亡，所以这样就确定了8组肯定是好的，也就是800桶。
再优化此方法，我简单找到900桶的解。
我的问题是，900是极限吗？ 将1000个酒桶分成5分，每份200桶，用4只老鼠试，可以排除600桶，再次分成5分，每份80桶，再次用4只，排除240桶，在分三份53、53、54用两只，至少可以排除53桶，总计排除893桶 将1000个酒桶分成5分，每份200桶，用4只老鼠试，可以排除600桶，再次分成4分，每份100桶，再次用3只，排除200桶，在分4份，每份50只，用3只，至少可以排除100桶，总计排除900桶 可以排除掉 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桶以内
页:
[1]