haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 科学科学

经典智力题

发布时间:2013-12-22 14:39:58  

称球问题--经典智力题推而广之

说明

这篇文章试图给出称球问题的一个一般

的和严格的解答。正因为需要做到一般和严

格,就要考虑许多平时遇不到的特别情形,jingdianzhilit

所以叙述比较繁琐。如果对读者对严格的证

明没有兴趣,可以只阅读介绍问题和约定记

号的第一、第二节,以及第三节末尾27个球

的例子,和第五节13个球和40个球的解法。

事实上所有的技巧都已经表现在这几个例子

里了。

一、问题

称球问题的经典形式是这样的:

“有十二个外表相同的球,其中有一个坏球,它的重量和其它十 一个有轻微的(但是可以测量出来的)差别。现在有一架没有砝码的 很灵敏的天平,问如何称三次就保证找出那个坏球,并知道它比标准 球重还是轻。”

这可能是网上被做过次数最多的一道智力题了。它的一种解法如 下:

将十二个球编号为1-12。

第一次,先将1-4号放在左边,5-8号放在右边。

1.如果右重则坏球在1-8号。

第二次将2-4号拿掉,将6-8号从右边移到左边,把9-11号放 在右边。就是说,把1,6,7,8放在左边,5,9,10,11放在右边。

1.如果右重则坏球在没有被触动的1,5号。如果是1号, 则它比标准球轻;如果是5号,则它比标准球重。 第三次将1号放在左边,2号放在右边。

1.如果右重则1号是坏球且比标准球轻;

2.如果平衡则5号是坏球且比标准球重;

3.这次不可能左重。

2.如果平衡则坏球在被拿掉的2-4号,且比标准球轻。 第三次将2号放在左边,3号放在右边。

1.如果右重则2号是坏球且比标准球轻;

2.如果平衡则4号是坏球且比标准球轻;

3.如果左重则3号是坏球且比标准球轻。

3.如果左重则坏球在拿到左边的6-8号,且比标准球重。 第三次将6号放在左边,7号放在右边。

1.如果右重则7号是坏球且比标准球重;

2.如果平衡则8号是坏球且比标准球重;

3.如果左重则6号是坏球且比标准球重。

2.如果天平平衡,则坏球在9-12号。

第二次将1-3号放在左边,9-11号放在右边。

1.如果右重则坏球在9-11号且坏球较重。

第三次将9号放在左边,10号放在右边。

1.如果右重则10号是坏球且比标准球重;

2.如果平衡则11号是坏球且比标准球重;

3.如果左重则9号是坏球且比标准球重。

2.如果平衡则坏球为12号。

第三次将1号放在左边,12号放在右边。

1.如果右重则12号是坏球且比标准球重;

2.这次不可能平衡;

3.如果左重则12号是坏球且比标准球轻。

3.如果左重则坏球在9-11号且坏球较轻。

第三次将9号放在左边,10号放在右边。

1.如果右重则9号是坏球且比标准球轻;

2.如果平衡则11号是坏球且比标准球轻;

3.如果左重则10号是坏球且比标准球轻。

3.如果左重则坏球在1-8号。

第二次将2-4号拿掉,将6-8号从右边移到左边,把9-11号放 在右边。就是说,把1,6,7,8放在左边,5,9,10,11放在右边。

1.如果右重则坏球在拿到左边的6-8号,且比标准球轻。 第三次将6号放在左边,7号放在右边。

1.如果右重则6号是坏球且比标准球轻;

2.如果平衡则8号是坏球且比标准球轻;

3.如果左重则7号是坏球且比标准球轻。

2.如果平衡则坏球在被拿掉的2-4号,且比标准球重。 第三次将2号放在左边,3号放在右边。

1.如果右重则3号是坏球且比标准球重;

2.如果平衡则4号是坏球且比标准球重;

3.如果左重则2号是坏球且比标准球重。

3.如果左重则坏球在没有被触动的1,5号。如果是1号, 则它比标准球重;如果是5号,则它比标准球轻。 第三次将1号放在左边,2号放在右边。

1.这次不可能右重。

2.如果平衡则5号是坏球且比标准球轻;

3.如果左重则1号是坏球且比标准球重;

够麻烦的吧。其实里面有许多情况是对称的,比如第一次称时的 右重和右轻,只需考虑一种就可以了,另一种完全可以比照执行。我

把整个过程写下来,只是想吓唬吓唬大家。

稍微试一下,就可以知道只称两次是不可能保证找到坏球的。如 果给的是十三个球,以上的解法也基本有效,只是要有个小小的改动, 就是在这种情况下,在第一第二次都平衡的时候,第三次还是有可能 平衡(就是上面的第2.2.2步),那么我们可以肯定坏球是13号球,可 是我们没法知道它到底是比标准球轻,还是比标准球重。如果给的是 十四个球,我们会发现无论如何也不可能只称三次,就保证找出坏球。

一个自然而然的问题就是:对于给定的自然数N,我们怎么来解有 N个球的称球问题?

在下面的讨论中,给定任一自然数N,我们要解决以下问题:

⑴找出N球称球问题所需的最小次数,并证明以上所给的最小次数的确 是最小的;

⑵给出最小次数称球的具体方法;

⑶如果只要求找出坏球而不要求知道坏球的轻重,对N球称球问题解决 以上两个问题;

还有一个我们并不是那么感兴趣,但是作为副产品的问题是:

⑷如果除了所给的N个球外,另外还给一标准球,解决以上三个问题。

二、记号

我们先不忙着马上着手解决上述问题。先得给出几个定义,尤其 是,要给出比较简单的符号和记法。大家看到上面给出的解法写起来 实在麻烦--想象一下如果我们要用这种方法来描述称40个或1000个 球的问题!

仍旧考虑十二个球的情况和上面举的解法。在还没有开始称第一 次时,我们对这十二个球所知的信息就是其中有一或较轻,或较重的 坏球,所以以下24种情况都是可能的:

