使用天平在12个小球次品，保证找到，至少称几次？
导语
最近很久没写文章了，一是工作很忙，二封闭在家，我花了不少时间辅导娃的功课，小学二年级第五单元，有这么一道题目，说9个球里面有1个是次品，比其他球轻，使用天平最少几次可以找出那个次品。这题让我联想到了经典的一个面试问题，12个小球里找次品（不知道次品的轻重），天平最少称几次？
小学题目分析
这道小学题目：9个球里面有1个是次品，比其他球轻，使用天平最少几次可以找出那个次品？应该还是比较容易的，先说答案最少2次可以找出次品小球。首先将9个球平均分为3堆：
第一次称完后，无非三种情况：
- 天平左右平衡，那么次品在剩下的3个小球中；
- 天平的左边轻，那么次品在左边的3个小球中；
- 天平的右边轻，那么次品在右边的3个小球中；
无论哪一种情况，都把次品小球的范围缩小到了在3个小球中找，那么我们接下来再称一次，选择3个小球中的2个，放在天平的左右两端，如下所示：
这一次的结果和第一次一样去进行分类讨论：
- 天平左右平衡，那么次品就是未放上天平的那个小球；
- 天平左边轻，那么次品在就是放在天平左边的小球；
- 天平右边轻，那么次品在就是放在天平右边的小球；
OK，至此，小学生阶段的分析就此打住了，把答案写上，还算一个优秀的小学生。我追问了我孩子一句，你知道27个小球要称几次么？我孩子一下愣住了，那么更通用的情况，到底要称几次，才能把次品小球从N个球中找出来呢？比如N=100、1000、100000……
通用情况分析
其实这个通用情况也不难阐述，按上面的例子，其实每次称重，都能将范围缩小为原来的1/3，假设称了k次后，范围缩小到1个球的时候，就找到了次品小球，数学公式为：
N*(1/3)^k <= 1
变换上述公式，N <= 3^k，那么如果称2次，N <= 9, 称3次，N <= 27。
变换上述公式，k >= log3(N)，如果N=100，k >= 4.xxxx，向上取整，k=5，以此类推。
使用天平进行测量，每次在不停的消除不确定性，缩小了次品小球的范围。
面试问题分析
面试问题，12个小球里找次品（不知道次品的轻重），天平最少称几次？这比上面的问题难度大多了，但是也还是可以使用类似的方法去分析，只不过，次品小球的情况变多了，比如上面问题告诉你，次品是比较轻的，那么N个球只有N个情况，要么1号小球轻，要么2号小球轻，以此类推，而现在结果可能有2*N中，要么1号轻，要么1号重，要么2号轻，要么2号重，一次类推，原因是你并不知道次品是轻还是重。
举个例子，N = 6的情况下，可能的结果有12个，分别标识为：1L（1号轻），1H（1号重），2L（2号轻），2H（2号重），3L（3号轻），3H（3号重），4L（4号轻），4H（4号重），5L（5号轻），5H（5号重），6L（6号轻），6H（6号重）。
那么我们还是进行测量，第一次这样分：
分三种情况讨论：
- 天平左右平衡，那么次品在5、6两个小球中，剩下有4种情况5L、5H、6L、6H；
- 天平的左边轻右边重，那么次品在1、2、3、4四个小球中，但是剩下的也只有4种情况，分别是1L、2L、3H、4H；
- 天平的左边重右边轻，那么次品在1、2、3、4四个小球中，但是剩下的也只有4种情况，分别是1H、2H、3L、4L；
那么很简单，如果再测一次，结果平均看应该是4/3 = 1.333…，平均是大于1的，怎么理解呢，其实就是有可能只有1种，有可能有2种。我们继续分析，假如是第一种情况，次品在5、6两球中，我们可以这样称：
5球放左边，前面第一次称出的任何一颗正常球放右边，那么分三种情况讨论：
- 天平左右平衡，那么次品为6球，剩下有2种情况6L、6H；
- 天平的左边轻右边重，那么次品为5球，5球轻了，5L；
- 天平的左边重右边轻，那么次品为5球，5球重了，5H；
上述天平左右平衡的情况下，还得再称一次，就能得到6球是轻了还是重了。
那如果第一次称的结果不是平衡的，是第二种情况，怎么办呢，也有办法，按如下方式称重第二次，把可能重的两球分左右两边放在天平上，然后一边再放一个可能轻的球，另外一边放正常的球。
称重结果出来后，分三种情况讨论：
- 天平左右平衡，那么次品为2球，2L；
- 天平的左边轻右边重，那么次品1或者4球，1L或者4H；
- 天平的左边重右边轻，那么次品3球，3H；
只剩下当中那种情况，需要再称一次，即可找到真正的次品，就不展开论述。
第一次称重后的第三种情况，和第二种情况是对成的，所以经过两次测量，基本上把可能的结果压缩到了2次以下，再测一次，必然可以找到次品小球。
面试问题通用情况分析
根据上面例子分析，如果N个球，测量k次，能找到次品小球，不等式为：
2N * (1/3)^k <= 1
=> N <= (3^k)/2
上面仅仅算出的是上限，我们尽心更细致的分析：
第一次我们将N个球分为相等的2堆a个球，加上剩余的b个球，两堆a个球上天平称，分三种情况讨论：
- 天平左右平衡，那么次品在那堆b个球中，可能性为2b个（要么轻，要么重），那么必须满足如下不等式：
- (1/3)^(k-1) <= 1
=> b <= (3^(k-1))/2
=> b <= (3^(k-1)-1)/2 (因为3的k-1次幂为基数，b又只能为整数，所以3^(k-1)减去1，不等式必须满足)
- 天平左边重右边轻，次品可能在左边的a球中（可能性是左边a个球重），也可能在右边的a球中（可能性是左边a个球重），所以加起来的可能性是2a，那么必须满足如下不等式：
- (1/3)^(k-1) <= 1
=> a <= (3^(k-1))/2
=> a <= (3^(k-1)-1)/2 (理由同上)
- 天平左边轻右边重，这和第2个情况是对成的，直接得到不等式：
- <= (3^(k-1)-1)/2
所以，N = 2a+b <= (3^k-3)/2。所以我们得到了如下结果：
如果k=2，N <= 6;如果k=3，N <= 12;如果k=4，N <= 39;……
所以有了公式，回答面试问题就变得很简答了，12个小球要保证能找到次品小球，最少要称3次，但是称重的方案，还是非常复杂的。怎么样，是不是非常有趣呢？
结论
今天想写这篇文章，原因是，往往很多的知识，从我们小学时代就开始有了雏形，慢慢地，随着我们长大，问题会慢慢变复杂，我觉得只有多思考，多动脑，从小打好思维的基础，才能在遇到更复杂问题时，充满信心和耐心，解决更大的挑战吧，一起加油吧。
1
555