天平称球问题
前段时间在朋友日志里看到这个问题：12个小球，有一个质量和其他11个不一样，一架天平，没有砝码，称3次找出这个不一样的小球。下面是我今天上午想出的一个解法，看下去之前大家也可以自己先想想。
================= 疲倦的分割线 ==================
将正常小球记作N，不正常的记作A。
引理1：已知一个小球是N，A在两个小球之中，只需要一次就可以称出A。方法如下：
两个待选小球中任取一个和N比较，若平衡，则剩下那个是A，否则取出那个是A。
那么以下方法可以3步称出小球：
1. 取两组R, L 各四个小球称。不失一般性，标记为 R{1,2,3,4}; L{5,6,7,8};
若R和L一样，记作R=L，则剩下的集合S{9,10,11,12}中含有A，R，L构成标准组；取{9,10}与{1,2}比较，若相等，则A属于{11,12}，否则属于{9,10}，由引理，一步可以称出。
若R != L，假设 R>L (R比L重)。**交换{1, 2, 3} <–> {5, 6, 7}，若平衡不变，即仍有R>L，则A属于{4,8} (问题一步可以解决)。否则A属于{1,2,3,5,6,7}。其实这里故意绕了一下，这样的话是解不出来的，我们其实可以从这一步利用S = {9，10,11,12}是标准组得出更多的结论(知道A属于{1,2,3}或者{5,6,7}并且A是较重或者较轻)。
从**处开始：交换{1,2,3} <–> {5, 6, 7}，并用{9,10,11}代替{1,2,3}，此时R’={5,6,7,4}; L’={9,10,11,8};S’={1,2,3,12}
若仍有R’>L’，则A属于{4,8} (问题一步可以解决)。
若R’ = L’ 则A属于替换下天平的三个球，即{1,2,3}并且A较重（因为A来自于R)。{5,6,7}中任选两个比较即可。
若R’ < L’ 则A属于{5,6,7}且A较轻（因为A来自于L）。{1,2,3}中任选两个比较即可。
技巧的关键就是，通过交换天平两边的部分小球来进一步缩小A的范围，同时用标准组的球进行替换，设立比较的标准可以制造更多的不同结果（可能出现的结果越多，对于根据结果分类帮助更大）。
不过我不知道解法是否唯一。
大胆的进一步推测，因为第一步称只能产生2个结果，第二步通过轮换产生3个结果，第二步之后知道轻重，用2分法就可以比较快的得到答案。所以可以猜测，当总的小球数介于 [ 2*3*2^n, 2*3*2^(n+1) ) 时，用 (n+2)步就可以称出。不过我还没想到好的证明方法。
本文用菊子曰发布
