称球问题一般解法

《称球问题一般解法》由会员分享，可在线阅读，更多相关《称球问题一般解法（6页珍藏版）》请在金锄头文库上搜索。

1、称球问题一般解法称球问题一般会有以下3种变形：1、n个球，其中有一个坏的，知道是轻还是重，用天平称出坏球来。2、n个球，其中有一个坏的，不知是轻还是重，用天平称出坏球来。3、n个球，其中有一个坏的，不知是轻还是重，用天平称出坏球来，并告知坏 球是轻还是重。对于上面3种情况，称量n次，最多可以在几个球中找出坏球来？答案：分别为：3X, (3X - 1)/2, (3X - 3)/2.称法体现在下面的证明中：、天平称重，有两个托盘比较轻重，加上托盘外面，也就是每次称重有3个结 果，就是In3/ln2比特信息。n个球要知道其中一个不同的球，如果知道那个不 同重量的球是轻还是重，找出来的话那就是n个结果

2、中的一种,就是有ln(n)/ln2 比特信息，假设我们要称k次，根据信息理论：k*ln3/ln2=ln(n)/ln2, 解得 k=ln(n)/ln3这是得到下限，可以很轻易证明满足条件的最小正整数k就是所求。比如称 3次知道轻重可以从33二27个球中找出不同的球出来。具体称法就是：每次再待定的n个球中取(n+2)/3个球，放在天平左边； (n+2)/3个球放在天平右边。(注：x 表示不大于x的最大整数。)二、对于(m) = (3，n)-L)/2个小球，现在我们来寻求m次的解法。首先，对于2的情况，相当于四个小球来称两次的情况，这个已经讨论过多次 了，也很简单，在此略去其次，若时，假定对于(卜1

3、)=(3飞1)-1)/2个球的情况我们都有解 法。现在来考虑m=k的情况。第一次称取37k-l)-1个球放在天平天平两端，则：如果平衡,获得3Xk-l)T个标准球,坏球在剩下的3/kT)+l/2个 中。由于37k-l)-l=37k-l)+l/2, (k=2),即已知的标准球数不小于未 知球数；所以在以后的测量中就相当于任意给定标准球的情况，由前面的引理 二可知对于3k-l)+l/2的情况(k-l)次可解。如果不平衡，大的那方记做A,小的那方记作B。标准球记做C.则现在我们有3(卜1)-1/2个A球和B球，有0 (k-l)+1/2个C球。第二次用3(k-2)个A球加3、(k-2)-1/2个B球放

4、左边；3- (k-2)个C球加3一 (卜2)-1/2个A球放右边。如果左边大于右边，则说明是在左边的3、(k-2)个A球中质量大的 为坏球；如果左边等于右边，则说明是在第二次称时没用的37k-2)个B球 中质量轻的为坏球。以上两种情况都可以再用三分法(2)次解决, 加上前两次共k次解决。如果左边小于右边，则坏球在左边的3一(2)-1/2个B球中或在 右边的同样数目的A球中。此时的情况和第二次开始时类似(只不过是k-l 变成k-2).用相同的办法一直往下追溯到一个A球和一个B球一次区分的情 况，这时只需拿A球和标准球比较以下就行了。因此在这种情况下也是可以最终用k次解决的。由以上两步加上数学归纳

5、法知，对于N(m) = (3-L)/2的情况，称m次是可以称 出来的。由这个解法加上前面所给出的上界max(m) (3-1)/2,知称m次能解决的最 大的小球数Nmax (m) = (3 - mT) /2。有兴趣的人可以验证一下m=3,X=13的情况一一该情况已经被反复拿出来讨论过 了。大家好，我们来继续昨天的问题。现在我要给出通解啦。为了简化下面的过程， 我们假设小球的个数正好是-3)/2。首先我们把小球分成数量相等的三组&人BiBn Cf,其中n二-1)/2。 笫一次使用天平的时候，不妨把A组和B组分别放在天平左右.盘。如果天平左低 右.高，那么有可能因为左边n个小球之一较重，也可能因为右

