爱华网今天下午和3个同事去爬山，下山时1同事说很无聊，于是我“很有聊”地出了一道高中以来我用于测试自己的思维清晰度的保留题目：心算789乘以987的答案。以前都是用789*(1000-13)算，今天首次用(800-11)*(1000-13)，结果我很没面子地算成了110000-21257，而正确答案是800000-21257……汗。接着该同事给我出了一道题——据说是微软公司的面试题：
今有12个外观相同的球，其中11个球一样重，剩下那个球重量和其他11个不同。用1个天平称3次，找出那个重量异常的球。
我花了大概路上的20分钟，想出了3个答案，都被出题的同事一一否决，他还试图给我一个提示：第一次选多少球，被我谢绝了（答案当然要完全自己想出来才有成就感嘛~）。回到公司后又想了45分钟左右，终于在晚饭18:00前成功地答出了。
答案是很简单啦，到网上随便一搜都有，虽然可能稍有不同。
下面用“重？”表示“过重或正常的球”，“轻？”表示“过轻或正常的球”，“正常”表示“正常的球”。
(1)选出8个球，一边4个称。
(1_a)一样重：异常球在剩下4个里。从中选出2个，一边一个：如果一样重，那么异常球在剩下两个里；如果不一样重，那么异常球在这两个里。即，范围缩小到两个球。随便选1个和剩下那10个“正常”中的1个比较即可判断异常球。
(1_b)不一样重。此时情况是3组球：{重？，重？，重？，重？}是比较重的那一组，{轻？，轻？，轻？，轻？}是比较轻的那一组，{正常，正常，正常，正常}是没有称过的那一组。
(1_b_2){重？，重？，轻？}和{重？，重？，正常？}称量，剩下的是{轻，轻，轻} 和{正常，正常，正常}。
(1_b_2_a){重？，重？，轻？} 比较轻。这时，可能异常球是那个“轻？”，也可能是{重？，重？，正常？}组中两个“重？”中的1个。即，范围缩小到{重？，重？，轻？} 里。
(1_b_2_a_3)把一个“重？”和一个“轻”放在一组，另一组放两个“正常”。如果前者重，那么该组中“重？”就是异常重的那个；如果前者轻，那么该组中“轻？”就是异常轻的那个；如果一样重，那么剩下没称的那个“重？”就是异常重的那个。
(1_b_2_b){重？，重？，轻？} 比较重。这时异常球是该组中两个“重？”中的1个。即，范围缩小到{重？，重？} 里。
(1_b_2_b_3)随便选一个和“正常”比较，如果一样重，剩下的那个“重？”就是异常重的球；如果“重？”比较重，那么它就是异常重的球。
题目是解出来了，但光这样还不够过瘾。在思考过程中，我习惯性地找出思考方向，而不是像没头苍蝇一样往四处乱想。以下是我的思考结果。
1.本题本质上是一个搜索问题，从一大堆结果中找出一个目标的问题。这类问题的本质就是每次对样本空间测试都会得到某些信息，利用这些信息来设计之后的测试方法，最终获得终极信息——答案。因此，要让测试次数最少，就要让每次测试获得的信息(1)尽量多；(2)被充分利用。
2.关于“获取尽量多的信息”,一个很容易理解的看法是,那些可能有“左重右轻”、“左轻右重”和“一样重”3种可能结果的称量方式，比只有两种或一种可能的结果的称量方式更有助于获得较多的信息。
3.关于“信息被充分利用”，要点是判断出获得了那些信息，再自问自己的测试是否在任何结果中都充分利用了信息。信息包括“异常球在这x个球中”和“异常球较重/轻”。
本题的一个陷阱是，题目并没要求答题者判断异常球和正常球相比是更重还是更轻,这让答题者觉得这是个1/12的搜索问题。然而事实上，为了信息最大化，无论怎么称量都不可能出现“知道异常球所在却不知道该球比正常球重还是轻”。这是由于开始时球数是12是偶数（详情待证）。
从信息和熵的角度来看搜索问题，可以这么理解：答题者每次称量都从结果中获得一定的信息，这些信息累加并去掉重复（多余）信息，如果结果大于或等于问题的熵，那就能得到答案。
为什么3次称量的每一次都要保证可能的结果有3个?
由于异常球的位置是个1/12的问题，需要的信息是-ln(1/12)=ln(12)，异常球较重还是较轻是个1/2的问题，需要的信息是-ln(1/2)=ln(2)，本问题实际上需要的信息是ln(12)+ln(2)=ln(12*2)=ln(24)。
每次称量，即使没有任何信息损失，对于可能结果有3个的称法，每次称量获得的信息熵是ln(3)，3次则是ln(3)+ln(3)+ln(3)-f=ln(27)-f。当然，如果设计不当，会有些多余信息f。如果f足够小，使得ln(27)-f大于问题的熵ln(24)，那就能找到答案。
如果3次称量中有任何一次只获得ln(2)的信息（即只有两种可能的结果），那3次称量的最大获得信息量是ln(3*3*2)=ln(18)，即使信息没有多余，也无法得到答案。
为什么网上的答案的第一步都是一样的：4，4，4分组?
如果第一次称量时采用3，3，6的分组方式，3个3个称，那如果两边相等，剩下6个球就陷入1/6*1/2=1/12的搜索问题中了。而余下的两次称量最多只能提供ln(9)的信息，对于ln(12)的问题无能为力。
当然，上述的分析是很粗糙的，因为称量的方式获得的信息还受到天平两侧放多少球的影响。也没有对多余信息量f的计算以及为什么“知道异常球所在却不知道该球比正常球重还是轻的情况对于总球数12称3次的问题不可能出现”做出说明。这些留待以后我再慢慢思考……貌似很难很难，靠初等数学分析是不够的。
