【经典智力题衍生思考】十二乒乓球衍生问题：称球问题严密数学分析
凉衣。 2016-01-20 13:37:23
作者：才zZz眠
本文对经典的称球问题进行了通解性的探究。当你看完并理解解了这篇文章，那么称球问题对你来说已经不是什么问题了。本文采取的是以归纳法的方法，证明了n次称量在不同条件下能解决的球个数。称的方法也就是证明的过程。
可直接跳过看结论
本文均以“：”表示天平，A1,A2,A3,……An表示球
-------------------------------------------------------------------------------
求证一：在知坏球轻重情况下，n次可以从3^n个球中找出坏球
证明一：
当n=1时，即知轻重3球找1次。很简单，不妨设坏球是重球。A1:A2三种情况:左重，则A1坏。左轻，则A2坏。等重，则A3坏。
假设当n=k时，k次可以从3^k个球中找出坏球
则当n=k+1时，共3^(k+1)个球，平均分三份，各3^k个球。
第一称。左右均放3^k个球，可找出是哪一份3^k个球中有问题球。接下来还有k次机会，完全可以从那3^k个球中找出坏球。
由数学归纳法可得
结论一：在知坏球轻重情况下，n次可以从3^n个球中找出坏球
由结论一，可作如下推理：
在有足够多标准球的情况下，不知坏球轻重，按下面的方法称
第一称。拿3^(n-1)个球与3^(n-1)个标准球比。
如果不等重，可知坏球轻重，还有n-1次机会，则可以从这3^(n-1)个球中找出坏球。（根据结论一）
若第一称等重，则还有n-1次机会，
第二称。拿另外3^(n-2)个球与3^(n-2)个标准球比。
如果不等重，可知坏球轻重，还有n-2次机会，则可以从这3^(n-2)个球中找出坏球。
若第二称等重，则还有n-2次机会，
第三称。另外拿3^(n-3)个球与3^(n-3)个标准球比
……
……
第n-1称，另外拿3个球与3个标准球比。
若不等重，可知坏球轻重，还有1次机会，则可以从这3个球中找出坏球。
若第n-1称等重，则还有1次机会，
第n称。另外拿1个球与1个标准球比，
若不等重则为坏球。
若第n称等重，则已无机会，若此时还有1球未称，则此球为坏球。
由上可得，n次可以从这么多的球中找出坏球：3^(n-1)+3^(n-2)+3^(n-3)+……+3+1+1= 1/2 *3^n + 1/2
结论二：在有足够多标准球队情况下，不知坏球轻重，n次机会可以从1/2 *3^n + 1/2个球中找出坏球（足够多指有3^(n-1)个）
看到这，你都看明白了的话，当你看到别人在炫耀三次能称出十三个时，你可以很自豪地对他说：十三个算什么，给我九个标准球，我三次可以从十四个球中找出坏球。哈哈。
有了以上两个结论作铺垫，现在开始切入正题：不知坏球轻重，无辅助标准球！
众所周知，二次可以称4球，三次可以称13球，四次可以称40球。
首先观察数列a(2)=4 a(3)=13 a(4)=40
可以看出后一项是前一项的三倍加一，即得递推公式a(n)=3a(n-1)+1
由数学方法解得通项公式a(n)=1/2 * 3^n - 1/2 (n≥2)
那么，做如下猜想，是否n次称量可以从1/2 * 3^n - 1/2个球中找出坏球？
求证三：不知坏球轻重，无额外标准球，称n次可以从1/2 * 3^n - 1/2个球中找出坏球。(n≥2)
证明三：
将1/2 * 3^n - 1/2个球分成1/2 * 3^（n-1） - 1/2，1/2 * 3^（n-1） - 1/2，1/2 * 3^（n-1）+ 1/2三分。
第一称。左右两边均放1/2 * 3^（n-1） - 1/2
若等重，则坏球在剩下的1/2 * 3^（n-1） + 1/2个球中，此时还有n-1次机会，又得到了足够多的标准球，由结论二可得，此时可以找出坏球，不作赘述。
若第一称不等重，不妨设左边重。此时还有n-1次机会，且知坏球要么在左边那1/2 * 3^（n-1） - 1/2个球中，是个重球；要么在右边那1/2 * 3^（n-1） - 1/2球中，是个轻球。而且还有足够多标准球。
只要证明在这种条件下可以找出坏球，证明三即可得证。
求证三-2：共有3^n -1 个球，已知坏球要么在其中1/2 * 3^n - 1/2个球中是个重球；要么在剩下的1/2 * 3^n - 1/2个球中是个轻球。n次机会可找出坏球。(n≥2)
证明三-2：像这种一层套一层的证明，依然采用归纳法。
当n=2时，即为共有8个球，坏球要么在其中4个球中是个重球，要么在剩下的4个球中是个轻球。有2次机会。
第一称。将重的那边放入3个标准球，取3个疑似重球放入轻的那边，取走3个疑似轻球。
相信许多朋友很快就看出这是13选1解法中的一部分，因此第二称不再赘述。
所以当n=2时，命题成立
假设当n=k时命题成立
则当n=k+1时，共有3^(k+1)-1个球。坏球要么在其中1/2 *3(k+1)-1/2个球中是个重球，要么在剩下1/2 *3(k+1)-1/2个球中是个轻球。
第一称。 将重的那边放入3^k个标准球，取3^k个疑似重球放入轻的那边，取走3^k个疑似轻球。
若第一称为原先重的那边重（即左重），那么坏球要么在那1/2 *3^k-1/2个疑似重球中是个重球，要么在那1/2 *3^k-1/2个疑似轻球中是个轻球。还有k次机会。这本质上就是当n=k时的情形，因此可解。
若第一称为原先重的那边轻（即左轻），那么坏球一定在被移动的那个3^k个疑似重球中，还有k次机会。由结论一知，可解。
若第一称为等重。那么坏球一定在被移动的那3^k个疑似轻球中，还有k次机会。由结论一知，可解。
当n=k+1时，命题也成立。
由数学归纳法，得
结论三-2：共有3^n -1 个球，已知坏球要么在其中1/2 * 3^n - 1/2个球中是个重球；要么在剩下的1/2 * 3^n - 1/2个球中是个轻球。n次机会可找出坏球。(n≥2)
因此，证明三中所述的n-1次机会的那个条件下是可解的。由此，证明三得证。
结论三：不知坏球轻重，无额外标准球，称n次可以从1/2 * 3^n - 1/2个球中找出坏球。(n≥2)
哦也！全部证明完毕。语文表达能力有限，不知道大家都看懂了没。数学思想上是很严谨滴，嘿嘿。
抛开复杂的证明过程，摘出重要的三个结论，希望大家有用。
结论一：在知坏球轻重情况下，n次可以从3^n个球中找出坏球
结论二：在有足够多标准球队情况下，不知坏球轻重，n次机会可以从1/2 *3^n + 1/2个球中找出坏球（足够多指有3^(n-1)个）
结论三：不知坏球轻重，无额外标准球，称n次可以从1/2 * 3^n - 1/2个球中找出坏球。(n≥2)
