【 原文由 grass 所发表 】
这是我当时的一份作业题报告.写的有些乱，不过，应该可以看明白的，我想。
试题一：
有12个球,其中有一个坏球,但不知道是轻是重。试用天平称三次，找出坏球，并说出它
是轻是重。
试题二：
称n次，最多可以在多少个球中找出坏球来。（坏球只有一个）
对于天平问题，我们通常都可以把它和3相联系，这是因为对于每一次称物，都可以分
为三堆，天平上两堆，再加上未放上去的一堆；这样无论天平是否平衡，我们都可以得
到一些信息，并且信息不浪费。具体先看试题一的解答：
12个球，分别编号1，2，……，11，12。
1、 1，2，3，4 对 5，6，7，8 （一）
< 转6 ; > 转10 （类似 2、 9，10 对 11，1 （二）
< 转 5 ; > 转 4 ; = 转3
3、 1 对 12 （三）
< 坏球为12 ，重；> 坏球为12 ， 轻 ；不可能=。
转999；
4、 9 对 10 （三）
< 坏球为9 ， 轻；> 坏球为10 ， 轻 ；= 坏球为11 重。
转999；
5、 9 对 10 （三）
< 坏球为10 ， 重；> 坏球为9 ， 重 ；= 坏球为 11 轻；
转999；
6、 1 , 2 , 5 对 3，4，6 （二）
< 转9 ；> 转 8 ；= 转 7
7、 1 对 7 （三）
< 坏球为7 ， 重 ；< 坏球为8 ， 重 ；= 不可能
8、 3 对 4 （三）
< 坏球为 3 ，轻 ；< 坏球为 4 ， 重 ；= 坏球 5 ，重
9、 1 对 2 （三）
< 坏球为 1 ，轻 ；< 坏球为 2 ， 重 ；= 坏球 6 ，重
10、 类似于6—9
999、 结束。
通过对第一题的思索解答，我们可以发现一些规律：对于称n次，若我们能把称n-1次的
问题解决，n次就可以用递推来求出球的个数。（对于我们要解决的这个问题，用f(n)表
示。）
但是，也不是单纯简单的递推。因为我们在称第一次的时候，得到了一些信息，这些信
息可以给我们后面的称球带来帮助。
我们来分析第一次称的三堆球：
(一)若不平衡，我们得到的信息是：
1． 坏球在天边上的两堆里；
2． 有一堆的球重，一堆轻。
大家往往会忽视第二条信息，实际上这条信息是非常重要的。若我们知道一些球的轻重
关系，我们可以用比不知道这个关系称的次数更少就得出结论。如：若告诉你坏球轻，
那么27个球只要三次就够了。
所以我们要研究一下，若我们知道一些球的轻重关系，n次最多可以称出多少个球。我们
用函数h(n)表示。
（二）若平衡，则得到的信息是：
1． 坏球在剩下的一堆中；
2． 有若干个好球可以给我们利用。
第二条信息又是大家容易忽视的。就如12个球，称第一次若平衡，我们就可以用天平上
的球作为标准球。有标准球，两次可以称称出4个球（见第一试题解答部分的2—5）；若
没有的话，就只能称出3个球。
所以我们还要研究一下，若我们有一个标准球，n次最多可以称出多少个球。我们用函数
g(n)表示。
定义一：若一个球，若知道它不可能偏重（或知道不可能偏轻），则我们称此球为半确
定重球（或半确定轻球）；半确定重球和半确定轻球统称为半确定球。
第一题中，通过第一次称重后，若不平衡，则1,2,3,4,5,6,7,8号球都成为半确定球，
若1，2，3，4〈5，6，7，8，则1,2,3,4为半确定轻球，5,6,7,8为半确定重球。
定义二：若一个球，若知道它是好球，则我们称此球为确定好球；若知道是坏球，确定
坏球。确定好球和确定好球统称为确定球。
第一题中，通过第一次称重后，若平衡，则1,2,3,4,5,6,7,8号球都成为确定球好球。
定义三：若一个球，既不是确定球，也不是半确定球若，则我们称此球为不确定球。
第一题中，通过第一次称重后，则9，10，11，12号球都成为不确定球。
一次未称之前，所有球都是不确定球。
引理一、对于放上过天平的球，都是半确定球或是确定球
这是个显然成立的命题。
定义四：若所有球都是半确定球，那么n次可称出的球的最大个数我们用 h(n)表示。
引理二：h(n)=3^n。
证明：
用归纳法来证：
⑴对于n=1,先证3个球是可称的，再证4个是不可称的。
① 3个球可称，
若全为半确定重球，任意挑两个，若不平衡，重的就是坏重球；否则，剩下的那个就是
坏重球；
全为半确定轻球同理；
若两个半确定重球，一个半确定轻球，则称两个两半确定重球，若不平衡，重的就是确
定重球；否则，剩下的那个就是确定轻球；
若一个半确定重球，两个半确定轻球同理。
所以，3个求可称。
②四个球不可称
若是4个球，天平称一次，只能提供三条信息，由抽屉原理，必然有两个球的信息是相同
的。故一次无法保证能判断出来。
故，n=1是h(n)=3^n是成立的。
⑵设n = k时命题成立，对于n=k+1
①先证t=3^(k+1)个球是可判断的：
设t中有a个半确定重球，b个半确定轻球,t =a + b ;
由对称性，不妨设a>b (a + b是奇数，所以不可能相等)
按如下方法分为三堆：
若a>=2*(3^k),则天平两边各放3^k个半确定重球。若不平衡，坏球在重的那堆中；平衡
的话，坏球在剩下的那堆中。这时剩3^k个球，k次可判断出来，共k+1次，成立。
若a<2*(3^k), 则天平两边各放[a/2]个半确定重球,3^k-[a/2]个半确定轻球。若不平衡
，坏球在重的那堆中的半确定重球或轻的那堆半确定轻球中；平衡的话，坏球在剩下的
那堆中。这时剩3^k个球，k次可判断出来，共k+1次，成立。
a < b 同理可证。
所以3^(k+1)个球是可判断的。
②若3^(k+1)+1个球，称一次，只能提供三条信息，由抽屉原理，必然有3^k+1个球的信
息是相同的，这3^k+1个球无法用k次称出。故k+1次无法保证能判断出来。
故，n=k+1也成立。
由归纳法，h(n)=3^n对一切自然数都成立。
再回到原题，来求f(n).
对于第一次处理后，若不平衡，天平两边的球都将成为半确定球。设两边球个数各为a个
，另外一堆个数为b个。易知，a与b相互独立。为使得f(n)=2a+b最大，即要分别求出a
, b的最大值。
由引理二，这2a个半确定球要在n-1次判断出，当且仅当
2a <= h (n-1)=3^(n-1).
但等号无法取到，因为3^(n-1)为奇数,所以2a<=3(n-1)-1,
max(a)=(3^(n-1)-1)/2
f(n)=(3^(n-1)-1)+max(b)
定义四、给一个确定好球，n次能称的最多非确定球的个数用g(n)表示。
引理三：g(n)=f(n)+1
若有任意确定好球的话，g(n)比f(n)可提高效率的地方就在于第一次称的时候可以两边
放的非确定球的个数不一样多。一边放c个不确定球，一边放a个不确定球和c-a个确定好
球，剩下一堆为b个。平衡的话,b个球的处理同f(n),所以此时的max(b)显然等于f(n)的
max(b)。若不平衡的话，就有a + c个不确定球。
a + c <= 3 ^ ( n – 1 ) （等号可取）
令c=a+1=(3^(n-1)+1)/2,则此时只需要一个确定好球,
g(n)=max(a + c)+max(b)=3^(n-1)+max(b)=f(n)+1 #
再来研究max(b).若不平衡,则b个球全为确定好球,否则,全为非确定球。但天平上的球
全为确定好球。这时的b就恰好同我们刚刚讨论的g(n). 即有max(b)=g(n-1)=f(n-1)+1.
故有f(n)=3^(n-1)-1+f(n-1)+1 =f(n-1)+3^(n-1)
这是一个递推公式。
我们又易知，f(2)=3 ,所以易解得
f (n)=(3^n-3) / 2
故，称n次，最多可以在(3^n-3) / 2个球中找出坏球来。（坏球只有一个）
当n=3时，即第一题，f(3)=12. 3次能称得的最大数目将是12个。
