牛人们，进来帮助解数学题啦！ (转载) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

牛人们，进来帮助解数学题啦！ (转载)

牛人们，进来帮助解数学题啦！ (转载)# Joke - 肚皮舞运动

s*i2013-05-16 07:05

1 楼

更新成多少次老鼠实验次数了。
【以下文字转载自 PDA 讨论区】
发信人: sui (黑圈圈), 信区: PDA
标题: 牛人们，进来帮助解数学题啦！
发信站: BBS 未名空间站 (Thu May 16 15:26:55 2013, 美东)
现有酒 n 瓶。其中可能有少量几瓶（m）含有铊毒 (n > m)。
作为一个千老，你有老鼠若干。
你可以取多瓶酒滴混合喂老鼠。有毒就死。
求解，怎么做才能最节省老鼠实验次数而验出哪瓶有毒。

s*i2013-05-16 07:05

2 楼

学术版也同求

【在 s*i 的大作中提到】

: 更新成多少次老鼠实验次数了。
: 【以下文字转载自 PDA 讨论区】
: 发信人: sui (黑圈圈), 信区: PDA
: 标题: 牛人们，进来帮助解数学题啦！
: 发信站: BBS 未名空间站 (Thu May 16 15:26:55 2013, 美东)
: 现有酒 n 瓶。其中可能有少量几瓶（m）含有铊毒 (n > m)。
: 作为一个千老，你有老鼠若干。
: 你可以取多瓶酒滴混合喂老鼠。有毒就死。
: 求解，怎么做才能最节省老鼠实验次数而验出哪瓶有毒。

b*e2013-05-16 07:05

3 楼

n
【在 s*i 的大作中提到】

: 学术版也同求

s*i2013-05-16 07:05

4 楼

n > m
原文已改

[发表自未名空间手机版 - m.mitbbs.com]

【在 b*****e 的大作中提到】

: n

M*n2013-05-16 07:05

5 楼

那不就二进制么

【在 s*i 的大作中提到】

: n > m
: 原文已改
:
: [发表自未名空间手机版 - m.mitbbs.com]

s*i2013-05-16 07:05

6 楼

展开说说？

[发表自未名空间手机版 - m.mitbbs.com]

【在 M******n 的大作中提到】

: 那不就二进制么

M*n2013-05-16 07:05

7 楼

例如8瓶，编号01234567
换成二进制
000
001
010
011
100
101
110
111
第一列为1的瓶喂给老鼠1，第二列为1的瓶喂给老鼠2，第三列为1的瓶喂给老鼠3，看死
几只就知道是第几瓶了

【在 s*i 的大作中提到】

: 展开说说？
:
: [发表自未名空间手机版 - m.mitbbs.com]

m*02013-05-16 07:05

8 楼

m 只老鼠，慢慢喝，喝到哪瓶老鼠挂了，那瓶就有毒。

【在 s*i 的大作中提到】

: 展开说说？
:
: [发表自未名空间手机版 - m.mitbbs.com]

j*k2013-05-16 07:05

9 楼

直觉觉得是m！

F*u2013-05-16 07:05

10 楼

全都混一块就都有毒了
省得记错了闹心

【在 s*i 的大作中提到】

: 展开说说？
:
: [发表自未名空间手机版 - m.mitbbs.com]

R*d2013-05-16 07:05

11 楼

brutal but true

【在 m****0 的大作中提到】

: m 只老鼠，慢慢喝，喝到哪瓶老鼠挂了，那瓶就有毒。

s*i2013-05-16 07:05

12 楼

就是说3只就够了？
我喜欢这个算法！

【在 M******n 的大作中提到】

: 例如8瓶，编号01234567
: 换成二进制
: 000
: 001
: 010
: 011
: 100
: 101
: 110
: 111

R*d2013-05-16 07:05

13 楼

i thought it depends on how many of them have thallium in them

【在 s*i 的大作中提到】

: 就是说3只就够了？
: 我喜欢这个算法！

s*i2013-05-16 07:05

14 楼

对呀。他这个解不对！

【在 R******d 的大作中提到】

: i thought it depends on how many of them have thallium in them

R*d2013-05-16 07:05

15 楼

m is unknown, so it depends on m

【在 s*i 的大作中提到】

: 对呀。他这个解不对！

M*n2013-05-16 07:05

16 楼

是诶...那大概只能二分法了...

【在 R******d 的大作中提到】

: i thought it depends on how many of them have thallium in them

R*d2013-05-16 07:05

17 楼

they ask for how many rats, so it really doesn't matter

【在 M******n 的大作中提到】

