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次就可称出轻球。但是,每次分份时,轻球位置的概率分布不是相同的均匀分布,不容易分析一次称量所得到的信息量。因此,我们不关心这种最少次数的称量方案!