称球问题（1）

       榕城老应

我同学中一位才女给朋友的孩子出个练脑题："有十三个球，其中十二个重量相同，只有一个次品不知是轻还是重了。请用天平称三次，将这个次品找出来。"
 
这题我在念研究生午餐时听说过，当时想了一小时。晕。不了了之。后来这么多年也见过不少称球题，都没这道题难度高。虽然她是给小孩喂招的，考虑到这道题的难度，咱大老爷来接也不丢份。
 
题中球数目有限，只要有耐心在纸上写写画画并不难得解。所以考大人的是不借外物，虚空冥想，心智澄明的功力。智力的一项成分是思考堆栈（Call Stack）的深度，据说有个天才能够考虑十七层的深度而不乱套。咱们现在记性不如前，但经验丰富了，可以想出只需要记住较少几层的算法来。
 
昨晚熟睡，梦中忽得答案。

下面是思考的过程。

13个球要称量，肯定要分3堆。放外边那堆，喵一眼就知道不外乎只能考虑3，5，7个。若放7个，怕是傻了，剩下两次怎么分得清？3个，太天真了。最可能是5个。蒙对了这数目，省你不少力气，不然要多费一层思考的堆栈来排除了。

放外边那堆5个，剩下8个，两边4个上天平去称。

先考虑容易的情况，天平称得一样重。次品就在放外边那堆5个中了。再将这5个分3堆，放外边2个，剩下2个放天平左边，1个右边再加上1个第一次称过已知是正品的球。如果还一样重，将放外边2个随便拿一个上天平与正品相比就能知道是这2个中哪一个了。思考退回一层，如果不一样重，比如说左重右轻。那么如果次品在左边的一定较重，如果在右边则它较轻。将左边那2个上天平，它们不平衡，重的那个有问题。若平衡，右边只有一个未判明的，那就是它了，而且知道次品是轻的。

好了，容易的情况解决了，思考的堆栈退回一层。第一次称的8个，两边4个的天平，左重右轻的情况。左边留下4个，右边留下2个。撤下右边2个。留在天平的怎么折腾先不管，如果第二次称分不出轻重来。次品就在撤下这2个中，再称一次就能得答案。

回来考虑天平左边留下4个，右边留下2个的残局该怎么称？对调左右天平中的各一半的球，再称一次。结果不外乎：平衡，左重，右重。平衡的上面已考虑了。还是左重则次品在没掉换的左边2个，右边1个球中，依前面处理5个球称过第二次后的逻辑，再称一次可解决。若是右重了，次品则在交换过的3个球中，称一次也可解决。

在这个过程中，我们知道了分辨13个球三次足矣。反过来设计考题：称四次可以分辨最多几个球呢？有没有一般性的答案，这留给大家伤脑筋，我下次再谈。