1. 1号是坏球,且较重;

2. 2号是坏球,且较重;

??

12. 12号是坏球,且较重;

13. 1号是坏球,且较轻;

14. 2号是坏球,且较轻;

??

24. 12号是坏球,且较轻。

没有其他的可能性,比如说“1、2号都是坏球,且都较重”之类。当 我们按上面解法“先将1-4号放在左边,5-8号放在右边”称过第一次 以后,假设结果是右重,稍微分析一下,就会知道上面的24种情况中, 现在只有8种是可能的,就是

1. 1号是坏球,且较轻;

2. 2号是坏球,且较轻;

3. 3号是坏球,且较轻;

4. 4号是坏球,且较轻;

5. 5号是坏球,且较重;

6. 6号是坏球,且较重;

7. 7号是坏球,且较重;

8. 8号是坏球,且较重。

我们把诸如“1号是坏球,且较重,其他球都正常”和“2号是坏球, 且较轻,其他球都正常”这样的情况,称为一种“布局”,并记为: (1重) 和 (2轻)

我们把“先将1-4号放在左边,5-8号放在右边”这样的步骤,称为一 次“称量”。我们把上面这次称量记为

(1,2,3,4; 5,6,7,8)

(1-4; 5-8)

也就是在括号内写出参加称量的球的号码,并且以分号分开放在左边 和放在右边的球号。在最一开始,我们有24种可能的布局,而在经过 一次称量(1-4; 5-8)后,如果结果是右重,我们就剩下上述8种可能 的布局。我们的目的,就是要使用尽量少的称量,而获得唯一一种可 能的布局--这样我们就知道哪个球是坏球,它是比较重还是比较轻。

这里我们注意到没有必要去考虑两边球数不相等的称量。因为坏 球和标准球重量之间的差别很小,小于标准球的重量,所以当天平两 边球数不一样时,天平一定向球比较多的那边倾斜。所以在进行这样 一次称量之前,它的的结果就可以被预料到,它不能给我们带来任何 新的信息。事实上在看完

现在我们看到,上面关于十二个球问题的解法,其实就是由一系 列称量组成的--可不是随随便便的组合,而是以这样的形式构成的: 称量1

如果右重,则

称量3

??

如果平衡,则

称量2

??

如果左重,则

称量4

??

省略号部分则又是差不多的“如果右重,则??”等等。所以这就提

示我们用树的形式来表示上面的解法:树的根是第一次称量,它有三 个分支(即三棵子树,于是根有三个子节点),分别对应着在这个称 量下的右重、平衡、左重三种情况。在根的三个子节点上,又分别有 相应的称量,和它们的三个分支??如果具体地写出来,就是

|--右--( 1轻)

|--右--(1 ; 2)|--平--( 5重)

| |--左--( )

|

| |--右--( 2轻)

|--右--(1,6-8; |--平--(2 ; 3)|--平--( 4轻)

| 5,9-11)| |--左--( 3轻)

| |

| | |--右--( 7重)

| |--左--(6 ; 7)|--平--( 8重)

| |--左--( 6重)

|

| |--右--(10重)

| |--右--(9 ;10)|--平--(11重)

| | |--左--( 9重)

| |

| | |--右--(12重)

(1-4;5-8)|--平--(1-3; |--平--(1 ;12)|--平--(13轻, 13重)*

| 9-11)| |--左--(12轻)

| |

| | |--右--( 9轻)

| |--左--(9 ;10)|--平--(11轻)

| |--左--(10轻)

|

| |--右--( 6轻)

| |--右--(6 ; 7)|--平--( 8轻)

| | |--左--( 7轻)

| |

| | |--右--( 3重)

|--左--(1,6-8; |--平--(2 ; 3)|--平--( 4重)

5,9-11)| |--左--( 2重)

|

| |--右--( )

|--左--(1 ; 2)|--平--( 5轻)

|--左--( 1重)

(*:对应十三个球的情形。)

这里“右”、“平”和“左”分别表示称量的结果为“右重”、“平 衡”和“左重”所对应的分支。在树的叶子(就是最右边没有子节点 的那些节点)部分,我们标出了“能够到达”这些节点的布局,也就

是说在进行每一节点上的称量时,这个布局所给的结果和通往相对应 的叶子的道路上所标出的“右”、“平”和“左”相符合。从这个图 我们也可以清楚地看到,根下的左分支和右分支是对称的:只需要把 所有的“右”改成“左”,“左”改成“右”,“轻”改成“重”, “重”改成“轻”;节点(1-3; 9-11)下的左分支和右分支也有这个 特点。

(如果有朋友对树理论感兴趣,可以参考随便哪一本图论或者离 散数学的书。在这里我们只用到树理论里最基本的知识,所用的名词 和结论都是相当直观的。所以如果你不知道树理论,用不着特别去学 也可以看懂这里的论证。)

所以给定一棵三分树(就是说除了叶子以外其他的节点都有三个 子节点的树),在每个不是叶子的节点上给定一个称量,并且规定这 个节点下的三个分支(子树)分别对应右重、平衡、左重的情况,我 们就得到了一种称球的方法。我们把这样一棵三分树称为一个“策略” 或一棵“策略树”。你可以给出一个平凡的策略,比如说无论发生了 什么事总是把1号和2号球放在左右两侧来称(在叶子上我们没有写出 相应的布局,用@来代替):

|--右--@A

|--右--(1; 2)|--平--@

| |--左--@

|

| |--右--@

(1; 2)|--平--(1; 2)|--平--@

| |--左--@

|

| |--右--@B

| |--右--(1; 2)|--平--@

| | |--左--@

| |

| | |--右--@

|--左--(1; 2)|--平--(1; 2)|--平--@

| |--左--@

|

| |--右--@

|--左--(1; 2)|--平--@

|--左--@

