思想海洋的远航分享 http://blog.sciencenet.cn/u/xying 系统科学与数学水手札记

博文

称球问题的通解 精选

已有 18835 次阅读 2013-2-1 12:36 |个人分类:智力|系统分类:科普集锦| 智力游戏, 称球问题

13问题十分经典,就我所知也有三十多年历史了。因为问题简单,不需要预备知识,又有点难度,纯凭清醒脑力来解答,成为大人小孩通杀经久不衰的练脑题,聪明的中学生纸上画画也能解出,大人也就考究个虚空冥想,心智澄明的功力。这问题网上有不少答案,恐怕连中学生都知道了。喜欢做研究的人,就会考虑一般性的问题。

 

在除了一个重量不同的次品外,其他等重的一堆球中,用天平称k次找出来,问这堆球最多可以是多少?

 

它的通解是:最多可以达到n =3**k-1/2个球。这里3**k意思是3k次方。我曾将这证明贴在外面的网上,很多人都看过了,现在附在后面。在科学网写科普,要有点技术含量的新意,才对得起愿意动脑筋看帖子的人。我就在这里分享考虑问题的思路。

 

首先考虑一个简单的情况,假如已知这个次品比正品重(或轻),把这堆球三等分,放两堆到天平两边称一次可以指出是在哪一堆,一直重复这三等分法,就能确定是哪一个。所以称k次可以分辨3**k个球。

 

有人从信息的角度解答这简单题。从n个球中取出次品的概率是1/n,确定它需要log2(n)比特的信息量;用天平称会有三种结果:左重右轻、平衡、左轻右重,称一次给出的信息量是log2(3);所以从n个球中找出次品,需要称的次数klog2(n)/log2(3)=log3(n),也就是n = 3**k ,这和上面的答案是一样的。

 

对于不知次品轻重的情况,从n个球中取出次品的概率是1/n,而这次品是偏重或偏轻的概率是1/2,确定它需要log2(2n)比特的信息量。所以从n个球中找出次品需要称的次数k至少是log2(2n)/log2(3)=log3(2n),也就是2n <= 3**k ,考虑到左边是偶数,右边是奇数,故有n =3**k-1/2,这和通解的答案是一样的。

 

这个信息量说法看起来很牛,既简练又准确。但是做研究,每一步必须有根据,所有说法要落到实处,一直追查到逻辑上没有含糊之处才算完。我们首先要问:为什么可以应用这信息的计算?这球的信息量和天平的信息量是怎么联系起来?

 

“信息论中的编码理论呀!”好。那我们就要考究怎么把这问题转化为编码问题。

 

对于简化问题,把这球排成一列,每次称时相当于编码数字的位置,判断次品属于哪一堆相当于给这位置赋值,从而可以给这列球编号,这构造了编码的模型,当然可以用信息量来解。为了说明可以应用编码的概念,其根据是天平称量把球区分成3堆的分类法。这是绕了一圈来说问题,这里的信息论编码只是用来装饰,除了看起来比较高深以外,对解题没有多大帮助,还不如直接用分类法解来得更直观。

 

对于一般问题,怎么用几次天平称量的状态给这2n种的可能性编码?天平只能作用在物理的球上,每个球联系着两种的可能,在天平的两边必须放等量的球,所以考虑编码还必须受到物理实现的约束。不考虑这些细节,没办法构造编码的数学模型。直接套用信息量计算的公式看起来很牛,虽然结果也对。但深思下去就觉得这个步子迈得太大,缺乏说服力。

 

我举个例子来提疑问。大家知道对于5个球,用天平称两次是没有办法从中区分出次品球。这用信息量的解释是:5个球其中有个次品不知偏重或轻,信息量是log2(10),称两次信息处理能力是2log2(3)= log2(9),当然是不能区分。但是,我们如果加上一个已知的正品球,就能够区分了。(这个解法见《称球问题》帖子和下面决策树,其中放外边那堆5个球的称法,或后面通解的证明)需知这个已知的球信息量是0,加在一起不会减少问题的信息量。或许你说它可以加强天平分辨能力,这就需要深入分析其作用。所以说直接套用信息量的做法,没有揭示其中的逻辑。

 

好了,同分析简化问题看法一样,与其绕一圈套用信息的说法,不如考虑决策树来得直观。

 

