Math 版 (精华区)

发信人: llhhxht (绿林好汉), 信区: Math
标  题: 称球问题(第二节)
发信站: 哈工大紫丁香 (Tue Feb 11 12:31:02 2003) , 转信

文章阅读 北大未名站 精华区 

------------------------------------------------------------------------------
--
 发信人: symplectic (sound-of-silence), 信区: Mathematics
标  题: 称球问题(第二节)
发信站: 北大未名站 (2001年09月04日01:33:56 星期二) , 站内信件

《三思科学》电子杂志
第三期，2001年9月1日

http://www.myscience.com.cn/magazine/200109/




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

      　　　　　　　　　 异调


　　　　　　　　　　　　二、记号

　　我们先不忙着马上着手解决上述问题。先得给出几个定义，尤其
是，要给出比较简单的符号和记法。大家看到上面给出的解法写起来
实在麻烦——想象一下如果我们要用这种方法来描述称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号球一定是坏球，
但是通过这个策略我们不可能知道它到底是轻还是重。

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


--

※ 来源:·北大未名站 bbs.pku.edu.cn·[FROM: 130.149.13.23]

 

------------------------------------------------------------------------------
--
分类讨论区 全部讨论区 




--

※ 来源:．哈工大紫丁香 http://bbs.hit.edu.cn [FROM: 218.9.120.96]