IQrace 版 (精华区)

发信人: ciel (二分之根号五减一℃·冬天来啦), 信区: IQrace
标  题: 称小球问题终结----m次称出(3^m-1)/2个球
发信站: 哈工大紫丁香 (2003年10月25日14:24:59 星期六), 站内信件

对于N(m)=(3^m-1)/2个小球，现在我们来寻求m次的解法。
首先，对于m=2的情况，相当于四个小球来称两次的情况，这个已经讨论过多次了，也很
    简单，在此略去?
其次，若m<=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),即已知的标准球数不小于未知球数?
           所以在以后的测量中就相当于任意给定标准球的情况，由前面的引理二可知
           对于[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球放左边?
                   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球中或在右边的同样
           第二次用3^(k-2)个A球加[3^(k-2)-1]/2个B球放左边?
                   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。
有兴趣的人可以验证一下m=3,N=13的情况----该情况已经被反复拿出来讨论过了。

--
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.228.216]
※ 修改:·ciel 於 10月25日14:25:20 修改本文·[FROM: 202.118.228.216]