6、边n个小球之一较 轻。反过来也是一样。这种时候，转到下面的情况处理。而天平平衡的时候, 则坏球一定在剩下n个小球中，(2)讨论了这种问题。【情况1】这时的条件是：已知中一个球较重，或者艮Bn中一个球较轻, 其中叩(3皿-1)/2。我们把可以在C中任意拿出一个好球(C中的都是好球嘛) 放到B中去。然后由情况讨论接下来的处理方法。【情况2】这时的条件是：已知坏球中，且不知轻重关系，其中n二(3工1)/2。 我们把C分作三组机须bb. ac“ 其中hf(3八-1)/2。注意看啦，C组要 比a, b两组多出一个。怎么？我们昨天不是说这种情况没办法完成吗？但是， 我们现在多了一项武器一一好球。对，我们可

7、以从已经判断为一定是好球的A, B组中任意拿出一个好球，和a一起放到天平左盘，把c组放到天平右盘，如果 天平左低右高，那么一定是a组中m个球较重或者c组重m+1个球较轻，反过来 也于这个类似，情况正是讨论这种问题的。如果平衡的话，说明b组的 111=(3-1)/2个小球是问题小球，这不正好和我们当前要讨论的问题一样吗？所 以我们又回到了情况(2)。【情况3】这种情况最为复杂，我们知道的是电电中一个小球较重，或者5 J1中的一个小球较轻，其中m=(3：-Ll)/2。另外，还有一个标准小球。我们把a 分为。1Q5B 1B二丫 1丫 m三组；把c分为 i 2 1，C iC ” 其中/(31-1)/2

8、。把a 放再天平左盘，B 放在天平右盘。要是天平平衡, 说明要么Y组的s+1个小球较重，要么C组的s个小球较轻，这恰恰是一个更 小规模的情况(3)。要是天平不平衡呢？以左低右高为例，左盘是a 而右盘是 B 这种情况不可能是由较重引起的一一如果中的球有坏球，它只会比 好球轻。同样也不会是B较轻引起的。所以，这个时候，要么是Q中的s个球 之一较重，要么是中的s+1个球之一较轻。这同样是情况(3)。好了，到这里所有的情况都有了一个递归的算法。可以把问题分解直到下面这些 情况：1 .使用一次天平，一个标准球，判断一个坏球是轻还是重。2 .有两个球，要么其中一个球较重，要么其中一个球较轻，仍然有标准球可

9、 以利用，使用一次天平找到坏球。3 .三个球，要么是1号与2号球之一比较重，要么是3号球比较轻。使用一 次天平找到坏球。相信这三个问题相当简单吧。什么，你不知道最后一种怎么做？呃，1号2号上 天平，要是倾斜了，低的那边是坏球；平衡的话好了，你可以尝试使用五次天平解决120个球了。不过，一定要先找到一张非常 非常大的纸。另外补充一点：对于(3：-1)/2个小球，如果另外给定一个标准球的话，就能以情 况(2)为入口，在t次内找到坏球，并得知其偏重还是偏轻。而少了一个标准球, 就只能保证找到坏球，网路上的13球问题就是这样的。称球问题的一般解法称球问题相信大家已经很熟悉了，并且已经知道从12个球中找

10、出坏球并判断其轻重最多 只需要3次称量。但如果把球数改变下，比如说13个球，答案又是几次呢？本文将对这一问 题进行“深入”分析。为了后面叙述方便，先在这里把般化后的问题重复下：有m (m3)个球，记为尔、生、”，其中有且仅有一个坏球，其重量与其他的不 同，现使用无硅码的天平进行称量，令n为称量次数，问：能确保找到环球并指出它与好球的轻 重关系的n的最小值是多少？先来看理论上要多少次。每次称量有左边轻、平衡和右边轻共3种可能的情况，而坏球 的可能结果有5轻、5重、生轻、生重、5轻、5重等共2m种。因此，根据商农的信息论， 此问题的焰就是需要的称量次数，又因为n是整数，所以有：n = F10S 3