当然这么个策略没什么用场,只能让我们知道1号球和2号球之间的轻 重关系。另外我们看到,每个分支不一定一样长,上面这棵策略树根 下面左分支就比较长。

一棵树的高度是叶子到根之间的结点数的最大值加一。比如说上

面这个图中,叶子A和根间有1个节点,而叶子B和根间有2个节点,没 有和根之间的节点数超过2的叶子。所以它的高度是2+1=3。前面十二 球解法策略树的高度也是3。一棵没有任何分支,只有根节点的树,我 们定义它的高度是0。

显然,策略树的高度就是实行这个策略所需要的称量的次数。我 们的目的,就是找到一棵“好”的策略树,使得它的高度最小。

什么是“好”策略?我们回过头来再看十二球解法策略树。我们 说过,叶子上的那些布局都是从根开始通向叶子的。比如说布局(7重), 它之所以在那片叶子上是因为按照这个策略,三次称量的结果是“右 左右”;又比如说布局(11重),它之所以在那片叶子上是因为按照这 个策略,三次称量的结果是“平右平”。如果两个布局通向同一片叶 子,那么就是说按照这个策略,三次称量的结果是完全一样的,于是 我们就不能通过这个策略来把这两种布局区分开来。比如说在十三个 球的情况下,(13轻)和(13重)都通向和“平平平”相对应的叶子,这 两个布局中13号球或者轻或者重,于是我们知道13号球一定是坏球, 但是通过这个策略我们不可能知道它到底是轻还是重。

所以对于标准的称球问题(找出坏球并知其比标准球重或轻)的 “好”策略,就是那些能使不同的布局通向不同的叶子的策略。

三、每个球都已知可能为轻或可能为重的情况

先引入一个记号:对于任意实数a,我们用{a}表示大于等于a的最 小整数,比如说{2.5}=3,{4}=4;我们用[a]表示小于等于a的最大整 数,比如说[2.5]=2,[4]=4。

我们首先考虑这样一种布局的集合。假设m,n为两个非负实数,

不同时为0。在编号从1到m+n的m+n个球中,我们知道1到m号球要么是 标准球,要么比标准球重,而m+1到m+n号球要么是标准球,要么比标 准球轻;我们还知道其中有一个是坏球(但不知轻重)。换句话说, 我们知道真实的情况是以下m+n种布局之一:

1. 1号是坏球,且较重;

2. 2号是坏球,且较重;

??

m. m号是坏球,且较重;

m+1. m+1号是坏球,且较轻;

m+2. m+2号是坏球,且较轻;

??

m+n. m+n号是坏球,且较轻。

有一种特殊的情况是m=0或n=0,也就是说坏球的是轻还是重已经知,常 常被用来单独作为智力题。

结论1:

1)在以上条件成立的情况下,要保证在m+n个球中找出坏球并知道 其轻重,至少需要称{log3(m+n)}次。

2)如果m和n不同时为1,那么称{log3(m+n)}次就足够了。如果 m=n=1,并且另有一标准球,那么称{log3(m+n)}={log3(1+1)}=1 次也足够了。

这里log3表示以3为底的对数。

需要对2)作点说明。如果m=n=1而没有标准球的话,那么是永远也 称不出坏球来的。把两个球一边一个放在天平上,必然是1号重2号轻。 但是由于没有标准球,我们无法知道是坏球比较重所以1号是坏的,还 是坏球比较轻所以2号是坏的。如果有标准球,只要把1号球和标准球 比较一下。如果天平不平衡,那么1号球是坏球,且比较重;如果天平 平衡,那么2号球是坏球,且比较轻。策略树如下:(用s表示标准球)

|--右--( )

|

|

(1; s)|--平--(2轻)

|

|

|--左--(1重)

现在来证明1)。在上面我们看到,可能的布局是m+n种(1重,2重, ??,m重,m+1轻,m+2轻,??,m+n轻)。假设我们已经有一个策 略能保证在这m+n个球中找出坏球并知道其轻重,那么每一个布局都要 通向策略树上的不同叶子,这棵策略树至少需要有m+n片叶子。但是一 棵高度为H的三分树最多只能有3H片叶子。于是这棵策略树必须满足条 件

3H ≥ m+n

也就是

H ≥ log3(m+n)

考虑到H是整数,我们就证明了

H ≥ {log3(m+n)}

现在我们要具体找到一棵高度为{log3(m+n)}的策略树,使得m+n 种布局通向它的不同叶子。我们对k=m+n使用数学归纳法。

首先k=1。那么称都不要称,因为必有一坏球,那么坏球就是唯一 的1号球。如果是m=1,n=0,那么1号球比较重;如果是m=0,n=1,那 么1号球比较轻。需要的称量次数为{log3(1)}=0。

对于k=2。m=1,n=1的情况已经讨论过了。考虑m=2,n=0。这时我 们知道坏球比较重。只要把1号球和2号球放在天平两边一称,哪个比较 重哪个就是坏球。策略树如下:

|--右--(2重)

|

|

(1; 2)|--平--( )

|

|

|--左--(1重)

m=0,n=2的情况完全类似。

假设对于m+n<k的情况我们都可以用{log3(k)}次称出坏球。考虑

m+n=k的情况。我们把1到m号球称为第一组球,m+1到n号球称为第二组 球。

设H={log3(m+n)}={log3(k)}。那么我们有

3H-1 < k ≤ 3H

3H-2 < k/3 ≤ 3H-1

3H-2 < {k/3} ≤ 3H-1

于是

{log3{k/3}}=H-1。

现在我们把这k个球分为三堆,第一堆和第二堆分别有{k/3}个球, 并且这两堆中属于第一组的球的数目一样(于是属于第二组的球的数 目也一样),第三堆中有k-2{k/3}个球(也就是其余的球)。举一个 例子,如果m=7,n=3,那么这三堆可以分成这样:(当然不是唯一的 分法)

