13 Balls Problem

时间:2023-11-09 23:23:02

今天讨论的是称球问题.

No.3 13 balls problem

You are given 13 balls. The odd ball may be either heavier or lighter. Find out the odd ball in 3 weightings.

分析与解答:

看到这道题,就想起来高中时候数学老师的一句话;“真正难的题不是那些很长的题,而是那些就几句话的题!!!”现在想想真是良训啊。又想到很多老师的话,感觉到失去方显弥足珍贵的名言,不禁唏嘘啊……

有人认为这道题是“One of the Hardest Interview Questions”,我认为是有道理的。学过信息论的人应该知道,这也是信息论中谈及信息量(熵)时的命题。它同时也反映了数据挖掘和充分利用信息量的重要性。对同样的数据,别人就是能挖掘出你得不到的信息。这就是信息时代“信息不对称”的深层表现。在获取同样数据量的情况下,怎样才能做到获得的信息量比别人多?沉思中……

算了算了,还是先给出方案吧:

Step 1. 将这13个球分为3组,分别标号为:A1,A2,A3,A4;B1,B2,B3,B4;C1,C2,C3,C4,C5。

Step 2.(第一次称量)  比较A组和B组的重量。如果A、B组的重量相等,则确认异常球在C组。如果A、B组的重量不一样,则确认异常球在A组或B组。下面开始分两种情况讨论:

情况1. 异常球在C组

Step 3.  (第二次称量)从C组中取出三个球(定为C1、C2、C3),并从A、B组中任取一个球,一共四个球一边两个放在天平上。(第三次称量)如果天平平衡,则异常球在C组剩下的两个球(C4、C5)中,这时只需将其中任意一个球与A、B组中的任一个球相比就能确定那个球是异常球,这个异常球是轻了还是重了。如果天平不平衡,那么我们知道异常球在C1、C2、C3中。进一步我们假设,天平的称重情况为:C1,N > C2,C2(小于的情况同理讨论),这样的话,我们可以进一步确认C1、C2、C3的情况为C1偏重或者C2偏轻或者C3偏轻。这样,我们后面就把C1、C2与两个正常球N、N相比较。如果C1、C2 > N、N ,则C1是异常球,且偏重;如果C1、C2 < N、N,则C2是异常球,且偏轻;如果C1、C2 = N、N,则C3是异常球,且偏轻。

情况2. 异常球在A、B组

Step 3.  不妨假设A1、A2、A3、A4 > B1、B2、B3、B4(小于的情况同样讨论)。那么我们首先得到信息:要么A组中有个球偏重、要么B组中有个球偏轻。(第二次称量)下面我们从A组中取出三个球,从B组中取出三个球。然后,我们分别在天平两边这样放:一边是A1、A2、B1,一边是A3、A4、B2。我们称称看。(第三次称量)如果 A1、A2、B1 > A3、A4、B2那么我们可以判定或是A1偏重或是A2偏重或是B2偏轻;如果A1、A2、B1 < A3、A4、B2那么我们可以判定或是A3偏重或是A4偏重或是B1偏轻;如果天平平衡,则判定B3偏轻或是B4偏轻。下一步的做法,就不用我多说了吧,方法与情况1中的最后一步一样。

至此,我们给出了本题的方案。12(or 13) balls problem是信息论的名题。在Thomas M  Cover的经典著作《信息论基础》(Element of information )中就作为习题出现。其实,我们进行方案设计的基本理念用信息论的行话来讲就是:怎样使每次称量获得的信息量最大。具体是怎样把信息论和本题联系起来的呢,看到网上有一篇文章Robert H.Thouless 的The 12-Balls Problem as an Illustration of the Application of Information Theory。不过我没有查到电子版,有的同学记得给一份我啊,也学习学习,呵呵。