决策树【1】是这样的,天平在树的节点上,每个节点依天平的3种状态分出3个分支,称量的次数k相当于树的层数,决策树的叶子是几次称量后可以分辨的状态集。什么是问题空间的状态?每个球有两种状态“疑重”或“疑轻”,分别代表着它可能是重的次品和轻的次品,附上球的编号,n个球对应着2n个状态。这些疑是次品球的状态通过通过节点,即天平称量的分流,沿着不同分支各自走向叶子。叶子中的状态是通过它所经路径称量的排除,次品和它的状态被确定到这里。如果要分辨出次品及其轻重,每个叶子只能包含一个状态,如果只要分辨出次品,叶子里包含的状态必须不超出一个球但可以包含这球的两个状态。举个具体例子。

 

比如说3个球,按编号和“疑重”、“疑轻”,6种状态分别记为1z 1q 2z 2q 3z 3q。将1号和2号球分别放天平左边和右边,3号在外面,一次称量后的决策树如下:

 

疑是次品球的状态及分配

天平的状态

称量后状态

1z 1q [2z 2q] 3z 3q

——左重

1z 2q

 

——右重

1q 2z

 

——平衡

3z 3q

 

第一列表示称量前,所有疑是次品球的状态,及在天平的位置,园括号里的球在天平的左边,方括号的在右边,其他的在天平外边。第二列是称量时天平的状态。第三列是被称量后区分出的疑是次品球的状态集。比如说1z 2q是在天平左重时,疑是次品只可能是1号重或2号球轻。在这叶子里,因为有两个状态,有两个球号的还不知道次品是哪个。只有对应平衡时3z 3q,知道3号球是次品,但不知其轻重。

 

细考决策树中,沿着所有平衡分支走到底的(全平衡)叶子,里面包含着每次称量都是平衡情况下的疑是次品球,它总是放在天平外。因为都没经过称量,所以它包含着每个球的两种状态。如果这叶子里只有一个球号,那个次品球就是它了,但不知其轻重。而所有其他叶子里的球,都至少经过了一次的称量,球一但上过天平,它的两种状态就分离开来,沿着两个分支走去,所以不可能同在一片叶子里。在这些叶子里,每个球都只能有一种状态。考虑n个球,通过称量要把它们区分出来,因为全平衡叶子必须包含一个球的两种状态,这需要2n-1片叶子。K次称量最多可以有3**k片叶子,我们有:2n-1 <= 3**kn <=3**k+1/2。这是称k次能够区分球的上限。这个上限不一定能够达到,要看实际的测量是怎么分配的。

 

下面的决策树是13球的一个区分方案:将1-4号球放天平左边,5-8号右边,9-13号外面,这里第357列是第一次、第二次、第三次称重后天平状态区分出疑是次品球的状态集,其中园括号里是下次称量时,天平左边中的球号状态;方括号则是右边的;括号外是在天平外待定的球号状态,x表示在天平那边加一个正品球。

 

 

称第一次

状态及分配

称第二次

状态及分配

称第三次

状态

All States

——左重

(1z 2z 5q) [3z 4z 6q] 7q 8q

——左重

(1z) [2z ] 6q

——左重

1z

 

 

 

 

 

——右重

2z

 

 

 

 

 

——平衡

6q

 

 

 

——右重

(3z) [ 4z] 5q

——左重

3z

 

 

 

 

 

——右重

4z

 

 

 

 

 

——平衡

5q

 

 

 

——平衡

(7q ) [8q]

——左重

8q

 

 

 

 

 

——右重

7q

 

 

 

 

 

——平衡

 

 

——右重

(1q 2q 5z ) [3q 4q 6z] 7z 8z

——左重

(3q) [4q] 5z

——左重

4q

 

 

 

 

 

——右重

3q

 

 

 

 

 

——平衡

5z

 

 

 

——右重

(1q ) [2q ]6z

——左重

2q

 

 

 

 

 

——右重

1q

 

 

 

 

 

——平衡

6z

 

 

 

——平衡

(7z) [ 8z]

——左重

7z

 

 

 

 

 

——右重

8z

 

 

 

 

 

——平衡

 

 

——平衡

(9z 9q 10z 10q) [11z 11q x ] 12z 12q 13z 13q