第一堆:1,2,3,7 (属于第一组的3个,第二组的1个) 第二堆:4,5,6,8 (属于第一组的3个,第二组的1个) 第三堆:9,10

这样的分堆总是可能的吗?如果m或n是偶数,那就很简单。比如 说假设m是偶数,有两种可能性。如果m/2≥{k/3},那么就从第一组球 中各取{k/3}个球作为第一和第二堆(这时在第一第二堆中只有第一组 的球);如果m/2<{k/3},那么就把第一组球分为相同的m/2个球的两 堆,再分别用{k/3}-m/2个第二组球去把它们补充成{k/3}个球的两堆 (这时在第三堆中就只有第二组的球了)。很显然这样的分堆符合上 面的要求。

如果m和n都是奇数,事情就有点复杂。首先如果(m-1)/2≥{k/3} 的话,那么按上面的方法也很容易把球按要求分为三堆。但是如果

(m-1)/2<{k/3},我们就必须先从第一组中各拿出(m-1)/2个球放入第 一和第二堆,再从第二组中各拿出{k/3}-(m-1)/2个球将它们补充到各 有{k/3}个球为止。这就需要从第二组中总共拿得出2({k/3}-(m-1)/2) 个球来。所以必须有

2({k/3}-(m-1)/2) ≤ n

2{k/3} ≤ (m-1)+n

2{k/3} ≤ k-1

这个不等式在k=3或k>4时总是成立的,但是对k=4就不成立。所以我 们要对k=4且m,n都是奇数的情况作特殊处理。我们只需考虑m=3,n=1 这种情况。把1号球和2号球放在天平两端,如果不平衡,那么较重的 那个是坏球;如果平衡,那么把1号球和3号球放在天平两端,平衡则 4号球为坏球且较轻,不平衡则3号球为坏球且较重。策略树如下:

|--右--(2重)

|

| |--右--(3重)

(1; 2)|--平--(1; 3)|--平--(4轻)

| |--左--( )

|

|--左--(1重)

m=1,n=3的情况完全类似。

于是现在我们就可以毫无障碍地假设,我们已经将m+n=k个球分为 这样的三堆:第一堆和第二堆分别有{k/3}个球,并且这两堆中属于第 一组的球的数目一样(于是属于第二组的球的数目也一样),第三堆 中有k-2{k/3}个球(也就是其余的球)。

我们把第一堆球和第二堆球分别放在天平的左右两端。如果平衡, 那就说明坏球在第三堆里,这样我们就把问题归结为一个k-2{k/3}个 球的问题;如果右边比较重,那么我们得到结论:要么是坏球比较轻, 并且它在第一堆中的第二组球,也就是可能较轻的那些球中,要么是 坏球比较重,并且它在第二堆中的第一组球,也就是可能较重的那些 球中,下面它就归结为一个{k/3}个球的问题了;如果是左边比较重, 那么我们也完全类似地将问题归结为一个{k/3}个球的问题。开始的策 略树如下:(小球的编号作了适当变化:假设1,2,??,s为第一堆 中的第一组球,1',2'??,s'为第二堆中的第一组球,(s+1),?? 为第一堆中的第二组球,(s+1)'为为第二堆中的第二组球)

归结为坏球在

