对于N(m)=(3^m-1)/2个小球,现在我们来寻求m次的解法。。。

scorpio (scorpio)
本文发表在 rolia.net/zh 相约加拿大网上社区枫下论坛
首先,对于m=2的情况,相当于四个小球来称两次的情况,这个已经讨论过多次了,也很
简单,在此略去?nbsp;
其次,若m?lt;=k-1时,假定对于N(k-1)=(3^(k-1)-1)/2个球的情况我们都有解法。
现在来考虑m=k的情况。
第一次称取[3^(k-1)-1]个球放在天平天平两端,则:
如果平衡,获得[3^(k-1)-1]个标准球,坏球在剩下的[3^(k-1)+1]/2个中。由于
[3^(k-1)-1]>=[3^(k-1)+1]/2,(k>=2),即已知的标准球数不小于未知球数?nbsp;
所以在以后的测量中就相当于任意给定标准球的情况,由前面的引理二可知
对于[3^(k-1)+1]/2的情况(k-1)次可解。
如果不平衡,大的那方记做A,小的那方记作B。标准球记做C.
则现在我们有[3^(k-1)-1]/2个A球和B球,有[3^(k-1)+1]/2个C球。
第二次用3^(k-2)个A球加[3^(k-2)-1]/2个B球放左边?nbsp;
3^(k-2)个C球加[3^(k-2)-1]/2个A球放右边。
如果左边大于右边,则说明是在左边的3^(k-2)个A球中质量大的为坏球;
如果左边等于右边,则说明是在第二次称时没用的3^(k-2)个B球中质量轻
的为坏球。以上两种情况都可以再用三分法(k-2)次解决,加上前两
次共k次解决。
如果左边小于右边,则坏球在左边的[3^(k-2)-1]/2个B球中或在右边的同样
数目的A球中。此时的情况和第二次开始时类似(只不过是k-1变成k-2).
用相同的办法一直往下追溯到一个A球和一个B球一次区分的情况,这时
只需拿A球和标准球比较以下就行了。
因此在这种情况下也是可以最终用k次解决的。
由以上两步加上数学归纳法知,对于N(m)=(3^m-1)/2的情况,称m次是可以称出来的。

由这个解法加上前面所给出的上界Nmax(m)<=(3^m-1)/2,知称m次能解决的最大的小球数
Nmax(m)=(3^m-1)/2。
更多精彩文章及讨论,请光临枫下论坛. 网址: rolia.net/zh
(#177678@0)
2001-8-23 -05:00

回到话题: 13个球,其中1个和其它球重量不同,如何用天平在3次内把它找出来?

回到论坛: HOME枫下论坛枫下论坛主坛枫下沙龙休闲娱乐

URL:   
http://www.rolia.net/zh/post.php?f=0&p=177678