本文均以“：”表示天平，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疑似重球，3^k标准球 ： 3^k疑似重球，1/2 *3^k-1/2疑似轻球。
                                   若第一称为原先重的那边重（即左重），那么坏球要么在那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)


特别鸣谢：小镇之月光。前辈肯为了鉴定我的文章而出山，我心里也是暗自感动的！特此引进前辈的文章链接以示敬意《有关N个球称t次挑出异常球的通解通法》http://tieba.baidu.com/f?kz=417490487   
月光出山：
小镇之月光
17位粉丝
75楼
LZ的解法是对的，不过和我解的不是同一题。因为13个球，没有标准球，则可能无法确定坏球的轻重。
简而言之，LZ的解法，是用于判断坏球
我的解法，是判断坏球，并指出轻重
不是同一题。不过LZ的想法确实很不错~就是排版有一点。。呵呵，无伤大雅。
2010-7-11 15:05 回复  
小镇之月光
17位粉丝
78楼
简单说明下LZ的解法
（所有球都用数字编号）
前提：3^n个球里有1个坏球，已知轻重，则通过n次可以称出
比如，3个球1次，9个球2次，这个就不赘述了。
推论：
第一题：
4个球称2次，不知轻重
No.1：
1 —— 2
闲置：3、4
如果不平衡，则一边轻，一边重，3、4好球，接下来1 —— 3，得到结果
如果平衡，则1、2好球，接着1 —— 3，如果不平衡，则3坏球，否则4坏球，此时无法判断4的轻重
第二题：
13个球称3次，不知轻重
No.1：
1、2、3、4 —— 5、6、7、8
闲置：9、10、11、12、13
如果不平衡，则9、10、11、12、13好球
此时，左边取走3个（1、2、3），4和8交换，放入3个好球
如果轻重平衡，则坏球在取走的1、2、3中，如果依然不平衡，同方向，则坏球在5、6、7中，如果平衡交换，则坏球在交换的4、8中，再靠1次称重就能解决了。
如果第一步平衡，则坏球在9、10、11、12、13，5个球中。分为3、1、1， 3个好球和9、10、11对称，如果不平衡则在9、10、11中，如果平衡则1个好球和12对称，得出结论。
推广到40个球，同样的道理
No.1 1-13——14-26
闲置：27-40,14个球
如果不平衡，则左边取走3^2=9个球，放入9个好球，同时剩余4个和右边交换
如果平衡，则取走的有坏球
如果依然不平衡，同向，则不动的9个有坏球
如果平衡交换，则换的8个有坏球
无论如何，再过2次，就能找出坏球
如果第一步平衡，则将14个球分为9、3、1、1， 接下来的3步如法炮制上面的步骤~
就是这样。
2010-7-11 15:29 回复  


回复：11楼

正解

小野妹妹随便插楼是不对的哦

说明：月光解决的问题是找出异常球并要分辨出坏球轻重。我解决的问题是找出异常球但不要求分辨坏球轻重

回复：14楼
恩，结果2楼不见了

这升级速度。。。。。。吓我一跳~！~~~~~~~~~~~~~~~~~~~·

没了

我是看都没看明白、、、、好难