|--右--(1',2',??,s',s+1,??)中

| 的问题({k/3}个球)

|

|

(1,2,……,s,s+1,……; |

1',2',??,s',(s+1)',??)|--平--归结为坏球在第三堆中的问题

| (k-2{k/3}个球)

|

| 归结为坏球在

|--左--(1,2,??,s,(s+1)',??)中

的问题({k/3}个球)

考虑到k-2{k/3}≤{k/3},另外此次称量后我们至少可以得到一个标准 球(如果不平衡,第三堆里的球均为标准球,否则第一第二堆里的球 均为标准球)。根据归纳假设,上面得到“左”、“平”、“右”三 种情况归结后的问题都可以用{log3{k/3}}=H-1次的称法来解决。所 以加上这第一次称量,k个球只需{log3(k)}次称量就可以找出坏球。

在这节的最后我们给出一个具体的例子:如果有27个球,其中有 一个坏球,而且已知第一堆1-14号球如果其中一个是坏球,那么它比 标准球重,第二堆15-27号球如果其中一个是坏球,那么它比标准球轻。 根据结果1,我们知道只要[log3(27)]=3次就可以找出坏球。

按照上面的称法,首先将27个球分为三堆,第一第二堆的个数为 {27/3}=9个球,而且其中分别属于第一和第二组的球的个数相同。于 是我们可以取:

第一堆: 1-7,15-16

第二堆:8-14,17-18

第三堆:19-27

现在把第一和第二堆放在天平左右两端,如果平衡,我们就归结为在 19-27号9个球中其中有个较轻坏球的问题;如果右边重,我们就归结 为坏球在8-14,15-16中的问题;如果左边重,我们就归结为坏球在 1-7,17-18中的问题。这三种情况都是9个球的问题。

|--右--归结为坏球在8-14,15-16中的问题

|

|

(1-7,15-16; |

8-14,17-18|--平--归结为坏球在19-27中的问题

|

|

|

|--左--归结为坏球在1-7,17-18中的问题

三种情况中我们只具体做一种:坏球在1-7,17-18中的问题。同 样地我们将其分为三堆

第一堆:1-3

第二堆:4-6

第三堆:7,17-18

照上面类似地我们有策略树

|--右--归结为坏球在4-6中的问题

|

|

(1-3; 4-6)|--平--归结为坏球在7,17-18中的问题

|

|

|--左--归结为坏球在1-3中的问题

于是变成了3个球的问题,解决方法就很显然了,我们把上面的策略树 写完整:

|--右--( 5重)

|--右--(4 ; 5)|--平--( 6重)

| |--左--( 4重)

|

| |--右--(17轻)

(1-3; 4-6)|--平--(17;18)|--平--( 7重)

| |--左--(18轻)

|

| |--右--( 2重)

|--左--(1 ; 2)|--平--( 3重)

|--左--( 1重)

类似地我们写出坏球在8-14,15-16中的问题的策略树:

|--右--(12重)

|--右--(11;12)|--平--(13重)

| |--左--(11重)

|

| |--右--(15轻)

(8-10;11-13)|--平--(15;16)|--平--(14重)

| |--左--(16轻)

|

| |--右--( 9重)

|--左--(8 ; 9)|--平--(10重)

|--左--( 8重)

和坏球在19-27中的问题的策略树:

|--右--(19轻)

|--右--(19;20)|--平--(21轻)

| |--左--(20轻)

|

| |--右--(25轻)

(19-21;22-24)|--平--(25;26)|--平--(27轻)

| |--左--(26轻)

|

| |--右--(22轻)

|--左--(22;23)|--平--(24轻)

|--左--(23轻)

于是最终将此三棵策略树拼起来的到最终解法:

|--右--(12重)

|--右--(11;12)|--平--(13重)

| |--左--(11重)

|

| |--右--(15轻)

|--右--(8-10; |--平--(15;16)|--平--(14重)

| 11-13)| |--左--(16轻)

| |

| | |--右--( 9重)

| |--左--(8 ; 9)|--平--(10重)

| |--左--( 8重)

|

| |--右--(19轻)

| |--右--(19;20)|--平--(21轻)

| | |--左--(20轻)

| |

| | |--右--(25轻)

(1-7,15-16; |--平--(19-21;|--平--(25;26)|--平--(27轻) 8-14,17-18)| 22-24)| |--左--(26轻)

| |

| | |--右--(22轻)

| |--左--(22;23)|--平--(24轻)

| |--左--(23轻)

|

| |--右--( 5重)

| |--右--(4 ; 5)|--平--( 6重)

| | |--左--( 4重)

| |

| | |--右--(17轻)

|--左--(1-3; |--平--(17;18)|--平--( 7重)

4-6)| |--左--(18轻)

|

| |--右--( 2重)

|--左--(1 ; 2)|--平--( 3重)

|--左--( 1重)

对一棵策略树正确性的验证比较容易(虽然比较烦)。首先检查 是否所有的布局都在某片叶子上了;其次就是检验每个布局经过树中 的每个节点的流向是否正确,就是说用此节点上的称量方法,它所属 的左中右分支符合实际。

四、问题的解答

现在我们就可以来回答第一节中的问题了。

结论2:现有N个小球,其中有一个坏球不知比标准球轻还是重。 我们令H={log3(2N)}。

1)要保证在N个球中找出坏球并知道其轻重,至少需要称H次。

假设N≠2,我们有

2)如果N<(3H-1)/2,那么称H次就足够了;

3)如果N=(3H-1)/2,那么称H次足以保证找到坏球,但不足以保 证知道坏球比标准球轻还是重;

4)如果N=(3H-1)/2,而且还另有一个标准球,那么称H次足以保 证找到坏球和知道,知道坏球比标准球轻还是重。

假设N=2,我们有

5)如果还另有一个标准球,称H={log3(2*2)}=2次足以保证找到 坏球和知道坏球比标准球轻还是重。

5)看起来有点奇怪,不过这其实很显然。如果有超过两个球,我 们知道坏球是“独一无二”的那一个,总找得出来;但是如果只有两 个球,一个好球一个坏球,都是“独一无二”的,如果没有一个标准 球的话,我们无论如何不可能知道哪个才是好的。

首先假设结论成立,我们来看看几个具体例子。如果是12个球, 那么

H = {log3(2*12)} = 3,

而且

12 < (33-1)/2 = 13。

所以根据2)我们知道称3次可以找出坏球并知其轻重。如果是13个球, 那么

H={log3(2*13)}=3,

而且

(33-1)/2=13。

根据3)我们知道称3次可以找出坏球但不一定能知其轻重。但是如果另 有一个标准球的话,称3次就可找出坏球且知其轻重。

一般地,能由H次称量找出坏球并知道其轻重的最大小球数量为 (3H-1)/2-1 = (3H-3)/2;

能由H次称量找出坏球但不需要知道其轻重的最大小球数量为

(3H-1)/2;

有一标准球,能由H次称量找出坏球并知道其轻重的最大小球数量也为 (3H-1)/2。

为了比如说为了找出坏球并知道其轻重,则3次最多可以称12个,4次 为39个,5次为120个,6次为363个等等;为了找出坏球却不需知道其 轻重,则3次最多可以称13个,4次为40个,5次121个,6次364个等等 --但是如果另有一个标准球,那么就可以用相同的次数来知道坏球 的轻重。

首先我们证明至少需要称{log3(2N)}次。这和上节类似问题的证

明几乎相同。我们看到,N个小球可能的布局是2N种(1重,2重,??, N重,1轻,2轻,??,N轻)。所以相应策略树至少需要有2N片叶子。 但是一棵高度为H的三分树最多只能有3H片叶子。于是这棵策略树必 须满足条件

H ≥ {log3(2N)}。

现在我们来证明3)的后半部分:如果N=(3H-1)/2,那么称H次还 是不足以保证知道坏球比标准球轻还是重。

我们知道第一步称量一定是各放n(这里2n≤N)个球在天平两端, 然后看天平的状况再决定后面的步骤。此时有三种情况

1)如果天平平衡,那么坏球就在剩下的N-2n个球里。这时候根据1), 我们还需要{log3(2(N-2n))}次来找到坏球并知其轻重;

2)如果是左边重,则要么是坏球比较轻,而且坏球在右面n个球里, 要么是坏球比较重,而且坏球在左面n个球里。这时根据结论1,我 们还要{log3(2n))}次来找到坏球并知其轻重;

3)如果是右边重,那么有和上面类似的结论,我们还要{log3(2n))}

