[math] 从信息论到天平称球

封面图是信息论的创始人 香农

1 简介

最近在面试时被问过“天平称球”之类的问题，在此做个总结。

首先来看一下几个问题：

1. 有27个球，其中 1 个球比其他球重。现在有一个天平，问最少需要多少次称量，才能找出质量不同的球。
2. 有27个球，其中 1 个球质量与其他球不一样。现在有一个天平，问最少需要多少次称量，才能找出质量不同的球。
3. 有n个球，其中 1 个球比其他球重。现在有一个天平，最多称2次，想找出质量不同的球，问n最大取值多少。

网上有比较多的解答，但是大部分都是写 “怎么做” 的，没有写 “为什么这么做” 的，所以我尝试从信息论的角度提供一个解题思路。

2 信息论

介绍一些信息论的基本概念。

2.1 信息熵

信息论从概率的角度，对事物的信息量进行了度量，这个信息度量称为信息熵。

• 信息熵表示了一个随机变量所拥有的不确定性。熵越大，不确定性就越大；熵越小，不确定性就越小。
• 信息熵也表示消除随机变量的不确定性，所需要的信息量。熵越大，所需信息量就越大；熵越小，所需信息量就越小。

2.2 信息熵公式

对于一个离散随机变量 X ，信息熵的计算方法如下，单位是比特

H(X)=-\sum_{x \varepsilon X}^{}P(x) \log{P(x)}

其中 P(x) 为 X 取值为 x 的概率。

2.3 信息熵的最大化

对于一个离散随机变量 X ，假设它可取值为 x_1,x_2,...,x_n ，对应概率为 p_1,p_2,...,p_n ，那么当 p_1=p_2=...=p_n=1/n 时，熵最大。

写成公式如下：

\begin{align*} &\max_{p_i} \ \sum_i -p_i \log{p_i}\\ & \begin{array}{r@{\quad}r@{}l@{\quad}l} s.t.&\sum_i p_i = 1\\ &p_i \geq 0\\ \end{array} . \end{align*}

利用拉格朗日乘子法，变为：

L(p_i, \alpha) = \sum_i -p_i \log{p_i} + \alpha(\sum_i p_i - 1)

由上式可知， L(p_i,\alpha) 对 p_i 的导数相同，因此 p_1=p_2=...=p_n=1/n 。

3 信息论与称球问题(1)

以第一个题为例子进行说明：有27个球，其中 1 个球质量比其他球大。现在有一个天平，问最少需要多少次称量，才能找出质量不同的球。

对于这个问题，想要找出质量不同的球，也就是要消除这些球中的不确定性。想要称量次数最少，也就是要每一次消除的不确定性尽可能大。

• (1) 所有球中的信息量是多少呢？

27个球中，每一个球是质量比较大的球的概率是 1/27，那么总共的信息量是： H(X)=(-\frac{1}{27}) \times \log (\frac{1}{27}) \times 27 = \log(27)

• (2) 一次称量能消除的信息量是多少呢？

因为称量的结果有：左边重、右边重、两边一样重三种情况，因此最多能消除的信息量是： H(Y)=(-\frac{1}{3}) \times \log (\frac{1}{3}) \times 3 = \log(3)

• (3) 理想情况下需要几次称量

于是理想情况下，需要的最小称量次数为 H(X) / H(Y) ，刚好为 3。这是理想的情况，还需要正向检验一下是否符合要求。

• (4) 称量方案

符合要求的意思是：每一次称量，都能消除 H(Y) = \log(3) 的信息量。

因为 H(X) / H(Y) 刚好为3，所以需要每次都消除 H(Y) = \log(3) 的信息量，如果 H(X) / H(Y) 为 2.5，那就不需要这么严格。

• (4.1) 第一次称量

易得，当天平左右两边都放9个球的时候，天平出现的3种可能等概，因此这就是第一次称量的方案。

当进行第一次称量后，无论天平出现什么状态，我们都能将目标缩小成9个球，剩下的信息量为 \log(9) ，换句话说，第一次称量消除的信息量为 \log(27)-\log(9)=\log(3) 。

• (4.2) 后两次称量

聪明的你一定知道后面两次称量怎么做了，这里就不说了。

4 信息论与称球问题(2)

对于第一部分中提到的第二题和第三题，解题思路也是一样的。

对于第二题，因为不知道质量不同的球是比其他球重还是轻，因此多了 \log(2) 的不确定性，总共的不确定性为 \log(27) + \log(2) = \log(54) 。对于每一次称量，最多能消除 \log(3) 的不确定性，因此最少需要称量次数为4次。

对于第三题，因为一次称量，最多能消除 \log(3) 的不确定性，所以2次最多能消除消除 2\log(3) 的不确定性， 2\log(3) \geq \log(n) ， n 最大为9。

5 总结

天平称球的问题，可以从信息论的角度来思考。本质上，每一次称量会给我们带来信息量，减少不确定性，当不确定性减小为零时，便得到了确定的结论，也就是答案。

水平有限，哪里写错了，欢迎指正，虚心接受大家的意见。

如果觉得我的文章对你有帮助，欢迎点赞、收藏、关注呀，以激励我更好地分享呀～