12球问题

Table of Contents

前言 #

有12个球，已知其中11个球的重量是相同的，有一个球的重量不同，如果用天平称重，最少称几次就一定能够找到那个重量不同的球。

信息=》编码 #

对球编码 #

先对12个球进行编码，用1~12表示即可。

对初始状态编码 #

在最初的状态，每个球都可能是那个独特的球，有12种可能，这个独特的球可能是重的也可能是轻的，因此一共有24种可能：

1重2~12轻
2重1、3~12轻
3重1、2、4~12轻
。。。
12重 1~11重
1轻2~12重
2轻1、3~12重
3轻1、2、4~12重
。。。
12轻 1~11重

为什么要区分这个球是重的还是轻的呢？这是因为我们衡量的工具是天平，而重量决定了天平的状态。

换个角度看，如果球还有不同的颜色，那么我们也不用考虑颜色这个属性，因为颜色不影响天平。

或者如果用的是电子秤，也不用考虑是重还是轻。

理论上的最优解 #

对于一个天平来说，有三种状态：左倾斜—左边重右边轻、右倾斜—左边轻右边重、平衡—左边和右边一样重。

每次称重都能够获得三种结果，每种结果都是一堆球的状态集合，最理想的状态是这三种结果对应的状态集合平均且不冲突——即三种结果平分了状态集合。

假设集合中的状态数量为N，那么一次称重能够将确定的状态降低到(1/3)N，那么M次称量能够将确定的状态降低到N((1/3)^M)个，也即M次称量能够得到稳定的确定状态，需要保证总的状态数不能够大于3^M.

现在N为24，那么可以得到M的最优解为3（3^3=27>24）.

证明能否达到最优解 #

1. 将24个状态划分为8-8-8 #

显然，将12个球划分为3堆，每堆4个球、8个状态。

我们令1~4为一堆，5~8为一堆，9~12为一堆，并且将1~4与5~8放到天平两侧。

如果天平左倾，说明1~4中有一个球重或者5~8中有一个球轻。
如果天平右倾，说明1~4中有一个球轻或者5~8中有一个球重。
如果天平平衡，说明9~12中有一个球重或者轻。

在这三种情况中，前两种是等价的，所以我们只需要考虑第一种和第三种情况即可。

2. 将8个状态划分为3-3-2 #

上一次称量后我们得到两种需要考虑的情况，先看后面一种：9~12中有一个球重或者轻。

将这8种状态分为3-3-2，显然我们可以得到

9~11中有一个球重
9~11中有一个球轻
12是重的或者轻的

为了达到这种划分，我们让9~11划分为一堆、1~3划分为一堆（1~3已经证明是正常的球）进行称量即可。

再看前面一种情况：1~4中有一个球重或者5~8中有一个球轻。

将这8种状态分为3-3-2，可以是：

1~3中有一个球重
5~7中有一个球轻
4是重的或8是轻的

显然将1~3划分为一堆、4~7划分为一堆放到天平上进行称量即可。

3. 由3或者2个状态得到1个状态 #

经过上边两次的称量，我们可以得到这样几种等价的情况：

12是重的或者轻的
1~3中有一个球重
1~3中有一个球轻
4是重的、8是轻的

显然这几种情况经过一次称量都能够找到那个特殊的球！

拓展 #

所有状态集合都是可达的吗？ #

比如现在要将状态：1~4中有一个球重或者5~8中有一个球轻划分为3-3-2，并且划分的状态集合为：

1、2是重的，5是轻的
3、4是重的，6是轻的
7、8是轻的

为了达到这种状态，让1、2、6在一侧，3、4、5在另一侧即可。

换一种划分方式：

1、2是重的，5是轻的
6、7是轻的，3是重的
4是重的、8是轻的

如何得到这3种状态集合呢？

让1、2、8在一侧，4、5、9（正常球）在一侧即可。

但这里我们使用到了9球，9球是已经被证明是正常的，如果不能用1~8之外的球那么这种状态划分就是不可达的！

一定能够达到最优解吗 #

我们将12个球扩展到121球，那么理论上的最优解为5，即5次就能找到那个特殊的球（3^5=243>242）。

第一次划分，将242个状态划分为81-81-80：

1~40是重或者轻的，一共80个状态
41~121是重的
41~121是轻的

这是一种合理的划分，但是除非有已经被证明是正常的122~202球，否则是不可达的！

那么如果将242个状态划分为82-80-80呢？这样也达不到最优解，因为82>81=2^4

能够用计算机编码解决吗？ #

天平的一次称量可以得到3种结果，我们可以对这3种结果进行编码：0、1、2，所以称量M次就能够得到3^M种结果。这和我们之前的结论是一样的。

问题是对状态的划分并不一定是可达的！因此判断状态是否可达是编码的关键！

如果已知特殊球比正常球重需要几次称量？ #

这时一共有12种状态，但还是需要3次称量：3^2 = 9 < 12 < 27 = 3^3

如果不用天平而是使用电子秤呢？ #

第一次，将12个球平分为3堆：1~4，5~8, 9~12，并用1~4和5~8进行称量。

第二次：

如果1~4和5~8的重量不一样，那么再用1~4与9~12进行称量，此时就可以知道坏球是在1~4还是5~8中。不失一般性，可以假设坏球在1~4中。
如果1~4和5~8的重量一样，那么坏球一定在9~12中，并且得到了正常球的重量，此时状态与上边的情况相同，因为我们只考虑最坏情况，因此这种没有消耗次数的情况就不再考虑。

经过上面两步，我们已经知道了坏球在哪里，并且正常球、坏球的重量已知，那么在4个球中找到这个坏球，使用两次二分法即可。

所以一共4次。