香水有毒——找出有毒的水

海姑娘 · 发表于 2007-5-27 17:08:18

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

www.ddhw.org---

---

海姑娘个人网站

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

那些花儿 · 发表于 2007-5-27 17:58:03

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

HF: · 发表于 2007-5-27 18:40:54

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

yinyin · 发表于 2007-5-28 12:22:45

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

M.E.D · 发表于 2007-5-28 17:42:24

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

husonghu · 发表于 2007-5-29 00:56:43

我想, 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:18

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

ob · 发表于 2007-5-31 03:59:34

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

		自动登录	找回密码
密码			立即注册

动态微博

香水有毒——找出有毒的水

看到这种题目就晕，不多想了，我猜我猜我猜猜猜，你别踩[:-D]

回复：香水有毒——找出有毒的水

回复：香水有毒——找出有毒的水

回复：香水有毒——找出有毒的水

回花儿，随便试试，M.E.D........

分法｛１６、１６、１６、２｝不可行。[:%]

回复：香水有毒——找出有毒的水