称重问题与信息论

信息论"/>

称重问题与信息论

朋友给了个网站，翻到最后发现了个称重问题，题目是这样的：

有12个小球，其中有一个小球的重量和其余小球不同（不知道偏轻还是偏重），只能称3次，问如何称才能找出这个小球。

称重问题归根到底归结为信息论的问题，也就是说如何通过充分利用每次称重的信息来得出想要的结论的问题。

具体来说，12个小球，每个小球都有可能偏轻或者偏重，所以一共有24种可能性。问题也就转化为了如何通过3次称重来描述这24种可能性。

假设每次称重只利用左沉或者右沉这两个信息，通过3次称重最多只能表示8种可能性(2的三次方），远小于24种可能性，所以每次称重必然要用左轻左重以及平衡3种信息才能求解，这也是求解此问题的必要条件。

根据上述条件我们可以排除一些严格劣势策略，比如第一次称就左边6个右边6个的称法，这种称法无法利用称平衡这一信息肯定解不出来。

通过以上分析，我们采用编码的方式来求解这个问题，首先把这12个小球编码：

球编号         编码

1             000

2             001

3             012

4             010

5             121

6             122

7             100

8             101

9             212

10           210

11           221

12           222

这只是一种可行的编码方式，编码只要满足以下特性就可：

1、每一位的0