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

《称球问题——经典智力题推而广之三（三）》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、称球问题——经典智力题推而广之三（三）三、每个球都已知可能为轻或可能为重的情况　　　　　　　　先引入一个记号：对于任意实数a，我们用{a}表示大于等于a的最小整数，比如说{}=3，{4}=4；我们用[a]表示小于等于a的最大整数，比如说[]=2，[4]=4。　　　　我们首先考虑这样一种布局的集合。假设m，n为两个非负实数，不同时为0。在编号从1到m+n的m+n个球中，我们知道1到m号球要么是标准球，要么比标准球重，而m+1到m+n号球要么是标准球，要么比标准球轻；我们还知道其中有一个是坏球。换句话说，我们知道真实的情况是以下m+n种布局之一：　　1.1号是坏球，且较重；　　2.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、3为底的对数。　　　　　　需要对2)作点说明。如果m=n=1而没有标准球的话，那么是永远也称不出坏球来的。把两个球一边一个放在天平上，必然是1号重2号轻。　　但是由于没有标准球，我们无法知道是坏球比较重所以1号是坏的，还是坏球比较轻所以2号是坏的。如果有标准球，只要把1号球和标准球比较一下。如果天平不平衡，那么1号球是坏球，且比较重；如果天平平衡，那么2号球是坏球，且比较轻。策略树如下：　　　　　　

4、--右--()　　　　

5、　　

6、　　(1;s)

7、--平--(2轻)　　

8、　　

9、　　

10、--左--(1重)　　　　　现在来证明1)。在上面我们看到，可能的布局是m+n种。假设我们已经有一个策略能保证

11、在这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号球比较轻。

12、需要的称量次数为{log3(1)}=0。　　　　对于k=2。m=1，n=1的情况已经讨论过了。考虑m=2，n=0。这时我们知道坏球比较重。只要把1号球和2号球放在天平两边一称，哪个比较重哪个就是坏球。策略树如下：　　　　　　

13、--右--(2重)　　　　

14、　　

15、　　(1;2)

16、--平--()　　

17、　　

18、　　

19、--左--(1重)　　　　　　m=0，n=2的情况完全类似。　　　　　　假设对于m+n＜k的情况我们都可以用{log3(k)}次称出坏球。考虑m+n=k的情况。我们把1到m号球称为第一组球，m+1到n号球称为第二组球。　　　　设H={log3(m+n)}＝{log3(k)}。那么我们有　

20、　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　　　第二堆：4，5，6，8　　　第三堆：9，10　　　　这样的分堆总是可能的吗？如果m或n是偶数，那就很简单。比如说假设m是偶数，有两种可能性。如果m/2≥{k/3}，那么就从第一组球中各取{k/3}个球作为第一和第二堆；如果m/2＜{k/3

21、}，那么就把第一组球分为相同的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