看你能不能给出答案

爱陈雅

有13 个球，其中一个是不同于其他12 个，这个球或者太重或者太轻。怎样用一个平衡称，称三次把这个球找出来并且知道它是太轻或者太重。

www.ddhw.com

 

husonghu

小宝贝,这题是经典,可这儿的都是高手,让我来将这题加点难度吧.求解...www.ddhw.com 上贴时间: 2005-8-17 8:12:34 文章来源: 寒潭清® （积分: 465 现金财富: 55元 详细信息） [ 脑筋一动 首页 ] [ 回复此贴 ] [ 加新贴 ] [ 回 顶顶华闻 主页 ]www.ddhw.com 先热个身,做完这题,再做下题吧www.ddhw.com 13个球，有一个异重（但不知是过轻还是过重），称三次，找出此球。www.ddhw.com 换个难的。(解此题需要很大的耐心和毅力哦)www.ddhw.com 1） 22个球中有两个重球，用无砝码天平称5次，找出这两个球。www.ddhw.com 2） 22个球和11个球中各有一个重球，用无砝码天平称5次，找出这两个球。www.ddhw.com

爱陈雅

小心肝（高手）能不能先帮我解出13个球来，我头快想破了，在下先谢过了。 www.ddhw.com

husonghu

我保证，一天之内你会得到答案。 我现在没时间，要不然我会给你找出来。对不起.www.ddhw.com

寒潭清

