称球智力题

上星期天去霸王笔群硕软件，别人开考接近十几分钟也放我们进去了，经典的称球问题再次在试卷上出现，对于算法的推广到n的情况，我没有搞定，这需要深刻的数学思考。看书好像碰到过类似的问题，但都放过了，借着这互联网之功把这道题也记载下来，这些问题很有意思哦，呵呵。

  先讲对于每个球都已知可能为轻或可能为重的情况，再往更复杂推广：

引用

先引入一个记号：对于任意实数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次也足够了。

现在来证明1)。

引用

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

　　3^H ≥ m+n
也就是
　　H ≥ log3(m+n)
考虑到H是整数，我们就证明了
　　H ≥ {log3(m+n)}

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

引用

对于k=1。不用说了
对于k=2。m=1，n=1的情况已经讨论过了。考虑m=2，n=0。这时我们知道坏球比较重。
们知道坏球比较重。m=0，n=2的情况完全类似。

假设对于m+n＜k的情况我们都可以用{log3(k)}次称出坏球。考虑m+n=k的情况。我们把1到m号球称为第一组球，m+1到n号球称为第二组球。

　　设H={log3(m+n)}＝{log3(k)}。那么我们有
　　3^H-1 ＜ k ≤ 3^H
　　3^H-2 ＜ k/3 ≤ 3^H-1
　　3^H-2 ＜ {k/3} ≤ 3^H-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号球为坏球且较重。m=1，n=3的情况完全类似。

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

我们把第一堆球和第二堆球分别放在天平的左右两端。如果平衡，那就说明坏球在第三堆里，这样我们就把问题归结为一个k-2{k/3}个球的问题；如果右边比较重，那么我们得到结论：要么是坏球比较轻，并且它在第一堆中的第二组球，也就是可能较轻的那些球中，要么是坏球比较重，并且它在第二堆中的第一组球，也就是可能较重的那些球中，下面它就归结为一个{k/3}个球的问题了；如果是左边比较重，那么我们也完全类似地将问题归结为一个{k/3}个球的问题。

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

引用

结论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次足以保证找到
　坏球和知道坏球比标准球轻还是重。

评论

1 楼 ouspec 2006-11-15  

有意思的面试题