小球称重问题

题目描述

有 12 个球，外形相同，其中一个小球的质量与其他 11 个不同，给一个天平，最少需要几次把这个小球找出来并且知道这个小球是比其他的轻还是重?

思考轨迹

首先想到的当然是分组称重这样的解法：

• 均分为三组，每组四个
• 取任意两组称重…GG

后经大佬提示，涨了姿势:

信息熵计算公式：

$$H(x) = - \sum_{i=1}^{n} P(x_{i}) \cdot log_2{P(x_{i})}$$

• 有12个小球，分别有重和不重两种状态，即有24种可能，那么信息熵为$H(x)=24 \cdot {1 \over 24} \cdot \log_2{24} = log_2{24} $
• 我们每一次称重存在三种状态，即轻、重、平衡，那么每一次称重的熵为$H(x)=3 \cdot {1 \over 3} \cdot \log_2{3} = log_2{3} $
• 所以理论上称重次数为$ {log_2{24} \over log_2{3}} = 3 $,即三次即可找出小球

100个，1000个也是同理，从信息论的角度来看只是熵大小的差别。

同理，给定称重次数N，也可以反推回去最多可以称多少个小球。（$n = \frac {3^N-3}{2}$）

具体实现

概括一下就是：

• 分为三组
• 平衡Pass，若不平衡，则引入三个正常球替换三个球
• …

final

在金勇的博客上看到这个问题，于此写下回答。

在解决很多常规想法看起来不好确定的问题的时候，从熵的角度去看会很有用。