主题：【原创】从两个经典智力趣题谈起(一) -- 丁坎

【描述】有 N = 3^n（3的n次方）个球，为方便以后的描述起见，将它们排好序。已知的信息是：其中有一个坏球；并且这个坏球出现的位置及其轻重，可归类为下列两种情况：

1、如果坏球出现在前‘N+’个位置上（1，……，N+），那么坏球重于好球。

2、如果坏球出现在后‘N-’个位置上（N+，……，N），那么坏球轻于好球。

（N+和N-这两个数是已知的，N+ + N- = N。）

有一台只能给出{“左重”、“平衡”、“左轻”}指示的天平。

【称球引理1】称量n次，便可将那个坏球所在的位置找出来（由题设，一旦确定其位置，那么亦马上可知其为轻或为重）。

【证明】

（A）当 n=0 时，就是说，有 N = 3^0 = 1 个球，已知其中有一个坏球（并且N+也是已知的，其取值为0或1。譬如若N+=0，那么坏球必然轻于好球，因为坏球位于1，排在N+的后面），这就意味着，坏球的位置及轻重都是已知的。所以不需称量，就已经知道结果了。故而所需的称量次数为0。

（B）设 n=K 时，命题成立。

（C）当 n=K+1，我们在 N= 3^(K+1) 个球中，选出 M= 2 × 3^K 个球，条件是：其中可能是轻球的个数，以及可能是重球的个数，都是偶数。（由“二色划分引理”，这是可以做到的。）既然它们都是偶数个，那就可以各自分为两半，在天平的左右托盘各放一半。

例如，假设我们选出了总共 M=6 个球，其中两个可能为轻球，四个可能为重球。那么我们将可能为轻球的那两个，分成两个子集，在天平的左右托盘各放其一；将可能为重球的那四个，亦类似地分成两半。就是说，在天平的左右托盘各放1个可能是轻球的球，以及2个可能是重球的球。

现在，天平的设置为：左盘有{QQ……Q，Z……Z}，右盘有{qq……q，z……z}。其中，‘Q’表示可能是轻球；‘Z’表示可能是重球。大写字母表示在左盘，小写字母表示在右盘。由划分方法，“QQ……Q”的个数等于“qq……q”的个数；“Z……Z”的个数等于“z……z”的个数。

我们进行称量，假设结果是“平衡”，那就说明，坏球只能在没被选中的那 N-M = 3^K 个球中。我们还剩下K次称量，由（B），我们可以从中找出坏球。

假设结果是“左轻”，那就说明，“Z……Z” 和 “qq……q” 那些球肯定是好的（因为不然的话，假设坏球是“Z……Z”或“qq……q”其中之一，那就应该左端为重、右端为轻才对），那些未被选中的 N-M = 3^K 个球 也都洗脱了嫌疑，因为罪魁祸首可以确定是在 “QQ……Q” 或者 “z……z”之中。 这些仍有嫌疑的球总共有多少个呢？ 正好 3^K 个！因为“QQ……Q”和“z……z”各为选中的轻、重球的一半，所以它们的和就是选中的球总数的一半，就是 M/2 = 3^K。 我们现在还剩下K次称量，由（B），可以从中找出坏球。

假设结果是“左重”，推理类前。

引理证毕。