称球问题-找出球中的坏球

原作者参考：http://blog.csdn.net/pongba/article/details/2544933

问题

问题模型描述：n个小球，其中有一个是坏球。有一架天平。需要你用最少的称次数来确定哪个小球是坏的并且它到底是轻还是重。有的题目给出了坏球是轻还是重。

这个问题是一道流传已久的智力题。网络上也有很多讲解，还有泛化到N个球的情况下的严格证明。也有零星的一些地方提到从信息论的角度来看待最优解法。本来我一直认为这道题目除了试错之外没有其它高妙的思路了，只能一个个方法试，并尽量从结果中寻找信息，然后看看哪种方案最少。

思路原则

数学之美中提到了一种数学分析的等概率模型。
现在我们用天平来称球，就等同于对所有情况可能性发问，由于天平的输出结果有三种“平衡、左倾、右倾”，
这就相当于我们的问题有三个答案，即可以将所有的可能性切成三份，
记住一个原则，我们应当尽量让这三个分支概率均等，即平均切分所有的可能性为三等份。
如此一来的话一次称量就可以将答案的可能性缩减为原来的1/3，三次就能缩减为1/27。
比如12个球不知道轻重，才有24种可能性，所以理论上是完全可以3次称出来的。
接下来我们用简单的实例来实际分析问题。

已知轻重找球问题

问题：现在9个小球，其中8个质量相同，有一个坏球较轻一点，如果用天平称，至少称多少次保证能找出这个较轻一个。
这里较轻较重的分析是一致的。

可能性：现在有9个小球，并且我们知道坏球是轻的。所有一种有9中可能性。
1-，2-，3-，4-，5-，6-，7-，8-，9- （这种用-号来表示 轻）
决策选择：按照等概率模型的原则，我们应该找出一种比较方法，能够使天平的三种情况缩减的问题可能性等量缩减。
这里我们使用三分的办法，9个小球分成三份称。希望每种最后缩减可能性都为3种。

可能性分析：这里我采用图表方式分析。

这里我们至少需要两次称重可以确保找出坏球。当然碰运气，第一次就出现的不算。
原谅我没有找到一个合适的画图工具，如果有人看文章的话希望可以推荐一个。

未知轻重找球问题

问题：现在9个小球，其中8个质量相同，有一个坏球，不知道轻重，如果用天平称，至少称多少次保证能找出这个坏球。

可能性：现在有9个小球，并且我们不知道知道坏球是轻重。所有一种有18种可能性。
1-，2-，3-，4-，5-，6-，7-，8-，9- ，1+，2+，3+，4+，5+，6+，7+，8+，9+ （这种用-号来表示 轻 +来表示 重）
决策选择：按照等概率模型的原则，我们应该找出一种比较方法，能够使天平的三种情况缩减的问题可能性等量缩减。
这里我们使用三分的办法，9个小球分成三份称。希望每种最后缩减可能性都为6种。

可能性分析：这里我采用图表方式分析。

这里比较难想的问题是 中间第二次进行称重的时候该如何选择。
这里我建议先用 球多用划分轻重组合法 后用球少逆向思维借助法

划分轻重组合法： 第二次 称重先划分组数 三组 ＞情况 1+ 4- 2+5- <情况 1- 4+ 2-5+

逆向思维借助法：第二次=的情况 划分三组 每组一个球 不能推出结论
借助其他标准小球
感觉这里的解释 有些牵强 因为具体的情况总是不同的分析方式 不好统一描述
有读者有更好的分析方式，请联系我。

下面再看一题
问题：现在12个小球，有一个坏球，不知道轻重，如果用天平称，至少称多少次保证能找出这个坏球。

可能性：现在有12个小球，并且我们不值知道坏球是轻重。所有一种有24种可能性。
1-，2-，3-，4-，5-，6-，7-，8-，9- ，10-，11-，12- ，1+，2+，3+，4+，5+，6+，7+，8+，9+ ，10+，11+，12+ （这种用-号来表示 轻 +来表示 重）
可能性分析：这里我采用图表方式分析。
图片来源：http://www.inference.org.uk/mackay/itprnn/ps/65.86.pdf