文章目錄

以前专门考虑过这个问题,只是没有记录笔记,和组里的同事说起这个问题,于是又考虑了一次,这次还是记下来为妙。

13球问题说的是有12个标准球和1个不合格的球,这个球可能偏重或者偏轻了,给你一个天平,问至少称多少次可以找到这个不合格的球。

考虑这个问题之前,可以先考虑高中时代,数学老师问过的8球问题。8球问题说的是一共有8个球,其中有一个球偏重了,给你一个天平,问至少称几次可以找到这个球。

一个很显然的办法是,两边各4个,之后拿重的一方再对分称,之后再拿重的一方对分称,一共三次就可以称出来。但这不是最优的,记得当时大部分同学都是这么考虑的,只有一个许杨冰同学不是这样,她说称两次即可知道。方法是,左边放三个,右边放三个,如果是左边重,则球一定在这3个中,从这个三个中取两个,天平两边各放一个,如果两边一样重,则偏重的球是剩下的那一个,如果两边不一样重,则偏重的一方就是那个球。当时就觉得许同学非同一般,后来高考时她考了全班第一。

大三的时候,学习了信息论,发现这个问题可以用信息论的观点来解释。考虑上面的8球问题,当只有3个球时,只称一次即可知道是哪一个球偏重了,也就是说,一次称球,可以知道3种情况,那么2此称球就可以知道9种情况。而8球问题,只有8种情况,所以只需称两次即可找到那个球。考虑上面的13球问题,这里一共有26种情况,1号球偏重,1号球偏轻,2号球偏重,2号球偏轻。。。,因为两次称球可以知道9种情况,那么三次称球可以知道27种情况,而13球一共只有26中情况,所以13球问题只需称3次就可以找到那个球,剩下的问题就是如何称了。

考虑之后,给出了一种解法。为了方便,我们给球编号,1,2,3,4,,,13。
1.首先把1,2,3,4放在左边天平,把5,6,7,8放在右边天平,
2.如果天平一样重,则那个球在剩下的5个球中,其它8个为标准球。之后在这5个球中取3个球,放在左边,取3个标准球放在天平右边,分三种情况
A 如果一样重,则不合格球在剩下的两个球中,对于剩下的两个球,取其中一个出来称,如果偏重或者偏轻,则找到了那个不合格球,如果一样重,则不合格球是剩下的一个(注意,这里我们不能知道它是偏重或者偏轻)。
B 如果左边轻,之后再称一次就可以知道是哪个球偏轻。
C 如果左边重,之后再称一次就可以知道是哪个球偏轻。
3.如果不一样重,则那个球在这8个球中。假设是左边重了,则剩下可能的8种情况,1,2,3,4号偏重,5,6,7,8号偏轻。之后的取法可以这样,左边放三个标准球再加上8号球,右边放5,6,7和4号球。依然分三种情况
A 如果一样重,则1 2 3号球偏重,称一次即可知道结果
B 如果左边重,则5 6 7 号球偏轻,称一次即可知道结果
C 如果左边轻,则8号球偏轻或者4号球偏重,称一次即可知道结果。

现在再来考虑,2时,剩下5个球的情况,5个球的时候,一共有10种情况,9号偏重,9号偏轻,,,13号偏重,所以称两次是无法知道具体是哪一个球偏重或者偏轻,这也是为什么在2的A情况中,如果一样重,则不合格球是剩下的一个,但我们无法知道它是偏重或者偏轻。所幸题目只要求我们找到那个球就可以了,没有要求知道它是偏重或者偏轻。

那么如果一定要找到那个球,且知道它是偏重或者偏轻呢?这样的话就不是这种方法能解决的了,需要精心设计的方法,继续考虑,等知道了再分享。

文章目錄