次来找到坏球并知其轻重。

如果我们在H次里可以称出坏球并知其轻重,那么我们必然要有 {log3(2(N-2n))} ≤ H-1 和 {log3(2n))} ≤ H-1

但前一个式子表明

2(N-2n) ≤ 3H-1

也就是

2((3H-1)/2-2n) ≤ 3H-1

所以

3H-1 ≤ 2n+1/2

考虑到3H-1为整数,于是

3H-1 ≤ 2n

但3H-1又是奇数,而2n是偶数,所以

3H-1 < 2n。 (*)

而后一个式子表明

2n ≤ 3H-1

同样考虑到奇偶性

2n < 3H-1。 (**)

我们看到(*)和(**)式是矛盾的。

所以对N=(3H-1)/2的情况,只用H步是不能够称出坏球又知道它 的轻重的。它的原因在于,虽然理论上N=(3H-1)/2,那么可能的布局 是(3H-1)种,而一棵H层的策略树有3H片叶子,看起来叶子足够多了。 但是由于第一步的称量无论如何也不可能把这3H-1种布局平均地分配 在左中右三棵子策略树上,总有一个分支上承受的布局会超过3H-1种, 于是在此分支上就无法用剩下的H-1次称量来称出坏球又知道它的轻 重。

接下来我们同时证明结论2中的2)、4)和5)。也就是说,我们要具 体找到一种策略,如果N<(3H-1)/2,那么不用标准球在H次内找到坏 球又知道它的轻重的;如果N=(3H-1)/2或者N=2,则允许使用一个标 准球来达到同样目的。仍旧使用数学归纳法。

首先对N=1,{log3(2N)}=1且N=(31-1)/2,允许使用标准球。因 为只有一个球,而题目的条件是有一个坏球,所以这唯一的一个就是 坏球,现在只需要知道它比标准球重还是轻。这只要把标准球和这个 小球在天平上比较一次就可以了,策略树如下(我们用s表示标准球):

|--右--(1轻)

(1; s)|--平--( )

|--左--(1重)

对N=2和N=3,{log3(2N)}=2。我们给出下面高度为2的策略树, 很容易验证其正确性。

N=2,允许使用标准球:

|--右--(1轻)

| |--右--(2轻)

(1; s)|--平--(2; s)|--平--( )

| |--左--(2重)

|--左--(1重)

N=3:

|--右--(1轻)

|--右--(1; 3)|--平--(2重)

| |--左--( )

|

| |--右--(3轻)

(1; 2)|--平--(1; 3)|--平--( )

| |--左--(3重)

|

| |--右--( )

|--左--(1; 3)|--平--(2轻)

|--左--(1重)

现在假设对小于N的情况,称法都已经找到。考虑N(现在假定N>3) 个小球的情况。仍记H={log3(2N)}。

首先如果N<(3H-1)/2,我们把N个球分成三堆:第一堆和第二堆 中分别有{N/3}个球,第三堆中为剩下的球,有N-2{N/3}个。我们把第 一和第二堆小球放在天平左右端进行第一次称量。

三种情况:

如果天平平衡,那么坏球在第三堆的N-2{N/3}个里,问题归结为 N-2{N/3}个小球,称H-1次,而且此时我们可以随便从第一或第二堆里 拿出一个球来作标准球。但是

N-2{N/3} ≤ 3{N/3}-2{N/3} = {N/3}

但由N<(3H-1)/2有

N ≤ (3H-1)/2-1 = (3H-3)/2

所以

N/3 ≤ (3H-1-1)/2

右边一定是一个整数,所以我们最终得到

N-2{N/3} ≤ {N/3} ≤ (3H-1-1)/2。

根据归纳假设,在有标准球的情况下,N-2{N/3}个球的问题可被H-1次 的称量解决。

如果左边重,则要么是坏球比较轻,而且坏球在右面{N/3}个球里; 要么是坏球比较重,而且坏球在左面{N/3}个球里。这时根据结论1,我 们还要{log3(2{N/3}))}次来找到坏球并知其轻重。和上面的计算完全 一样,

N/3 ≤ (3H-1-1)/2

于是

2{N/3} ≤ 3H-1-1

{log3(2{N/3}))} ≤ H-1

所以仍旧可以用剩下的H-1次称量解决问题。

如果右边重,完全类似于左边重的情况。

现在考虑N=(3H-1)/2的情况,这时允许用一个标准球。我们可以 把球分成三堆。第一堆为(3H-1+1)/2个,第二堆为(3H-1-1)/2个 再加上标准球,所以第二堆一共也是(3H-1+1)/2个球,第三堆是剩 下的

(3H-1)/2-(3H-1+1)/2-(3H-1-1)/2 = (3H-1-1)/2

个球。我们把第一和第二堆小球放在天平左右端进行第一次称量。

三种情况:

如果天平平衡,那么坏球在第三堆的(3H-1-1)/2个里。根据归 纳假设,在有标准球的情况下,这可被H-1次称量解决。

如果左边重,则要么是坏球比较轻,而且坏球在右面(3H-1+1)/2 个球里;要么是坏球比较重,而且坏球在左面除了附加的标准球以外 的(3H-1-1)/2个球里。这时根据结论1,我们还要

{log3(3H-1+1)/2+(3H-1-1)/2)} = H-1

次来找到坏球并知其轻重。所以这也可以用剩下的H-1次称量来解决问 题。

如果右边重,完全类似于左边重的情况。

这就完全证明了结论2中的2)、4)和5)。剩下的就是3)的前半部分: 如果N=(3H-1)/2,那么称H次足以保证找到坏球(但可能不知道轻重)。

这很简单,如果我们拿掉一个球,那么根据2),一定能用H次称量 来找到坏球并且知道轻重--唯一的例外是,如果被拿掉的那个恰好 就是坏球--那么这时候所有称量的结果都是天平保持平衡。如果发 生了这样的事,所有称量的结果都是天平保持平衡,我们就可以断定 坏球就是那个被拿掉的球,当然这时这个球从来没有上过天平,我们 绝无可能知道它是比标准球重,还是比标准球轻。

