精华区文章阅读

发信人: llhhxht (绿林好汉), 信区: Math
标  题: 称小球问题终结----关于所能解决的上限
发信站: 哈工大紫丁香 (Tue Feb 11 12:28:51 2003) , 转信

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

------------------------------------------------------------------------------
--
发信人: yuhuan (玻璃罩子), 信区: Mathematics
标  题: 称小球问题终结----关于所能解决的上限   zxl (...(转载)
发信站: 北大未名站 (2001年06月28日14:37:39 星期四), 站内信件

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

发信人: idle (回归线), 信区: GreatTurn
标  题: 称小球问题终结----关于所能解决的上限
发信站: BBS 水木清华站 (Sat Jul 25 08:29:09 1998)

现在来求m次所能解决的上限Nmax(m)问题。
为解决这个问题，我们给出几个引理。

引理一：无论加上什么其他的附加条件，只要k个球中的任一个都有可能是坏球（概率不
为0），则当k>3^L时，称L次是称不出来的。这里的附加条件包括已知坏球是否重于好球,

除k个未知球外还提供若干个标准球，以及k个球中某些的质量和大于另外一些的和等等，

只要在这些条件下k个球中的任一个都还有可能是坏球就可以是引理所说的附加条件。
证明：很显然，若k>3^L，则哪个球是坏球一共有k中情况，而称L次一共有3^L种情况，
由k>3^L知不可能一定分辨出哪个球是坏球。

引理二：如果另外在提供任意多个标准球（即在N个未知球外还任给标准球作"砝码"用）?
        则称m次最多能从N1max(m)=(3^m+1)/2个球中找出坏球来。
证明：对该引理的证明可以采用数学归纳法。
      当m=1时，显然若只有两个球，则任挑一个与另外的标准球比较（额外提供的，不是

          两个中的），若相等则是剩下那一个，若不等则是这一个。所以N1max(1)>=2。

          而对于三个球的情况，如果第一次称用了两个或三个未知球，则无法判断出用

          过的球中谁是坏球（只称一次），而如果第一次称只用了一个未知球，则剩下

          的两个球无法区分。因此一次不能解决三个球的问题。所以N1max(1)<3。
          由N1max(1)<3和N1max(1)>=2知，N1max=2。
      设当m<=k-1时命题都成立，则考虑m=k的情况。
           第一次称不能使用超过3^(k-1)个未知球，否则如果坏球在这超过3^(k-1)个
           球中的话，由引理一，在剩下的(k-1)次中不能肯定找出这个坏球来?
    另外，若第一次称碰到的都是好球，则第一次称后的结果就嵌嗵峁┝艘恍?
  标准球（这个结果对已经提供了任意个标准球的情况是毫无意义的）和缩小
           坏球的范围到剩下的球中。由归纳假设，剩下的球的数目不超过N1max(k-1)
           才能保证一定能称出来。所以：N1max(k)<=3^(k-1)+N1max(k-1)=(3^k+1)/2。

           如果有(3^k+1)/2个未知球，则第一次将3^(k-1)个未知球和提供的3^(k-1)个

           未知球比较：如果相等，则坏球在剩下的N1max(k-1)个中，由归纳假设能分
           出来；如果不等，则坏球在这3^(k-1)个中，但是同时知道了坏球是轻还是
           重，由三分法可以很容易用k-1次找出来。所以对于(3^k+1)/2个未知球的情
           况，是能够用k次找出坏球来的。即N1max(k)>=(3^k+1)/2.
           由前面的推导知，N1max(k)=(3^k+1)/2。所以m=k时命题也成立。
     由数学归纳法,所以N1max(k)=(3^k+1)/2对所有的自然数k都成立。

引理二得证。

引理三：Nmax(m)<=(3^m-1)/2。(m>=2)
证明：在原来的称小球问题中，起初没有提供标准球，所以第一次称的数目必须是偶数，

      由和引理二中推导N1max(m)时类似，有如下结论：
      Nmax(m)<=N1max(m-1)       +               [3^(m-1)-1]
               ^^^^^^^^^^                       ^^^^^^^^^^^
           若第一次称平衡了最多剩下的球数   第一次称最多使用的球数，必须是偶数

      所以Nmax(m)<=(3^m-1)/2=N1max(m)-1。命题得证。

到此为止，我们求出了称小球问题的一个上界Nmax(m)<=(3^m-1)/2。（m>=2)
在后面我们将证明这是一个上确界，即Nmax(m)=(3^m-1)/2。
对于m=1的情况，由于必须有两个以上球（否则无所谓好坏球），所以一次是怎么也称不
出来的，因此我们不讨论m=1的情况。

--

                玉石犹蒙昧，那堪小悔多。终无咎，笑呵呵。

※ 来源:·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 版 (精华区)