: 是诶...那大概只能二分法了...

M*n2013-05-16 07:05

18 楼

所以就是n只？
考虑极端情况，m=n，似乎真得要n只才能定论

【在 R******d 的大作中提到】

: they ask for how many rats, so it really doesn't matter

s*i2013-05-16 07:05

19 楼

更新成老鼠实验次数了。这个更真实些。

[发表自未名空间手机版 - m.mitbbs.com]

【在 R******d 的大作中提到】

: they ask for how many rats, so it really doesn't matter

R*d2013-05-16 07:05

20 楼

m right? there are m number of thallium,

【在 M******n 的大作中提到】

: 所以就是n只？
: 考虑极端情况，m=n，似乎真得要n只才能定论

M*n2013-05-16 07:05

21 楼

我以为m是未知的...

【在 R******d 的大作中提到】

: m right? there are m number of thallium,

R*d2013-05-16 07:05

22 楼

binary tree?

【在 s*i 的大作中提到】

: 更新成老鼠实验次数了。这个更真实些。
:
: [发表自未名空间手机版 - m.mitbbs.com]

F*u2013-05-16 07:05

23 楼

如果m不知道，那种共有2^n种可能，二分法需要n只老鼠
如果m已知，总共n choose m中可能，二分法需要log(n choose m)吧
worst case是m=n/2
n增大时log(n choose m)趋近于n

【在 M******n 的大作中提到】

: 所以就是n只？
: 考虑极端情况，m=n，似乎真得要n只才能定论

R*d2013-05-16 07:05

24 楼

that is why you need to find out by feeding them one by one, until it dies,
take that bottle out and do it again. if you know the value of m, you can
save one rat, which is m-1

【在 M******n 的大作中提到】

: 我以为m是未知的...

R*d2013-05-16 07:05

25 楼

actually, if m is known, the best you can do it 0 rat

,

【在 R******d 的大作中提到】

: that is why you need to find out by feeding them one by one, until it dies,
: take that bottle out and do it again. if you know the value of m, you can
: save one rat, which is m-1

M*n2013-05-16 07:05

26 楼

老鼠酒精中毒怎么办...

,

【在 R******d 的大作中提到】

: that is why you need to find out by feeding them one by one, until it dies,
: take that bottle out and do it again. if you know the value of m, you can
: save one rat, which is m-1

R*d2013-05-16 07:05

27 楼

soak it with cold water and wake it up, continue

【在 M******n 的大作中提到】

: 老鼠酒精中毒怎么办...
:
: ,

s*i2013-05-16 07:05

28 楼

milstein的解，比如m=1的话（也就是说最多一瓶，上限），就是 log2(n)。我觉得是
正确的。
[发表自未名空间手机版 - m.mitbbs.com]

R*d2013-05-16 07:05

29 楼

if m is known, say 2 out of 5 bottles have thallium, if you are lucky that
the rat survive after 3 bottles, you have 2 left and certainly you can
confirm by feeding the rest, and you can even reconfirm again by feeding
them to another rat

【在 s*i 的大作中提到】

: milstein的解，比如m=1的话（也就是说最多一瓶，上限），就是 log2(n)。我觉得是
: 正确的。
: [发表自未名空间手机版 - m.mitbbs.com]

s*i2013-05-16 07:05

30 楼

意思是n-m？太多了。

[发表自未名空间手机版 - m.mitbbs.com]

【在 R******d 的大作中提到】

: if m is known, say 2 out of 5 bottles have thallium, if you are lucky that
: the rat survive after 3 bottles, you have 2 left and certainly you can
: confirm by feeding the rest, and you can even reconfirm again by feeding
: them to another rat

M*n2013-05-16 07:05

31 楼

理解了，这个做法不错

【在 F*********u 的大作中提到】

: 如果m不知道，那种共有2^n种可能，二分法需要n只老鼠
: 如果m已知，总共n choose m中可能，二分法需要log(n choose m)吧
: worst case是m=n/2
: n增大时log(n choose m)趋近于n

M*n2013-05-16 07:05

32 楼

ls有人说了，m已知的情况下就是log2(Cnm)

【在 s*i 的大作中提到】

: milstein的解，比如m=1的话（也就是说最多一瓶，上限），就是 log2(n)。我觉得是
: 正确的。
: [发表自未名空间手机版 - m.mitbbs.com]

s*i2013-05-16 07:05

33 楼

不是log2(Pnm)吗？
具体到8选2的case，是个怎样的排列？

[发表自未名空间手机版 - m.mitbbs.com]

【在 M******n 的大作中提到】

