Math 版 (精华区)

发信人: micheal (平凡的世界), 信区: Math
标  题: 称小球问题的解答(完全版):-))
发信站: 紫 丁 香 (Thu May  4 21:38:47 2000), 转信

呵呵,终于被我拿下了.不过今天没时间写了,明天晚上我来不上.

定理:用天平称m次最多可以在只有一个坏球(重量不同)的n(n=(3^m-1)/2)
     个小球中找出这个坏球,且这里的n是最佳的,不能再大了.
证明:
     (明晚再写,没时间了)

     *_~.

       首先说一下基本思路,我们把一次称量映射成一个n长的向量,此n长向量
由元素{0,1,-1}组成(本文后面提到的向量元素都是取自0,1,-1).映射关系如下.

 1:把n个球编号,1,2,....n
 2:第k次称量对应的向量记为A[k].A[k]的元素按以下方式确定.
   在这次称量中:
   如果第i(i=1,2...n)个小球在左盘,则令A[k](i)=1;
   如果第i(1=1,2...n)个小球在右盘,则令A[k](i)=-1;
   如果第i(i=1,2...n)个小球没有参加称量,令A[k](i)=0.
   这里A[k](i)表示向量A[k]的第i个元素.

   下面我们构造一组满足两个条件的向量组A,为以下的工作做准备

约束条件
1.对任意i,j.A[i]!=-A[j]    ( !=  表示不等)
2.sum(A)=0,即A中所有向量和是零向量.
____________________________________________________________________
|                                                                   |  
| 第一步: 我们首先证明满足这样条件的m长向量个数不会超过n=(3^m-1)/2  |
|___________________________________________________________________|

    我们首先注意到所有的元素取自{-1,0,1}的向量总数是3^m.去掉非零向量,
其余的3^m-1各向量按互为相反向量(记对应元素互为相反数)配对,共有(3^m-1)/2对.
显然根据条件1,每一对中最多取一个元素,这样n<=(3^m-1)/2+1(算上0向量).
    
    下面再说不可能在所有的(3^m-1)/2对中每一对中都取出一个向量来.
    
    用反证法,不然,我们首先考虑所有的向量中第一位元素非零的向量共有多少个, 
显然有2*3^(m-1)个,由于这样的向量必然是两两互为相反数的.所以所有的(3^m-1)/2
对中有2*3^(m-1)/2=3^(m-1)个对第一位取自{1,-1}.这样如果我们在每一对中都取一
个向量的话,我们考虑所有向量的和的第一位元素,其值应该是前面所说的3^(m-1)个首位
非零的向量首位元素之和.而1,-1,3^(m-1)均为奇数,所以其和不可能是偶数零.而由上面
的约束条件2知所有的向量和为零.矛盾.
所以我们知道要满足上面的两个约束条件,n<=(3^m-1)/2

___________________________________________________
|                                                 |
|  第二步:  下面我们证明n=(3^m-1)/2是可以达到的.  |
|_________________________________________________|_

用归纳法.
m=1,n=(3^1-1)/2=1,取(0)
m=2,n=(3^2-1)/2=4,取(0,0),(0,1),(-1,0),(1,-1)

设m=k时成立,就是可以找到(3^k-1)/2个满足条件的k长向量.那么
  m=k+1时,我们在前面说的(3^k-1)/2-1个k长非零向量前分别添加元素-1,0,1,这样就得
到了3[(3^k-1)/2-1]=(3^(k+1)-1)/2-4.易证这些向量也满足前面给出的约束条件.
又由前面的证明知m=k时有一对向量未被选取(即由于前面的奇偶矛盾).设为(R,-R),我们
在她的基础上再构造3个新向量.(1,R),(-1,0..0),(0,-R).再加上全零向量.就得到的
[3^(k+1)-1]/2个满足约束条件的向量组.

*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
*                                                                           *
*     下面用前面构造的向量组来解决m个小球中找出唯一坏球的方法.              *
*                                                                           * 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
首先把所有的向量按列向量的方式写出,每列一个向量.这样有m各行向量排成一个m*n矩阵.

这样每一行就是一个n长行向量,按照本文最开始说的对应关系.我们往盘中放小球(即若
第k个元素为1,则放标号为k的小球在左盘,为-1则放右盘,0不放).并且我们记第k次称量
的结果写在第k行向量的右面.并且按照下面的方式纪录.左面沉则记1,右面沉记-1,平衡
记0.这样就得到了一组m长的结果列向量.

我们说把这个结果列向量与前面的矩阵的每一列相比较,如果与第k列相同,那么可以断言
标号为k的小球是坏球.:-)

     这是因为只有一个坏球,假设是标号为j的球是坏球.由于不知道该球比标准球轻还
是重.
    i)如果重,那么看矩阵的第j列,第s个元素为1,那么根据前面的纪录方法知结果向量
中的第s个元素也为1;第s个元素为-1,结果向量中的相应元素也为-1;第s元素为0,那么结
果向量中的相应元素也为0.
    ii)如果轻,道理相同,不过是1-->-1,-1-->1,0-->0.

因此,我们即使不知道坏小球比标准小球轻还是重,但是结果向量一定等于该小球所对的
列向量或者它的相反向量.故我们得到结果向量后,就得到两个互为相反向量的两个可能
向量.我们在前面的n列中找到与他们其中之一相同的向量,这列向量所对应的小球就是坏
球.


/////////////////////////////////////////////////////////////////////////////
    
说明:
    由于我们的限制条件1,使得每行向量中的1,-1数目一样多,这保证了称量时左右两
盘的球数一样多.

    由于限制条件2,保证了结果列向量所对应的两个互为相反向量的两个向量不能同时
在矩阵中.这就使得我们可以唯一确定坏球.

最后说一下,n=(3^m-1)/2是不能改进的,这由前面的向量构造中可以看出,如果数目增加
,别必然导致出现相反向量对或相同向量,这时由于我们不知道坏球是轻是重,从而无法
在这两个球中做出判断.


           
--


                        海纳百川,有容乃大.
                        壁立千仞,无欲则刚.
                                                       ^^             
                                                      ^^^^   
※ 修改:．micheal 于 May  5 19:50:12 修改本文．[FROM: hitsat.hit.edu.c]
※ 来源:．紫 丁 香 bbs.hit.edu.cn．[FROM: hitsat.hit.edu.c]