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

【描述】有 N =（3^n - 1）/2 个球，其中可能有一个坏球。（坏球可能比好球轻、也可能比好球重。）我们手头还有一个已知的好球。

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

【称球引理2】称量n次，便可确定：有没有坏球，若有，坏球在哪儿，它比好球轻还是重？

【证明】

分析：这N个球可能的状况共有 1 + 2×N = 3^n 个。（‘1’：没有坏球；‘2×N’：坏球在1……N个位置上，每个位置上还有轻或重两种可能。） 称量n次能给出的信息就是 3^n 个（不取log2()）。所以，这个N是n次称量所能确定结果的球数上确界。 同样地，“称球引理1”也是上确界。

（A）当n=1，那么N=1，将它和手头的好球用天平作比较，就知道结果了。

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

（C）当n=K+1，我们如此来划分那N个球：

留着 N0 = （3^K - 1）/2 个球不选，选中的是 N - N0 = （3^(K+1) - 1）/2 - （3^K - 1）/2 = (3^(K+1) - 3^K)/2 = (3× 3^K - 3^K)/2 = 3^K. 这是奇数，无法分成相等个数的两份，放在天平的左右边。不用急，这时那个好球正好可以派上用场了。将那 3^K 个球，连同一个好球，划分成两份（每份有(3^K+1)/2个球），放在天平的两端。进行称量。

假设结果是“平衡”，那么那个可能的坏球只能在那留下的N0个球中。我们还剩K次称量，由（B），保证可以完成任务。

假设结果是“左重”，那么那个必然的坏球就在天平上的 N - N0 个球中，我们就可以给这些球贴上标签，凡是在左端的球，都贴上“可能重”的标签；凡是在右端的球，都贴上“可能轻”的标签。（好球不用贴标签了。） 那么我们手头的问题是： 3^K 个有标签的球，需要称量K次，将坏球（及其轻重）找出来。由“称球引理1”，这是可以完成的。

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

引理证毕。