: ls有人说了，m已知的情况下就是log2(Cnm)

i*a2013-05-16 07:05

34 楼

你一群生物千老, 死脑经. 直接问SW不就知道哪瓶有毒了

【在 s*i 的大作中提到】

s*i2013-05-16 07:05

35 楼

细想，如果肯定有一瓶的话，三个都没死，推定是第一瓶有毒。但是因为原题有1瓶是*
最大可能*。那么实际操作，应该还得再测一下第一瓶本身，因为没有
任何一列含有第一瓶。所以最终是：
ceiling of log2(n) + 1。
不知道是不是这样？

[发表自未名空间手机版 - m.mitbbs.com]

【在 M******n 的大作中提到】

: 例如8瓶，编号01234567
: 换成二进制
: 000
: 001
: 010
: 011
: 100
: 101
: 110
: 111

M*n2013-05-16 07:05

36 楼

最大可能似乎就很复杂了，我再想想

是*

【在 s*i 的大作中提到】

: 细想，如果肯定有一瓶的话，三个都没死，推定是第一瓶有毒。但是因为原题有1瓶是*
: 最大可能*。那么实际操作，应该还得再测一下第一瓶本身，因为没有
: 任何一列含有第一瓶。所以最终是：
: ceiling of log2(n) + 1。
: 不知道是不是这样？
:
: [发表自未名空间手机版 - m.mitbbs.com]

F*u2013-05-16 07:05

37 楼

仔细想了想，所有case是没法严格二分的，所以实际上log(Cnm)是个下限
8选2的话
12 13 14 15 16 17 18
23 24 25 26 27 28
34 35 36 37 38
45 46 47 48
56 57 58
67 68
78
最开始选2瓶最接近二分，比如开始把1和2混在一起，把所有情况分成7+6 和5+4+3+2+1
即有毒的13种可能无毒的话15种情况
下面那15种情况实际上跟6选2是一样的，再分还是选2瓶，比如3 4混在一起
那就分成了9和6，9种情况已经无法用3次二分区分了，必须得4次
所以n=8 m=2的时候是需要6次才能找到

【在 s*i 的大作中提到】

: 不是log2(Pnm)吗？
: 具体到8选2的case，是个怎样的排列？
:
: [发表自未名空间手机版 - m.mitbbs.com]

M*n2013-05-16 07:05

38 楼

好像还是不对，例如1和3有毒，那一开始你的7+6和5+4+3+2+1都有毒，然后你得13选1
和15选1

+1

【在 F*********u 的大作中提到】

: 仔细想了想，所有case是没法严格二分的，所以实际上log(Cnm)是个下限
: 8选2的话
: 12 13 14 15 16 17 18
: 23 24 25 26 27 28
: 34 35 36 37 38
: 45 46 47 48
: 56 57 58
: 67 68
: 78
: 最开始选2瓶最接近二分，比如开始把1和2混在一起，把所有情况分成7+6 和5+4+3+2+1

F*u2013-05-16 07:05

39 楼

不是同时啊
他问次数
先看1+2，有毒是一种处理，没毒是另一种
没毒是再看3+4

1

【在 M******n 的大作中提到】

: 好像还是不对，例如1和3有毒，那一开始你的7+6和5+4+3+2+1都有毒，然后你得13选1
: 和15选1
:
: +1

M*n2013-05-16 07:05

40 楼

那例如1+2有毒，然后怎么处理？

【在 F*********u 的大作中提到】

: 不是同时啊
: 他问次数
: 先看1+2，有毒是一种处理，没毒是另一种
: 没毒是再看3+4
:
: 1

F*u2013-05-16 07:05

41 楼

那就只有13种情况了，单独看1又没有毒
分成7种或者6种
剩下的比较简单了

【在 M******n 的大作中提到】

: 那例如1+2有毒，然后怎么处理？

M*n2013-05-16 07:05

42 楼

我没理解错的话，
1是指混合12 13 14 15 16 17 18？
2是指混合23 24 25 26 27 28？
然后再混合1+2？
那不就八瓶全混进去了，肯定有毒啊...

【在 F*********u 的大作中提到】

: 那就只有13种情况了，单独看1又没有毒
: 分成7种或者6种
: 剩下的比较简单了

F*u2013-05-16 07:05

43 楼

每次从原来的瓶子里取一点出来混合

【在 M******n 的大作中提到】

: 我没理解错的话，
: 1是指混合12 13 14 15 16 17 18？
: 2是指混合23 24 25 26 27 28？
: 然后再混合1+2？
: 那不就八瓶全混进去了，肯定有毒啊...