五、四十个球的例子

最后我们来解决一下40个球,没有标准球的问题。我们知道 40 = (34-1)/2

所以我们可以称4次找出坏球,但是因为没有标准球,就不一定能知道 坏球的轻重。

顺便先考虑13个球,另有一标准球的问题。

13 = (33-1)/2

所以称3次可以找出坏球,因为有标准球,我们还可以同时知道坏球的 轻重。

根据上一节的证明过程,这时我们要把这13个球分为3堆: 第一堆:1-5

第二堆:6-9,再加上标准球s

第三堆:10-13

我们把第一和第二堆小球放在天平左右端进行第一次称量。

如果是左边重,那么要么是第一堆1-5号球中有一个是坏球,而且 它比标准球重,要么是第二堆6-9号球中有一个是坏球,那么它比标准 球轻。用结论1来解决的问题,第三节末尾我们处理过27个球的问题, 9个球的问题就是小菜了:

|--右--( 4重)

|--右--(3 ; 4)|--平--( 6轻)

| |--左--( 3重)

|

| |--右--( 8轻)

(1-2,6;3-4,7)|--平--(8 ; 9)|--平--( 5重)

| |--左--( 9轻)

|

| |--右--( 2重)

|--左--(1 ; 2)|--平--( 7轻)

|--左--( 1重)

如果是右边重,那么和上面的情况对称,只要把策略树中的“左” 和“右”互换,“轻”和“重”互换即可。

如果平衡,那么就化为4个球(10-13号)有一个标准球2次称出的 问题。虽然还可以往下照葫芦画瓢地递归一次,不过4个球的情况就太 简单了,所以直接写出策略树:

|--右--(10轻)

|--右--(10;11)|--平--(12重)

| |--左--(11轻)

|

| |--右--(13轻)

(10,11;12,s)|--平--(13; s)|--平--( )

| |--左--(13重)

|

| |--右--(11重)

|--左--(10;11)|--平--(12轻)

|--左--(10重)

把左中右三个分支拼起来我们就得到13个球有一标准球称3次的策 略树:

|--右--( 1轻)

|--右--(1 ; 2)|--平--( 7重)

| |--左--( 2轻)

|

| |--右--( 9重)

|--右--(1-2,6;|--平--(8 ; 9)|--平--( 5轻)

| 3-4,7)| |--左--( 8重)

| |

| | |--右--( 3轻)

| |--左--(3 ; 4)|--平--( 6重)

| |--左--( 4轻)

|

| |--右--(10轻)

| |--右--(10;11)|--平--(12重)

| | |--左--(11轻)

| |

| | |--右--(13轻)

(1-5; |--平--(10,11;|--平--(13; s)|--平--( )

6-9,s)| 12,s)| |--左--(13重)

| |

| | |--右--(11重)

| |--左--(10;11)|--平--(12轻)

| |--左--(10重)

|

| |--右--( 4重)

| |--右--(3 ; 4)|--平--( 6轻)

| | |--左--( 3重)

| |

| | |--右--( 8轻)

|--左--(1-2,6;|--平--(8 ; 9)|--平--( 5重)

3-4,7)| |--左--( 9轻)

|

| |--右--( 2重)

|--左--(1 ; 2)|--平--( 7轻)

|--左--( 1重)

现在可以考虑40个球,无标准球的问题了。根据上一节的证明过 程,我们首先拿掉第40号球,使之变为39个球的问题。然后我们把这 39个球分为3堆:

第一堆:1-13

第二堆:14-26

第三堆:27-39

把第一和第二堆小球放在天平左右端进行第一次称量。

如果是右边重,那么要么是第一堆1-14号球中有一个是坏球,而 且它比标准球重,要么是第二堆15-27号球中有一个是坏球,那么它比 标准球轻。这恰好是第三节末尾我们解决过的例子!这个策略树分支 我们可以完全拷贝过来。

如果是左边重,那么和上面的情况对称,只要把策略树中的“左” 和“右”互换,“轻”和“重”互换即可。

如果平衡,那么问题转化为本节开始的13个球,有一标准球的问 题(可取1号球为标准球),上面的策略树也可拷贝过来,只是要把原 来的1-13号球和这里的27-39号球一一对应(只要把所有的号码加26即 可)。

把左中右三个策略分支合并起来,并考虑到如果所有称量结果都 是平衡的话,则第40号球为坏球的结论。我们就得到了下面的关于称 40个球的巨无霸策略树,它有81片叶子:

|--右--( 1轻)

|--右--(1 ; 2)|--平--( 3轻)

| |--左--( 2轻)

|

| |--右--(18重)

|--右--(1-3; |--平--(17;18)|--平--( 7轻)

| 4-6)| |--左--(17重)

| |

| | |--右--( 4轻)

| |--左--(4 ; 5)|--平--( 6轻)

| |--左--( 5轻)

|

| |--右--(23重)

| |--右--(22;23)|--平--(24重)

| | |--左--(22重)

| |

| | |--右--(26重)

|--右--(1-7, |--平--(19-21;|--平--(25;26)|--平--(27重)

| 15-16;| 22-24)| |--左--(25重)

| 8-14,| |

| 17-18)| | |--右--(20重)

| | |--左--(19;20)|--平--(21重)

| | |--左--(19重)

| |

| | |--右--( 8轻)

| | |--右--(8 ; 9)|--平--(10轻)

| | | |--左--( 9轻)

| | |

| | | |--右--(16重)

| |--左--(8-10; |--平--(15;16)|--平--(14轻)

| 11-13)| |--左--(15重)

| |

| | |--右--(11轻)

| |--左--(11;12)|--平--(13轻)

| |--左--(12轻)