11、不过理论终归是理论，直接拿到现实生活中往往行不通。个很简单的情况：4个球， 上面的公式说2次称量就够了。但你可以想想办法，反正我是没找到两次解决问题的方案。那，是理论错了吗？唔，我可不敢怀疑商农，我只敢怀疑我自己。来看看我们错在哪了 吧。对4个球的情况，第次称量只有两个可选的方案：方案1： 5放左盘，也放右盘。若不平 衡(由于对称性，只分析左边轻的情况，下同)，则可能的结果还剩牛轻和年重，再称次就 能找到坏球：若平衡，则可能的结果还剩如轻、如重、qi轻和重4个，再套用一下商农的定理, 此时还要称0目3 41=2次。所以方案1被否决。方案2： 5、比放左盘，朱、q,放右盘。此时天 平肯定不会平衡

12、，称量后，可能的结果有牛轻、中轻、3重和5重4个。同样的道理，方案2 也难逃被否决的命运。在4个球这么简单的情况下就撞得满头是包，未免让人难以接受，总结一下经验教训吧， 把上面的分析归纳下并推广到一般情况，就是：整个称量过程中，要达到目的，倒数第k次称 量前的可能结果数h,必须满足条件上面的得出的结论虽然不能让我们找到问题的答案,但却有助于我们确定每次称量的方 案，特别是第次如何做。假设我们计划的称量次数是n,第次在左右两盘中各放x个球，则 保证下面两个不等式同时成立是解决问题的必要条件：2（m-2x）W35（平衡时）2xW3G （不平衡时）把这两个不等式稍加变换，就成了下面的样子：2m -尹

13、1-3周工幺 4 2注意到X是整数，3n-l是奇数，2m是偶数，所以上而的不等式等价于：2m-3nd区5 2321 -1显然，在n 定的情况下，m越大，x的取值范围越小，而当x只能取值 2 时，1n继续增 大，就会导致n次称量找到坏球的计划破产。籍此，可以得出在n 定的情况下m的取值范围： 手,m 12 O发现了吗？现在m的最大值正好比我们最初的结果少r lo同时此结果也与前面 提到的4个球的实际情况相符。但分析半天，我们只证明了 m不在取值范围内时，n次称量不能确保找到环球。那m 在取值范围内的时候，肯定能找到吗？答案是肯定的，不过马上证明它有点难，先来看两个简单 一点的命题。命题1：有A、

14、B两组球，球的个数分别为a、b,且OWb-a於1,已知这些球中有且仅 有个坏球，若它在A组中，则比正常球轻，在B组中则比正常球重。另有一个好球。先使用无 祛码的天平称量，令11=1g3（a + b）,则可以找到个称量方案，使得最多经过n次称量， 就可以找到坏球（此时肯定能指出它与好球的重量关系）。使用数学归纳法证明如下：当n=l时，a、b的取值可能有0, 1、1, 1、1, 2三组，由于还有一-个已知的 好球，所以不难验证此时命题成立。假设当n=k时命题也成立。当n=k+l时。我们将A、B两组球分别尽量平均得分为三组，记为Al、A2、A3、B1、B2和B3。不影响般性，假设这六组球按球数从少到

15、多的排列次序也与前面的顺序致，且A1 有球al个。则第次称量时的称量方案与每组球个数的对应关系如下，其中需要注意的是：在带蓝色的两种情况下，必有I,，否则就与命题的前提不符了。A1A2A3BlB2B3称量方案alalalalalalAl、Bl放左盘:A2、B2放右盘alalalalalal+1Al、Bl放左盘:A2、B2放右盘alalal+1alalal+1Al、B3放左盘:A3、B1放右盘alalal+1alal+1al+1Al、B2放左盘:A2、B3放右盘alal+1allalal+1al+1A2、B2放左盘:A3、B3放右盘alal+1al+1al+1al+1al+1A2、B2放左盘：A3、B3放右盘很明显，不管结果是什么，第次称量之后，问题都能转化为n=k时的情形。所以，命题1是真 命题。前面已经证明 L 2时，n次称量无法