——左重

(9z) [10z] 11q

——左重

9z

 

 

 

 

 

——右重

10z

 

 

 

 

 

——平衡

11q

 

 

 

——右重

(9q) [10q] 11z

——左重

10q

 

 

 

 

 

——右重

9q

 

 

 

 

 

——平衡

11z

 

 

 

——平衡

(12z 12q) [x] 13z 13q

——左重

12z

 

 

 

 

 

——右重

12q

 

 

 

 

 

——平衡

13z 13q

 

 

这个决策树很直观地揭露出很多信息。其一,(3**k+1/2是个很好的上界,通过合适的配置可能实现。如在第一次平衡后的子树显示,加一个正品球就可以区分5个球达到了这个上界,注意到这个13球的决策树,叶子中有两个空位,如果称量时手里有个正品球,第一次称9个加上这个正品球,3次就能区分出14个球,也达到这个上界。所以13球的局限在于天平分配上,这暗示着没有已知正品球时,可以达到的极限是n =3**k-1/2。其二,因为全平衡叶子不能区分球的两种状态,如果要求确定次品的轻重,我们就不能利用这个叶子,所以这种情况下的极限是n =3**k-3/2。有了这些猜测和决策树分配的思路,不难用数学归纳法证明这些结论。

 

《称球问题》帖子里,有人建议用黄金分割法(优选法)来确定放在外面的球数,对13球这确实近似于正确值5,但是0.618比率并没有与正确值有内在联系,也只是一个猜测法。从下面证明可以看出,对于称k次情况,放在外面的球数应该是(3**(k-1)+1/2。当k > 3时,优选法建议的值就开始不对了。

 

有人说,这题中的正品球应该是不可区分的,就像玻色子一样。这个改变了题意。不过探索新问题这也是做研究时常做的事,就像我们看到很漂亮的理论结果,就看看改变一下条件能否也得出有意义的结果。我想了一下,觉得这个改变把难度降低了点,家里有小孩的不妨让他们试试,这个(因为不可区分)不允许混合称过的球及没称过球的解法。问:在这时要几次才能分13球?反问题是:称3次可以从多少这样的球中找出次品?

 

做研究、玩游戏和写帖子凡是有意义的,都需要有一点技术含量。这才对得起花时间的读者和自己的智商。有时看到没什么技术含量的东西却冠以夸张的说法,还顾盼自雄,真的很无语。这如果只是想炒作自己,尚无大害。如果做研究也是这般的态度,写的也是吹毛求疵但没有什么有意义的内容,类似于:发现了Gale-Shapley算法不符合“为稳定婚配设计的求偶规则”提法之类的口水文,为此洋洋自得,以为捍卫了数学的严谨性和科学的严肃性,那学生们就可堪忧虑了。

 

 

【附录】

称球问题通解的证明

 

做研究最好的方法是先看简单特殊的问题,从直观中找出思路,经过前面这些思考,我们已经找到诀窍,所以不难将它扩大成一般性的结果。

 

考虑一般问题,把球分三堆,放两堆等数的球上天平,如果平衡,次品当然在外面这一堆。如果不平衡,比如说左边重,我们只知道外边的肯定是正品,但次品不知道是在天平的哪一边。重的那一边的球定义为“疑重球”,如果在这边,那次品一定是较重。轻的那一边定义为“疑轻球”,若是在这边则次品较轻。所以天平上的这些球经过一次称量之后已经被消除掉一部分的不确定性,称为半确定的球。半确定的球集合中只有两类的球,疑重球或疑轻球,集合中可以混合着这两类球,但知道每个球属于哪一类。

 

现在证明。在叙述时,我们只考虑这堆球的数量在可达到最多的情况。对少于这个数的情况,我们总是可以这样的安排:使得分三堆时,每一堆都不大于证明中分法的数量,这样归纳法总是能够进行下去。引理和定理中的球是可以达到的最大的数量,否则在三分时总有一方超过证明里分配的数量,从归纳法推导可以看出这将导致k=1情况下不可能实现。

 

引理1:在多于2个的一堆球,已知次品在其中,称k次可以并最多在3**k个半确定的球中找出次品,并且知道其轻重。

 

用数学归纳法,k=13个半确定的球,一定至少有两个属于同一类,比如说疑重球,将这两个上天平,重的那个就是次品,如果平衡,外边的那个就是次品,而且从它的类别知道这次品是较重还是较轻。验证正确。

 

假设结论对k-1次正确。将不多于3**k个半确定的球三等分,如果不能够等分,除天平两边要等数外,三方都不多于3**(k-1)个球,且使得两边共有偶数个疑重球,记为2a个。这总是可以做到的。因为我们可以把天平上“不齐整”的球和外面异类的球对调。这样天平左右各有a个疑重球和3**(k-1)-a个疑轻球。这一般有多种可能的a值满足要求,任取一个都行。这时如果左边重,左边的a个疑重球和右边的3**(k-1)-a个疑轻球,共3**(k-1)个半确定球有嫌疑,其他都是正品。如果右边重,同理将嫌疑缩小到3**(k-1)个半确定球。如果平衡,嫌疑在外面的3**(k-1)个半确定球中。如果这嫌疑是1个或2个半确定球,可以用一个正品与其中一个称一次解决,其他情况我们已知用k-1次可以解决不多于3**(k-1)个半确定的球。证毕。

 

引理2:已知次品在其中,加一个已知的正品球称k次,可以并最多在(3**k+1/2个球中找出次品,但有且仅有一种情况不知其次品的轻重。

 

k=1情况,有2个球,取一个与正品球上天平,如果平衡,次品在外面,但不知它比正品轻还是重,注意这是归纳证明中仅有的情况。如果只有1个球,它就是次品了,称一次可以知道比正品轻了还是重。

 

假设结论对k-1次正确。考虑第一次天平称量,一边取(3**k-1-1/2个加上一个正品球,另一边取(3**k-1+1/2个球。我们知道这次称量以后,如果天平平衡,那么嫌疑在外面。余下k-1次可以解决这里的不超过(3**k-1+1/2个球,有且仅有一种情况不知其次品的轻重。如果天平不平衡,天平的两边都是半确定的球。由引理1知道,余下k-1次可以解决这里的3**(k-1)个球。因为这个数是奇数,所以我们必须在第一次天平称量时再加上一个已知的正品球。因此称k次,可以并最多解决3**k-1+3**k-1+1/2=3**k+1/2个球。证毕。

 

定理在一堆等重球中有一个重量不同的次品球,用天平称k次找出来,这堆球最多且可以是(3**k-1/2个球。

 

在第一次称量我们最多可以将3**(k-1)-1个球两等分放在天平上,如果不平衡,由引理1,可以再称k-1次解决。如果平衡,天平这里都是已知球,由引理2,可以再称k-1次解决外面的(3**k-1+1/2个球。所以总共可以解决(3**k-1/2个球。证毕。

 

由这个定理我们可以知道称2345次,分别可以在41340121个球中找出那个次品,因为这个证明是构造性的,所以知道该怎么称量。

 

如果在称球问题中不知道有没有这个次品球存在,这和判别出嫌疑的次品球是较轻还是较重是同一个问题。在引理2证明中知道,只有每次分堆时,天平都是平衡的,总是被分在外面的那个球被认为是次品球时不知轻重。把这个球去掉,或者说要解决的问题少了一个球就行了。这也就是说,用天平称k次可以在一堆(3**k-3/2个球中确定有没有一个重量不同的次品,如果有,我们知道是哪一个,确定是较轻还是较重。

 

有人问,如果我要解决问题那堆球比你构造性证明中的数量少,怎么办?你参考证明的提示,每次分堆时尽量三等分把不齐整的数搁在外边那堆,不就行了?

 

【参考资料】

【1】       维基百科,决策树http://zh.wikipedia.org/wiki/%E5%86%B3%E7%AD%96%E6%A0%91

 



https://blog.sciencenet.cn/blog-826653-658533.html

上一篇:称球问题
下一篇:六人集会问题
收藏 IP: 50.131.158.*| 热度|

18 张华容 魏东平 鲍海飞 梁建华 丁大勇 赵凤光 曹须 程代展 戴德昌 李伟钢 鲍得海 罗祥存 陈学雷 杨正瓴 张能立 yueliang002 xiyouxiyou ddsers

该博文允许注册用户评论 请点击登录 评论 (36 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-7-15 17:37

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部