13-balls-problem.md

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、C3）（小于的情况同理讨论），此时，我们可以进一步确认（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。