说明 　　这篇文章试图给出称球问题的一个一般 的和严格的解答。正因为需要做到一般和严 格，就要考虑许多平时遇不到的特别情形， 所以叙述比较繁琐。如果对读者对严格的证 明没有兴趣，可以只阅读介绍问题和约定记 号的第一、第二节，以及第三节末尾27个球 的例子，和第五节13个球的解法。 事实上所有的技巧都已经表现在这几个例子 里了。www.ddhw.com 　一、问题 　　称球问题的经典形式是这样的： 　　“有十二个外表相同的球，其中有一个坏球，它的重量和其它十 一个有轻微的（但是可以测量出来的）差别。现在有一架没有砝码的 很灵敏的天平，问如何称三次就保证找出那个坏球，并知道它比标准 球重还是轻。” 这可能是网上被做过次数最多的一道智力题了。它的一种解法如 下： 将十二个球编号为1-12。www.ddhw.com 第一次，先将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号是坏球且比标准球重；www.ddhw.com      够麻烦的吧。其实里面有许多情况是对称的，比如第一次称时的 右重和右轻，只需考虑一种就可以了，另一种完全可以比照执行。我 把整个过程写下来，只是想吓唬吓唬大家。 　　稍微试一下，就可以知道只称两次是不可能保证找到坏球的。如 果给的是十三个球，以上的解法也基本有效，只是要有个小小的改动， 就是在这种情况下，在第一第二次都平衡的时候，第三次还是有可能 平衡（就是上面的第2.2.2步），那么我们可以肯定坏球是13号球，可 是我们没法知道它到底是比标准球轻，还是比标准球重。如果给的是 十四个球，我们会发现无论如何也不可能只称三次，就保证找出坏球。 　　一个自然而然的问题就是：对于给定的自然数N，我们怎么来解有 N个球的称球问题？www.ddhw.com 　　在下面的讨论中，给定任一自然数N，我们要解决以下问题： ⑴找出N球称球问题所需的最小次数，并证明以上所给的最小次数的确 　是最小的； ⑵给出最小次数称球的具体方法； ⑶如果只要求找出坏球而不要求知道坏球的轻重，对N球称球问题解决 　以上两个问题； ⑷如果除了所给的N个球外，另外还给一标准球，解决以上三个问题。 二、记号 　　我们先不忙着马上着手解决上述问题。先得给出几个定义，尤其 是，要给出比较简单的符号和记法。大家看到上面给出的解法写起来 实在麻烦——想象一下如果我们要用这种方法来描述称40个或1000个 球的问题！www.ddhw.com 　　仍旧考虑十二个球的情况和上面举的解法。在还没有开始称第一 次时，我们对这十二个球所知的信息就是其中有一或较轻，或较重的 坏球，所以以下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种可能 的布局。我们的目的，就是要使用尽量少的称量，而获得唯一一种可 能的布局——这样我们就知道哪个球是坏球，它是比较重还是比较轻。www.ddhw.com 　　这里我们注意到没有必要去考虑两边球数不相等的称量。因为坏 球和标准球重量之间的差别很小，小于标准球的重量，所以当天平两 边球数不一样时，天平一定向球比较多的那边倾斜。所以在进行这样 一次称量之前，它的的结果就可以被预料到，它不能给我们带来任何 新的信息。事实上在看完本文以后大家就很容易明白，即使坏球和标 准球重量之间的差别很大，也不会影响本文的结论。因为考虑这种情 况会使问题变麻烦，而并不能带来有趣的结果，我们就省略对此的考 虑。 现在我们看到，上面关于十二个球问题的解法，其实就是由一系 列称量组成的——可不是随随便便的组合，而是以这样的形式构成的： 　　称量1 　　　　如果右重，则 　　　　　　称量3 　　　　　　　　…… 　　　　如果平衡，则 　　　　　　称量2 　　　　　　　　…… 　　　　如果左重，则 　　　　　　称量4 　　　　　　　　…… 省略号部分则又是差不多的“如果右重，则……”等等。所以这就提 示我们用树的形式来表示上面的解法：树的根是第一次称量，它有三 个分支（即三棵子树，于是根有三个子节点），分别对应着在这个称 量下的右重、平衡、左重三种情况。在根的三个子节点上，又分别有 相应的称量，和它们的三个分支……如果具体地写出来，就是www.ddhw.com                                        |--右--( 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号球放在左右两侧来称（在叶子上我们没有写出 相应的布局，用@来代替）：www.ddhw.com                    |--右--@A       |--右--(1; 2)|--平--@       |            |--左--@       |       |            |--右--@ (1; 2)|--平--(1; 2)|--平--@       |            |--左--@       |       |                         |--右--@B       |            |--右--(1; 2)|--平--@       |            |            |--左--@       |            |       |            |            |--右--@       |--左--(1; 2)|--平--(1; 2)|--平--@                    |            |--左--@                    |                    |            |--右--@                    |--左--(1; 2)|--平--@                                 |--左--@www.ddhw.com 当然这么个策略没什么用场，只能让我们知道1号球和2号球之间的轻 重关系。另外我们看到，每个分支不一定一样长，上面这棵策略树根 下面左分支就比较长。 　　一棵树的高度是叶子到根之间的结点数的最大值加一。比如说上 面这个图中，叶子A和根间有1个节点，而叶子B和根间有2个节点，没 有和根之间的节点数超过2的叶子。所以它的高度是2+1=3。前面十二 球解法策略树的高度也是3。一棵没有任何分支，只有根节点的树，我 们定义它的高度是0。 　　显然，策略树的高度就是实行这个策略所需要的称量的次数。我 们的目的，就是找到一棵“好”的策略树，使得它的高度最小。www.ddhw.com 　　什么是“好”策略？我们回过头来再看十二球解法策略树。我们 说过，叶子上的那些布局都是从根开始通向叶子的。比如说布局(7重)， 它之所以在那片叶子上是因为按照这个策略，三次称量的结果是“右 左右”；又比如说布局(11重)，它之所以在那片叶子上是因为按照这 个策略，三次称量的结果是“平右平”。如果两个布局通向同一片叶 子，那么就是说按照这个策略，三次称量的结果是完全一样的，于是 我们就不能通过这个策略来把这两种布局区分开来。比如说在十三个 球的情况下，(13轻)和(13重)都通向和“平平平”相对应的叶子，这 两个布局中13号球或者轻或者重，于是我们知道13号球一定是坏球， 但是通过这个策略我们不可能知道它到底是轻还是重。 　　所以对于标准的称球问题（找出坏球并知其比标准球重或轻）的 “好”策略，就是那些能使不同的布局通向不同的叶子的策略。 三、每个球都已知可能为轻或可能为重的情况 　　先引入一个记号：对于任意实数a，我们用{a}表示大于等于a的最 小整数，比如说{2.5}=3，{4}=4；我们用[a]表示小于等于a的最大整 数，比如说[2.5]=2，[4]=4。www.ddhw.com 　　我们首先考虑这样一种布局的集合。假设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为底的对数。www.ddhw.com 　　需要对2)作点说明。如果m=n=1而没有标准球的话，那么是永远也 称不出坏球来的。把两个球一边一个放在天平上，必然是1号重2号轻。 但是由于没有标准球，我们无法知道是坏球比较重所以1号是坏的，还 是坏球比较轻所以2号是坏的。如果有标准球，只要把1号球和标准球 比较一下。如果天平不平衡，那么1号球是坏球，且比较重；如果天平 平衡，那么2号球是坏球，且比较轻。策略树如下：（用s表示标准球）       |--右--       |       | (1; s)|--平--(2轻)       |       |       |--左--(1重)www.ddhw.com 　  现在来证明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。www.ddhw.com 　　对于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号球称为第二组 球。www.ddhw.com 　　设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，10www.ddhw.com 　　这样的分堆总是可能的吗？如果m或n是偶数，那就很简单。比如 说假设m是偶数，有两种可能性。如果m/2≥{k/3}，那么就从第一组球 中各取{k/3}个球作为第一和第二堆（这时在第一第二堆中只有第一组 的球）；如果m/2＜{k/3}，那么就把第一组球分为相同的m/2个球的两 堆，再分别用{k/3}-m/2个第二组球去把它们补充成{k/3}个球的两堆 （这时在第三堆中就只有第二组的球了）。很显然这样的分堆符合上 面的要求。www.ddhw.com 　　如果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重)www.ddhw.com m=1，n=3的情况完全类似。www.ddhw.com 　　于是现在我们就可以毫无障碍地假设，我们已经将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次就可以找出坏球。www.ddhw.com 　　按照上面的称法，首先将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个球的问题。www.ddhw.com             |--右--归结为坏球在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 照上面类似地我们有策略树www.ddhw.com           |--右--归结为坏球在4-6中的问题           |           | (1-3; 4-6)|--平--归结为坏球在7，17-18中的问题           |           |           |--左--归结为坏球在1-3中的问题 于是变成了3个球的问题，解决方法就很显然了，我们把上面的策略树 写完整：www.ddhw.com                         |--右--( 5重)           |--右--(4 ; 5)|--平--( 6重)           |             |--左--( 4重)           |           |             |--右--(17轻) (1-3; 4-6)|--平--(17;18)|--平--( 7重)           |             |--左--(18轻)           |           |             |--右--( 2重)           |--左--(1 ; 2)|--平--( 3重)                         |--左--( 1重) 类似地我们写出坏球在8-14，15-16中的问题的策略树：www.ddhw.com                           |--右--(12重)             |--右--(11;12)|--平--(13重)             |             |--左--(11重)             |             |             |--右--(15轻) (8-10;11-13)|--平--(15;16)|--平--(14重)             |             |--左--(16轻)             |             |             |--右--( 9重)             |--左--(8 ; 9)|--平--(10重)                           |--左--( 8重) 和坏球在19-27中的问题的策略树：www.ddhw.com                            |--右--(19轻)              |--右--(19;20)|--平--(21轻)              |             |--左--(20轻)              |              |             |--右--(25轻) (19-21;22-24)|--平--(25;26)|--平--(27轻)              |             |--左--(26轻)              |              |             |--右--(22轻)              |--左--(22;23)|--平--(24轻)                            |--左--(23轻) 　　于是最终将此三棵策略树拼起来的到最终解法：www.ddhw.com                                          |--右--(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重) 　　对一棵策略树正确性的验证比较容易（虽然比较烦）。首先检查 是否所有的布局都在某片叶子上了；其次就是检验每个布局经过树中 的每个节点的流向是否正确，就是说用此节点上的称量方法，它所属 的左中右分支符合实际。 四、问题的解答www.ddhw.com 　　现在我们就可以来回答第一节中的问题了。 结论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)看起来有点奇怪，不过这其实很显然。如果有超过两个球，我 们知道坏球是“独一无二”的那一个，总找得出来；但是如果只有两 个球，一个好球一个坏球，都是“独一无二”的，如果没有一个标准 球的话，我们无论如何不可能知道哪个才是好的。www.ddhw.com 　　首先假设结论成立，我们来看看几个具体例子。如果是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次就可找出坏球且知其轻重。www.ddhw.com 　　一般地，能由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次还 是不足以保证知道坏球比标准球轻还是重。www.ddhw.com 　　我们知道第一步称量一定是各放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。    (**) 我们看到(*)和(**)式是矛盾的。www.ddhw.com 　　所以对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表示标准球）：www.ddhw.com       |--右--(1轻) (1; s)|--平--       |--左--(1重) 　　对N=2和N=3，{log3(2N)}=2。我们给出下面高度为2的策略树， 很容易验证其正确性。 N=2，允许使用标准球：www.ddhw.com       |--右--(1轻)       |            |--右--(2轻) (1; s)|--平--(2; s)|--平--       |            |--左--(2重)       |--左--(1重) N=3：www.ddhw.com                    |--右--(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}个。我们把第 一和第二堆小球放在天平左右端进行第一次称量。 　　三种情况：www.ddhw.com 　　如果天平平衡，那么坏球在第三堆的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次称量解决问题。 　　如果右边重，完全类似于左边重的情况。www.ddhw.com 　　现在考虑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次足以保证找到坏球（但可能不知道轻重）。www.ddhw.com 　　这很简单，如果我们拿掉一个球，那么根据2)，一定能用H次称量 来找到坏球并且知道轻重——唯一的例外是，如果被拿掉的那个恰好 就是坏球——那么这时候所有称量的结果都是天平保持平衡。如果发 生了这样的事，所有称量的结果都是天平保持平衡，我们就可以断定 坏球就是那个被拿掉的球，当然这时这个球从来没有上过天平，我们 绝无可能知道它是比标准球重，还是比标准球轻。 五、十三个球的例子 　　考虑13个球，另有一标准球的问题。 　　 13 = (33-1)/2 所以称3次可以找出坏球，因为有标准球，我们还可以同时知道坏球的 轻重。 　　根据上一节的证明过程，这时我们要把这13个球分为3堆： 　　第一堆：1-5 　　第二堆：6-9，再加上标准球s 　　第三堆：10-13 我们把第一和第二堆小球放在天平左右端进行第一次称量。www.ddhw.com 　　如果是左边重，那么要么是第一堆1-5号球中有一个是坏球，而且 它比标准球重，要么是第二堆6-9号球中有一个是坏球，那么它比标准 球轻。用结论1来解决的问题，第三节末尾我们处理过27个球的问题， 9个球的问题就是小菜了：www.ddhw.com                            |--右--( 4重)              |--右--(3 ; 4)|--平--( 6轻)              |             |--左--( 3重)              |              |             |--右--( 8轻) (1-2,6;3-4,7)|--平--(8 ; 9)|--平--( 5重)              |             |--左--( 9轻)              |              |             |--右--( 2重)              |--左--(1 ; 2)|--平--( 7轻)                            |--左--( 1重) 　　如果是右边重，那么和上面的情况对称，只要把策略树中的“左” 和“右”互换，“轻”和“重”互换即可。www.ddhw.com 　　如果平衡，那么就化为4个球（10-13号）有一个标准球2次称出的 问题。虽然还可以往下照葫芦画瓢地递归一次，不过4个球的情况就太 简单了，所以直接写出策略树：www.ddhw.com                           |--右--(10轻)             |--右--(10;11)|--平--(12重)             |             |--左--(11轻)             |             |             |--右--(13轻) (10,11;12,s)|--平--(13; s)|--平--             |             |--左--(13重)             |             |             |--右--(11重)             |--左--(10;11)|--平--(12轻)                           |--左--(10重) www.ddhw.com 　　把左中右三个分支拼起来我们就得到13个球有一标准球称3次的策 略树：www.ddhw.com                                    |--右--( 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重) 让我们来严格表述这个问题： 　　“有N(N≥1)个外表相同的球，其中有一个坏球，它的重量和标 准球有轻微的（但是可以测量出来的）差别。现在有一架没有砝码的 很灵敏的天平，问最少需要称几次才可以知道坏球比标准球重还是轻？” 　　就象在普通称球问题的讨论中一样，我们首先来看几个特殊例子。 　　如果N=1，那么根据题意这个唯一的球就是坏球。可是如果没有 另外的标准球的话，我们怎么也不可能知道这个坏球是比标准球轻还 是重。如果另有一个标准球的话，很显然只需要把它和标准球放在天 平两端称一次，就可以知道这个坏球是比较重还是比较轻。www.ddhw.com 　　如果N=2，那么这里有一个好球一个坏球，但是如果没有另外的 标准球的话，我们无论称几次都只能得到一个比较轻一个比较重的结 果，还是不可能知道坏球比标准球轻还是重。如果另有一个标准球的 话，我们必须把标准球分别和两个球比较，如果运气比较好的话，第 一次就和坏球比较，那么称一次就解决问题，否则要称两次。所以一 般的解答就是N=2时，另有一标准球，上面的问题需要称两次才能解 决。 　　如果N=3或者更多，很显然即便另有一标准球的话，我们也不可 能称一次就解决问题——如果在天平上和标准球同一边有另外的未知 好坏的球，那么这一边就不能作为标准重量了，此时天平偏向一边只 能给出某一边比较重的信息，却不能告诉我们到底哪一边才是标准重 量。 　　但是当N=3时，即使不用标准球，我们也可以称两次来知道坏球 比较重还是比较轻。将球编为1-3号。首先1，2号球放在天平两端，如 果平衡的话，那么3号是坏球，接下来只要用标准的1号球来和它比较 就知道它是比较轻还是比较重；如果不平衡，比如1号球较重，那么3 号球是标准的，比较1号和3号球：如果它们一样重，那么2号球是坏 球，而且它比较轻，相反如果1号球比3号球重，那么坏球1号球就比 较重。www.ddhw.com 　　当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堆内。根据和上面相同的推理，坏球 比较轻。 www.ddhw.com

husonghu

  是晕了。得好好读读，认真想想。

爱陈雅

It took me a while to finish this essay but finally i figured out how to balance the 13 balls. These questions are a little hard for me to solve it myself. Fortunely, i can get the answer or hint from all of your professional math-problem solvers. Thanks.www.ddhw.com

husonghu

  有的是professional，如野菜花。但大多数都不是，象你一样。欢迎多来