|

| |--右--(27轻)

| |--右--(27;28)|--平--(33重)

| | |--左--(28轻)

| |

| | |--右--(35重)

| |--右--(27-28,|--平--(34;35)|--平--(31轻)

| | 32;| |--左--(34重)

| | 29-30,|

| | 33)| |--右--(29轻)

| | |--左--(29;30)|--平--(32重)

| | |--左--(30轻)

| |

| | |--右--(36轻)

| | |--右--(36;37)|--平--(38重)

| | | |--左--(37轻)

| | |

| | | |--右--(39轻)

(1-13;|--平--(27-31;|--平--(36,37;|--平--(39; 1)|--平--(40坏) 14-26)| 32-35,1)| 38,1)| |--左--(39重)

| | |

| | | |--右--(37重)

| | |--左--(36;37)|--平--(38轻)

| | |--左--(36重)

| |

| | |--右--(30重)

| | |--右--(29;30)|--平--(32轻)

| | | |--左--(29重)

| | |

| | | |--右--(34轻)

| |--左--(27-28,|--平--(34;35)|--平--(31重) | 32;| |--左--(35轻)

| 29-30,|

| 33)| |--右--(28重)

| |--左--(27;28)|--平--(33轻)

| |--左--(27重)

|

| |--右--(12重)

| |--右--(11;12)|--平--(13重)

| | |--左--(11重)

| |

| | |--右--(15轻)

| |--右--(8-10; |--平--(15;16)|--平--(14重) | | 11-13)| |--左--(16轻)

| | |

| | | |--右--( 9重)

| | |--左--(8 ; 9)|--平--(10重)

| | |--左--( 8重)

| |

| | |--右--(19轻)

| | |--右--(19;20)|--平--(21轻)

| | | |--左--(20轻)

| | |

| | | |--右--(25轻)

|--左--(1-7, |--平--(19-21;|--平--(25;26)|--平--(27轻) 15-16;| 22-24)| |--左--(26轻)

8-14, | |

17-18)| | |--右--(22轻)

| |--左--(22;23)|--平--(24轻)

| |--左--(23轻)

|

| |--右--( 5重)

| |--右--(4 ; 5)|--平--( 6重)

| | |--左--( 4重)

| |

| | |--右--(17轻)

|--左--(1-3; |--平--(17;18)|--平--( 7重)

4-6)| |--左--(18轻)

|

| |--右--( 2重)

|--左--(1 ; 2)|--平--( 3重)

|--左--( 1重)

补:如果我们不需要找出那个坏球,只想知道坏球是比标准球轻还是重, 怎样用最少的称法来解决这个问题?

让我们来严格表述这个问题:

“有N(N≥1)个外表相同的球,其中有一个坏球,它的重量和标 准球有轻微的(但是可以测量出来的)差别。现在有一架没有砝码的 很灵敏的天平,问最少需要称几次才可以知道坏球比标准球重还是轻?”

就象在普通称球问题的讨论中一样,我们首先来看几个特殊例子。

如果N=1,那么根据题意这个唯一的球就是坏球。可是如果没有 另外的标准球的话,我们怎么也不可能知道这个坏球是比标准球轻还 是重。如果另有一个标准球的话,很显然只需要把它和标准球放在天 平两端称一次,就可以知道这个坏球是比较重还是比较轻。

如果N=2,那么这里有一个好球一个坏球,但是如果没有另外的 标准球的话,我们无论称几次都只能得到一个比较轻一个比较重的结 果,还是不可能知道坏球比标准球轻还是重。如果另有一个标准球的 话,我们必须把标准球分别和两个球比较,如果运气比较好的话,第 一次就和坏球比较,那么称一次就解决问题,否则要称两次。所以一 般的解答就是N=2时,另有一标准球,上面的问题需要称两次才能解 决。

如果N=3或者更多,很显然即便另有一标准球的话,我们也不可 能称一次就解决问题--如果在天平上和标准球同一边有另外的未知 好坏的球,那么这一边就不能作为标准重量了,此时天平偏向一边只 能给出某一边比较重的信息,却不能告诉我们到底哪一边才是标准重 量。

但是当N=3时,即使不用标准球,我们也可以称两次来知道坏球 比较重还是比较轻。将球编为1-3号。首先1,2号球放在天平两端,如 果平衡的话,那么3号是坏球,接下来只要用标准的1号球来和它比较 就知道它是比较轻还是比较重;如果不平衡,比如1号球较重,那么3 号球是标准的,比较1号和3号球:如果它们一样重,那么2号球是坏 球,而且它比较轻,相反如果1号球比3号球重,那么坏球1号球就比 较重。

当N≥4时我们会有什么结论呢?也许会出乎大部分人的意料-- 无论多少个球,比如说一亿个球,如果只需要知道坏球是比较轻还是

比较重,我们总是只需要称2次。

当N≥4时,我们总可以把N写成N=4k+i的形式,其中0≤i≤3,而 k≥1。我们把这堆球分成5堆:前4堆(分别编号为第1、2、3、4堆) 分别有k个球,最后一堆(编号为第5堆)是剩下的i个球。

首先将第1、2堆放在天平左端,第3、4堆放在天平右端进行称量, 如果平衡的话,说明所有这四堆中的球都是好球。因为k≥1,已经确 定的好球数目一定至少有四个,所以接下来只要从中拿出i个和第5堆 比较一下,就可以知道坏球是比较重还是比较轻了。

如果第1、2堆和第3、4堆的称量中天平不平衡,比如说第1、2堆 这端比较重,那么我们将第1、2堆分别放在天平两端进行第二次称量。 如果天平不平衡,那么说明坏球就在第1、2堆内。我们还记得在第一 次称量中,第1、2堆是比较重的,所以坏球比较重。如果第二次称量 天平平衡,那么坏球就在第3、4堆内。根据和上面相同的推理,坏球 比较轻。

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com