2.1　问题1

例2-1　有16个外形完全一样的铜球，其中有一个球的重量比其他球略轻。问用一架天平称几次一定可以把这个轻球找出来？

解：

把16个球平分成两组（第1次），每组8个，放在天平的两边。立知轻球在天平轻的那头，剩下8个球。同样，再把这8个球分成两组称一次（第2次），剩下4个球。称第3次剩下2个球。称第4次时，那个轻球就被找到了！

用二分法，16=24，可知分4次就一定可以找出轻球。

分析：

问题的本质在于，轻球出现在哪一个位置的概率都相同，等于1/16，我们称之为均匀分布。用天平称一次，可以在两个相同概率的选择中确定其中一个。

对我们来说，“状态”（或信息）的不确定性有多大呢？可以从这样的典型范例中找到不确定性的“单位”。

将16个球一分为二，轻球在每边的概率各为1/2，我们把确定轻球在哪一边的不确定性程度取作一个单位。现用一架天平称一次，确定了轻球在其中的一边，消除了这个不确定性。把包含了轻球的8个再一分为二，轻球在两边的概率仍各为1/2。同样，不确定性还是一个单位。如此继续，我们共4次处理不确定性为一个单位的决策。整个不确定性程度是4个单位。注意，4是16的以2为底的对数，log2 16=4。

用天平称一次，消除了一个单位的不确定性，或者说，可获得一个单位的信息量。出现概率为1/16的事件，包含的不确定性为log2 16=4（单位），故只需要这样称4次，就可以消除其不确定性。

用二等分法进行天平称量的优点在于：每次称量得到的信息量（即消除的不确定性）都相同，可视为一个单位。

你也可以把16个球第一次分为5，5，6三份，在天平的两端各放5个球。若天平一端轻，则轻球就在轻的5个球中；否则，轻球在6个球中。第二次，若是5个球，可以分成2，2，1三份，只要再称一次即可找出轻球；若是6个球，可以分成3，3两份，只要再称一次也可找出轻球。总之，3次就可称出轻球。但是，每次分份时，轻球位置的概率分布不是相同的均匀分布，不容易分析一次称量所得到的信息量。因此，我们不关心这种最少次数的称量方案！