精华区文章阅读

发信人: llhhxht (绿林好汉), 信区: Math
标  题: 称小球问题终结----m次称出(3^m-1)/2个球
发信站: 哈工大紫丁香 (Tue Feb 11 12:29:25 2003) , 转信

文章阅读北大未名站精华区

------------------------------------------------------------------------------
--
发信人: yuhuan (玻璃罩子), 信区: Mathematics
标  题: 称小球问题终结----m次称出(3^m-1)/2个球 zxl (...(转载)
发信站: 北大未名站 (2001年06月28日14:37:45 星期四), 站内信件

【以下文字转载自 post 讨论区】
【原文由 Yuhuan.bbs@smth.org 所发表】
来  源: from smth (bbs.net.tsinghua.edu.cn [166.111.8.238])
日  期: Thu Jun 28 14:35:59 2001

发信人: idle (回归线), 信区: GreatTurn
标  题: 称小球问题终结----m次称出(3^m-1)/2个球的解法
发信站: BBS 水木清华站 (Sat Jul 25 09:10:51 1998)

对于N(m)=(3^m-1)/2个小球，现在我们来寻求m次的解法。
首先，对于m=2的情况，相当于四个小球来称两次的情况，这个已经讨论过多次了，也很
    简单，在此略去?其次，若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),即已知的标准球数不小于未知球数?
           所以在以后的测量中就相当于任意给定标准球的情况，由前面的引理二可知
           对于[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球中或在右边的同样

               数目的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 水木清华站 bbs.net.tsinghua.edu.cn·[FROM: 162.105.160.126]
--
※ 转载:·北大未名站 bbs.pku.edu.cn·[FROM: 162.105.106.53]

------------------------------------------------------------------------------
--
分类讨论区全部讨论区

--

※ 来源:．哈工大紫丁香 http://bbs.hit.edu.cn [FROM: 218.9.120.96]

Math 版 (精华区)