|||
我们湾区有个研究生院同学的封闭论坛,大家常在那儿聊聊天、练练手,权当是网上聚会。微生物所的老文开了音乐讲座,学科学史的刘兄介绍苏联歌曲,理论物理所来的张女侠分析音阶后面的数学,秀出计算机产生的分形音乐。应用数学所的管克英乘机谈起数学之美,我则写个“美的颠覆”系列,用悖论和数学危机来唱对台戏。陈教授贴出质疑玻尔兹曼方程的初稿,大家讨论得烟云四起,老管联想整出了篇“烟云拓扑结构的稳定性”。
现在正忙着写傻博士的才女张天蓉,在那儿给同学的孩子出个练脑题:
"有十三个球,其中十二个重量相同,只有一个次品不知是轻还是重了。请用天平称三次,将这个次品找出来。"
这题我在念研究生午餐时听说过,当时想了一小时。晕。不了了之。后来这么多年也见过不少称球题,都没这道题难度高。虽然她是给小孩喂招的,考虑到这道题的难度,咱大老爷来接也不丢份。
题中球数目有限,只要有耐心在纸上写写画画并不难得解。所以考大人的大约是不借外物,虚空冥想,心智澄明的功力。智力的一项成分是思考堆栈(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个球三次足矣。反过来设计考题:称四次可以分辨最多几个球呢?有没有一般性的答案,这留给大家伤脑筋,我下次再谈。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-12-23 21:03
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社