IQrace 版 (精华区)

发信人: ciel (二分之根号五减一℃·冬天来啦), 信区: IQrace
标  题: 称小球问题终结----关于所能解决的上限
发信站: 哈工大紫丁香 (2003年10月25日14:24:02 星期六), 站内信件

现在来求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]
               ^^^^^^^^^^                       ^^^^^^^^^^^
           若第一次称平衡了最多剩下的球数   第一次称最多使用的球数，必须是偶数
     由数学归纳法,所以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.hit.edu.cn·[FROM: 202.118.228.216]