M*n2013-05-16 07:05

44 楼

真是不错的算法，我看看怎么推广之

【在 F*********u 的大作中提到】

: 每次从原来的瓶子里取一点出来混合

M*n2013-05-16 07:05

45 楼

不对...n=8, m=2，直接一瓶一瓶地试也6次就够了...

【在 M******n 的大作中提到】

: 真是不错的算法，我看看怎么推广之

c*r2013-05-16 07:05

46 楼

一只老鼠慢慢喝不就行了？

【在 m****0 的大作中提到】

: m 只老鼠，慢慢喝，喝到哪瓶老鼠挂了，那瓶就有毒。

F*u2013-05-16 07:05

47 楼

这个算法在n增大的时候才能体现出作用啊

【在 M******n 的大作中提到】

: 不对...n=8, m=2，直接一瓶一瓶地试也6次就够了...

F*u2013-05-16 07:05

48 楼

而且一瓶一瓶的试，到6次的时候如果只有1个有毒怎么办

【在 M******n 的大作中提到】

: 不对...n=8, m=2，直接一瓶一瓶地试也6次就够了...

f*e2013-05-16 07:05

49 楼

【在 s*i 的大作中提到】

f*e2013-05-16 07:05

50 楼

酒一共C(n,m)状态，老鼠生或死两种状态，所以需要试验次数log2[C(n,m)]

【在 s*i 的大作中提到】

s*i2013-05-16 07:05

51 楼

一共是
C(n, m) + C(n, m-1) ..., + C(n， 1）+ 1 种状态；因为m是上限
然后log2之。
请指正！

【在 f*********e 的大作中提到】

: 酒一共C(n,m)状态，老鼠生或死两种状态，所以需要试验次数log2[C(n,m)]

l*s2013-05-16 07:05

52 楼

F(n,m) = 当m为已知数时，最少试验次数。
T(n,m) = 当m为已知上限时，1为下限时，最少试验次数。
F(n,m)=MIN{ F1(n,m), F2(n,m),…}
T(n,m)=MIN{ T1(n,m), T2(n,m),…}
F1,T1: 逐瓶试验，
F2,T2: 两分法。
其他方法估计不会优于这两种方法中较少的试验次数。
F1(n,m) =n-m,
T1(n,m) =n-1,
F2(n,1) =log2(n)
F2(n,m)=2*(m-1)*( log2(n)-P)+2^(P+1)-2, P=CEIL[log2(m-1)]
T2(n,m)= F2(n,m)+m-1
楼上有按照可能的试验结果给出 F(n,m)=log2[C(n,m)],
这是理论上的最低上限，但除了m=1, 设计不出可行的方案。
最简单的例子是n=4, m=3. log2[C(4,3)]= log2[4]=2. 设计不出可行的2次试验的方
案。

s*i2013-05-16 07:05

53 楼

大牛！赞。我觉得最后一个特别有道理。

【在 l*******s 的大作中提到】

: F(n,m) = 当m为已知数时，最少试验次数。
: T(n,m) = 当m为已知上限时，1为下限时，最少试验次数。
: F(n,m)=MIN{ F1(n,m), F2(n,m),…}
: T(n,m)=MIN{ T1(n,m), T2(n,m),…}
: F1,T1: 逐瓶试验，
: F2,T2: 两分法。
: 其他方法估计不会优于这两种方法中较少的试验次数。
: F1(n,m) =n-m,
: T1(n,m) =n-1,
: F2(n,1) =log2(n)

l*s2013-05-16 07:05

54 楼

F(n,m) = 当m为已知数时，最少试验次数。
T(n,m) = 当m为已知上限时，1为下限时，最少试验次数。
F(n,m)=MIN{ F1(n,m), F2(n,m),…}
T(n,m)=MIN{ T1(n,m), T2(n,m),…}
F1,T1: 逐瓶试验，
F2,T2: 两分法。
其他方法估计不会优于这两种方法中较少的试验次数。
F1(n,m) =n-m,
T1(n,m) =n,
F2(n,1) =T2(n,1) =log2(n)
F2(n,2) =T2(n,2) =2*log2(n)
F2(n,m>2)= 2*(m-1)*(log2(n)-P)+2^(P+1)-3, P=CEIL[log2(m-1)]
T2(n,m>2)= F2(n,m)+1
有按照可能的试验结果给出 F(n,m)=log2[C(n,m)],
这是理论上的最低上限，但除了m=1, 设计不出可行的方案。
最简单的例子是n=4, m=3. log2[C(4,3)]= log2[4]=2. 设计不出可行的2次试验的方
案。