珍珠湾ART

标题: 香水有毒——找出有毒的水 [打印本页]

作者: 海姑娘 时间: 2007-5-27 17:08
标题: 香水有毒——找出有毒的水

50杯无色透明的水，其中3杯有毒，用一种试纸可以检验水是否有毒，最不理想的情况下，最少需要检验多少次才能找出有毒的三杯水？

www.ddhw.org---

---

海姑娘个人网站

http://www.tianxianmeimei.com/xuehua/xhindex.html

作者: 那些花儿 时间: 2007-5-27 17:58
标题: 看到这种题目就晕，不多想了，我猜我猜我猜猜猜，你别踩[:-D]

我猜想啊，最糟糕的情况就是，第一杯不是，第二杯不是，第三....到47杯都不是。所以要47次才知道剩下三杯有毒。是这个意思吗？

作者: HF: 时间: 2007-5-27 18:40
标题: 回复：香水有毒——找出有毒的水

The integer part of log_2(C(50,3)) +1

作者: yinyin 时间: 2007-5-28 12:22
标题: 回复：香水有毒——找出有毒的水

楼上是从信息量的角度来估计所需测试次数所得的下界：１５。它也可表为┌ log₂C(50,3)┐，其中┌ ... ┐为 ceiling function 。但具体如何安排测试，还得考虑。直觉让我选择第一步为分５０杯成１６、１６、１６、２这四摊。

作者: M.E.D 时间: 2007-5-28 17:42
标题: 回复：香水有毒——找出有毒的水

关键分几组才能达到最优？感觉应该是每次分两组，取样，混合，测试，这样的话，应该五次吧

作者: husonghu 时间: 2007-5-29 00:56
标题: 回花儿，随便试试，M.E.D........

我想, HF和yinyin的思路对。方法大致是(比如)：

把50个样分成5组：10，10，10，10，10。同组内取样混合，得5份样，最多试5次(更正：其实这里最多试4次就够了)，可至少排除两组(20个样)是清白的，不用再试，

剩下在30个样中用类似的方法再分组, 再试......

如yinyin说，关键是每次如何组合才好。为使次数最少，每次分组的组合法很有讲究(使前后次相关).

HF和yinyin, 我的理解对吗？

总之，总共不需47次；但总共5次太少，也不可能。www.ddhw.com

(题意是有点不清。实际上，上述那样分组混合其实够烦的，可能还不如一个一个试更方便呢)

本贴由[husonghu]最后编辑于：2007-5-28 20:35:28

作者: yinyin 时间: 2007-5-30 11:41
标题: 分法｛１６、１６、１６、２｝不可行。[:%]

从信息量的观点考虑，仅一种分法｛１２、１２、１２、１２、２｝可行。进一步思考中。

作者: ob 时间: 2007-5-31 03:59
标题: 回复：香水有毒——找出有毒的水

It seems one needs 24 times to find the cups with poison water.
8, 8, 8, 8, 8, 10 need 6 times
4, 4, 4, 4, 4, 4, 4 need 7 times
2, 2, 2, 2, 2, 2 need 6 times
1, 1, 1, 1, 1, 1 need 5 times

欢迎光临珍珠湾ART (http://66.160.158.134/)