BBS水木清华站: 称小球问题终结(99年微软招聘的考题耶,愿意练脑者请看:http://www.sdfi.edu.cn/tsinghua/greatturn.aix/index.htm)

deepblue (deepblue)
本文发表在 rolia.net/zh 相约加拿大网上社区枫下论坛
关于称小球问题,一般是这样的:
有N个小球外形无区别,但是有一个在质量上与其他的球不一样。用天平称最少m次一定将
不同的球找出来。显然随N增大,m不会减小。现在想解决的问题是对于任何给定的次数m,
找出在该次数下能解决的最大的N值,用Nmax来表示。并给出对应于(Nmax,m)的一种解法.

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

引理一:无论加上什么其他的附加条件,只要k个球中的任一个都有可能是坏球(概率不
为0),则当k>3^L时,称L次是称不出来的。这里的附加条件包括已知坏球是否重于好球,
除k个未知球外还提供若干个标准球,以及k个球中某些的质量和大于另外一些的和等等,
只要在这些条件下k个球中的任一个都还有可能是坏球就可以是引理所说的附加条件。
证明:很显然,若k>3^L,则哪个球是坏球一共有k中情况,而称L次一共有3^L种情况,
由k>3^L知不可能一定分辨出哪个球是坏球。

引理二:如果另外在提供任意多个标准球(即在N个未知球外还任给标准球作"砝码"用)?nbsp;
则称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)次中不能肯定找出这个坏球来?nbsp;
另外,若第一次称碰到的都是好球,则第一次称后的结果就是多提供了一些
标准球(这个结果对已经提供了任意个标准球的情况是毫无意义的)和缩小
坏球的范围到剩下的球中。由归纳假设,剩下的球的数目不超过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的情况。

对于N(m)=(3^m-1)/2个小球,现在我们来寻求m次的解法。
首先,对于m=2的情况,相当于四个小球来称两次的情况,这个已经讨论过多次了,也很
简单,在此略去?nbsp;
其次,若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),即已知的标准球数不小于未知球数?nbsp;
所以在以后的测量中就相当于任意给定标准球的情况,由前面的引理二可知
对于[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球放左边?nbsp;
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的情况----该情况已经被反复拿出来讨论过了。
更多精彩文章及讨论,请光临枫下论坛. 网址: rolia.net/zh
(#48187@0)
2001-4-18 -05:00

回到话题: 智力题

回到论坛: HOME枫下论坛枫下论坛主坛枫下沙龙休闲娱乐

URL:   
http://www.rolia.net/zh/post.php?f=0&p=48187