用天平在m个球中找坏球

问题:有m个小球，其中有1个与其它（m-1）个球的重量不一样。请用无码天平用尽量少的次数找出这坏球并判定它比好球偏轻还是偏重。
把问题改为下面提法：
有m个小球，其中有1个与其它（m-1）个球的重量不一样。用无码天平称n次最多能从多少个球中找出坏球并判定它比好球偏轻还是偏重。
一，定理
1，有m个小球，其中有1个和其它（m-1）个球的重量不一样。用天平称n次，能“找出坏球并判定它比好球偏轻还是偏重”m的最大值是(3^n-3)/2。就是：0、3、12、39、120、363、1092、……
2，三个引理（待续）

2，三个引理
引理1
如果已知坏球比好球偏轻或偏重，那么，称n次可“找出这坏球”的最大值是3^n。也就是：m=3、9、27、81、243、729、2187、……
这个引理很容易证明，在此略去。
引理2
如果已知一堆球中有1个坏球但不知比好球偏轻还是偏重，且另有不少于3^（n-1）个的好球，那么，称n次可“找出这坏球并判定它比好球偏轻还是偏重”的最大值是（3^n-1）/2。也就是：1、4、13、40、121、364、1093、……
m=1时，也就是说唯一的1个坏球。这时把它与好球称，即可确定这1个坏球的轻重；
m=4时，第一次，在这4个球中，任取3个与3个好球称。若平衡，则剩下的那个球与好球称即可；若不平衡，则必知坏球轻重，根据引理1知，再称1次即可。总共2次，即n=2；
m=13时，第一次，在这13个球中，任取9个与9个好球称。若平衡，则坏球必在剩下的那4个球中，化为m=4的情况，还须2次；若不平衡，则必知坏球轻重，根据引理1知，再称2次即可，共2次。总共3次，即n=3；
m=40时，第一次，在这40个球中，任取27个与27个好球称，下面剩13个。化为引理1与m=13的情况，都再称3次，总共4次，即n=4。
不难看出，m=121时，因为121=81+40，所以问题化为引理1与m=40的情况，都再称4次，总共5次，即n=5。
m=364=243+120，可以化为引理1与m=121的情况，即n=6；
m=1093=729+364，可以化为引理1与m=364的情况,即 n=7。
以上不厌其烦地举例，是为了让大家理解下面两点：
一是发现了一系列“递归”式子：
1+3=4、4+9=13、13+27=40、40+81=121、121+243=364、364+729=1093。
二是找到了证明的“递归”叙述方式。也就是，只要说明了第一次称，就可以递归到“小一级”的情况，大大简化了叙述过程而且说得明白、容易读懂。
引理3（待续）

2，三个引理(续）
引理3 如果已知两堆球中有1个坏球，不知比好球偏轻还是偏重，但知道：“如果坏球在其中某一堆的话必是偏轻（疑轻）、坏球在其中另一堆的话必是偏重”（疑重），而且另有不少于3^（n-1）个的好球，那么，称n次可“找出这坏球并判定它比好球偏轻还是偏重”的最大值是（3^n-1）/2（指每一堆）。也就是：1、4、13、40、121、364、1093、……。
具体看看：
m=2（=2×1）时，显然，这时任取其一与好球比较即可，即n=1;
m=8（=2×4）时，按下述方法分组：左“3疑重 1疑轻”、右“3好 1疑重”，天平下面“3疑轻 1好”。称2次（即n=2）如下 ：
（1）如果第一次“左、右平”，那么，第二次，天平下面中的“3疑轻”转化为前述的引理1；
（2）如果第一次“左重、右轻”，那么，第二次，左“3疑重”也转化为前述引理1；
（3）如果第一次“左轻、右重”，那么，第二次，在左“1疑轻”或右“1疑重”中，可任取其一与好球称即可。
m=26（=2×13）时，按下述方法分组：左“9疑重 4疑轻”、右“9好 4疑重”，天平下面“9疑轻 4好”。
第一次称，有以下3种情况：
（1）如果“左、右平”，那么，天平下面中的“9疑轻”转化为引理1，再称2次；
（2）如果“左重、右轻”，那么，左“9疑重”也转化为引理1，再称2次；
（3）如果“左轻、右重”，那么，左“4疑轻”及右“4疑重”。这时转化前述的引理3中m=4，再称2次。
总之，不管哪种情况，都是再称2次，共3次，即n=3。
m=80（=2×40）时，按下述方法分组：左“27疑重 13疑轻”、右“27疑好 13疑重”，天平下面“27疑轻 13好”。
第一次称，有以下3种情况：“左、右平”、“左重、右轻”、“左轻、右重”。如同m=13那样，都可以再称3次，共4次，即n=4。不再细说了，
121、364、1093、……通通类似,不必细说了。

关键在于，如同引理2时说的，大家要注意理解下面两点：
一，“递归”式子：
1+3=4、4+9=13、13+27=40、40+81=121、121+243=364、364+729=1093。
二，“递归”叙述方式。也就是，只要说明了第一次称，就可以递归到“小一级”的情况，大大简化了叙述过程而且说得明白、容易读懂。

前面说了如下内容：
一，定理
1，定理内容
2，三个引理
下面继续，看看怎么用三个引理来证明定理。

3，定理的证明
有了上述3个引理，就可以很容易说明如下定理：有m个小球，其中有1个和其它（m-1）个球的重量不一样。用天平称n次，能“找出坏球并判定它比好球偏轻还是偏重”m的最大值是(3^n-3)/2。就是：0、3、12、39、120、363、1092、……
具体看看：
容易看出：称1次，是不可能找出坏球的，即n=1时，m=0；称2次时，只能从3个球里找出坏球并且判定轻重，即n=2时，m=3。
m=12时，
第一次：把12个球平均分成3组，天平的“左”、“右”、“下”都是4个。称后，以下两种情况，都再称2次即可，共3次，即n=3。
第二、三次：
第一种情况，“左、右平”，那么，坏球在“下面”4个里，转化为前述的引理2中的m=4时的情况；
第二种情况，“左、右不平”，那么，转化为前述的引理3中的m=8（=2×4）时的情况。
m=39时，
第一次：把39个球平均分成3组，天平的“左”、“右”、“下”都是13个。称后，以下两种情况，都再称3次即可，共4次，即n=4：
第二、三、四次：
第一种情况，“左、右平”，那么，坏球在“下面”13个里，转化为前述的引理2中的m=13时的情况；
第二种情况，“左、右不平”，那么，转化为前述的引理3中的m=26（=2×13）时的情况。
如此等等，m=120、363、1092、……时，都可以“一下子”转化为“小一级”的情况，不再赘述。
说明：
一，注重理解上述的“递归”叙述方式。也就是，只要说明了第一次称，就可以递归到“小一级”的情况。
二，由以上实例，我们具体地理解了定理内容及叙述过程。若要严格证明，可用“数学归纳法”。

在“一，定理”中，对有关“最大值”的情况做了相当仔细的说明。直观、通俗、易懂、实用。实际上也可以说是作了证明（用“数学归纳法”，只是没具体写出严格的证明过程）。
为了进一步理解、掌握“找坏球”这个问题的解决方法的基本思路、递归思想、实际操作的一些细节问题，下面对一些典型的m值进行详细的解说。
二，解说n=4
n=4 适用的m为13到39。
为了读起来方便，下面把3个引理在n=2、3时的具体内容重说一下。
引理1：如果已知坏球比好球偏轻或偏重（简称“已知轻重”），那么，称量2次可“找出这坏球”的m为3到9，称量3次可“找出这坏球”的m为10到27；
引理2：如果已知一堆球中有1个坏球但不知比好球偏轻还是偏重（简称“不知轻重”），且另有足够多的好球，那么，称量2次可“找出这坏球并判定它轻重”的m为3和4；称量3次可找出坏球的m为5到13；
引理3：如果已知两堆球中有1个坏球，不知轻重，但知道：“如果坏球在其中某一堆的话必是偏轻（疑轻）、坏球在其中另一堆的话必是偏重”（疑重），而且另有足够多的好球，那么，称量2次可“找出这坏球并判定它轻重”的m为3和4；称量3次可找出坏球的m为5到13（都是指每一堆）。
下面对n=4时的m的各个取值做分析。
1，m=13到29时，总可以：第一次尽量三等分后进行第一次称量，然后继续，最多4次解决问题。具体点说就是：
（1）m=3k时，即m=15、18、……、27，分组方法是：“左”、“右”、“下”都是k（=5到9）,称量2次后，必定得到“知轻重”的k（=5到9）个球。由引理1知，再称2次即可，总共4次；
（2）m=3k+1时，即m=13、16、……、25，分组方法是：“左”、“右”都是k（=4到8）,“下”是k+1（=5到9）。第一次称量后如果平衡，则坏球在“下”k+1（=5到9）中，由引理2知，再称3次即可，总共4次；而第一次称量后如果不平衡，则坏球在“左”、“右”都是k（=4到8）中，由引理3知，最多再称3次即可，总共最多4次；
（3）m=3k+2时，即m=14、17、……、26，分组方法、第一次称量后平衡或不平衡后的分析，与刚说完的“（2）m=3k+1时”类似，在此不再赘述。
2，m=30、31时（待续）

8楼说了：
二，解说n=4
n=4 适用的m为13到39。
下面对n=4时的m的各个取值做分析。
1，m=13到29时，
接着看：
2，m=30、31时
（1）m=30时，如果三等分，即“左”、“右”、“下”都是10，那么，称2次后，必定得到“知轻重”的10个球。别看这10只比9多1，由引理1知，要称3次才可，总共5次，不行。可改用别的方法。
第一种方法：第一次可以如下分组：“左”、“右”都是9,“下”12。如果第一次称量后平衡，那么，由引理2知，“下”12个再称3次即可，总共4次；如果第一次称量后不平衡，那么，由引理3知，也再称3次即可，总共4次；
第二种方法，第一次三等分，即“左”、“右”、“下”都是10。如果第一次称量后平衡，那么，由引理2知，“下”10个再称3次即可，总共4次；如果第一次称量后不平衡，那么，由引理3知，也再称3次即可，总共4次。
注意：第二种方法中,如果第一次称量后不平衡时，第二次就要采用“混合分组法”了。这个是难点，可以稍具体说说：不妨设“左重右轻”。按下述方法分组：“左”9疑重1疑轻、“右”9好1疑重，“下”9疑轻1好。称第二次如下3种可能 ：
①如果“左、右平”，那么，“下”的“9疑轻”转化为前述的引理1再称2次，共4次；
②如果“左重、右轻”，那么，左“9疑重”也转化为前述引理1再称2次，共4次，；
③如果“左轻、右重”，那么，在“左”1疑轻或“右”1疑重中，可任取其一与好球称即可，共3次。
（2）m=31时，与m=30时类似，不再赘述。

3，m=32到39时，待续。

前面说了：
二，解说n=4
n=4 适用的m为13到39。下面对n=4时的m的各个取值做分析。
1，m=13到29时，
2，m=30、31时
接着看：
3，m=32到39时，总可以：第一次“尽量三等分”后进行第一次称量，然后根据平衡与否，采取不同方法。
（1）m=32时
第一次可以如下分组：“左”、“右”都是10、“下”12。称后，以下两种情况，都再称3次即可，总共4次。
第二、三、四次：
第一种情况，“左、右平衡”，那么，坏球在“下面”12个里，根据引理2（最大值13）再称3次即可，总共4次。
第二种情况，“左、右不平衡”，那么，坏球在“左”10或“右”10里，根据引理3（最大值13），即用到“混合分组”法，也是再称3次即可，总共4次。
（2）m=34到37以及m=39时，类似。不再赘述；
（3）m=38时，基本上一样，也是“尽量三等分”、也要用到“混合分组”。只是第一次分组不能是“左”、“右”都是12、“下”14。这是因为14=9+5，这里的5大于4，这样，在应用引理2、引理3时，还需要3次，总共5次，不符合要求。那么，第一次分组可以：“左”、“右”都是13、“下”12，这样就可以恰当应用引理2、引理3了。
以上，对n=4的m值13到39逐个说了。麻雀虽小，五脏俱全。只要真正理解、掌握了它，那么，对更大的n、更大的m的 “找坏球”问题就不难解决了。
下面将要对“n=4、m=13到39”这麻雀归纳总结出一些规律性的东西，以指导一般情况的解决。待续。

此前说了：
一，定理
1，有m个小球，其中有1个和其它（m-1）个球的重量不一样。用天平称n次，能“找出坏球并判定它比好球偏轻还是偏重”m的最大值是(3^n-3)/2。就是：0、3、12、39、120、363、1092、……
2，三个引理
二，解说n=4
下面继续：
三，几点说明
1，关于“递归”
从字面意思来看，递——是传递，归——是回归。一种计算过程，如果其中每一步都要用到前一步或前几步的结果，就称为递归的。也就是将问题传递、回归为同类的子问题而解决问题的方法。
递归是一种简化问题的思维方式，也是一种简化问题的叙述方式。
具体到我们现在的“找坏球”问题，也就是：
（1）“递归”叙述方式
只要正确地分组后进行了第一次称量，或者有时候继续正确地分组后进行了第二次称，就可以递归到“小一级”的情况或递归到“小两级”的情况后，就直接确定解决了问题，不必赘述了。
这样，大大简化了叙述过程，而且说得简捷、明白，容易读懂。
（2）“递归”数据组合
1+3=4、4+9=13、13+27=40、40+81=121、121+243=364、364+729=1093。
这些是进行“正确分组”的依据。
2，关于“另有好球”问题
（1）第一次称量后，必出现足够多的好球，供后面称量时使用；
（2）有了足够的好球，就为选择“疑轻”球或“疑重”球提供了完善的条件。
3，关于“轻重”问题
（1）所谓“轻重”，是指“坏球比好球偏轻或偏重”。
（2）所谓“已知轻重”，是指“已知坏球比好球偏轻或偏重”。
（3）所谓“确定轻重”，是指“确定坏球比好球偏轻或偏重”。在我们的问题中，通常需要经过2次以上称量确定。
（4）所谓“疑轻”、“疑重”：虽然不知坏球在哪一堆里，但如果在“疑轻”那一堆里的话，坏球就可判定“偏轻”，如果在“疑重”那一堆里的话，坏球就可判定“偏重”。在我们的问题中，通常是在天平称量不平衡后，就分别称这两堆球为“疑轻”球或“疑重”球。

4，待续

此前说了：
一，定理
二，解说n=4
三，几点说明
1，关于“递归”
2，关于“另有好球”问题
3，关于“轻重”问题
下面继续：
4，关于“分组”
我们已经知道，称n次可找出坏球的球数m，都有一个范围。比如，称4次可找出坏球的球数范围是13到39。对于给定的m，一开始怎么分组，有不同的方法可用。
我的方法是：把13到39分成三段：13到27；28到31；32到39。在这三段里，选择不同的分组方法。
（1）在13到27时，用“尽量三等分法”，比如m=25：“左”8、“右”8、“下”9；
（2）在28到31时，用“3^n分法”，比如m=30：“左”、“右”都是3²，“下”13。
（3）在32到39时，用“尽量三等分法”，比如m=35：“左”11、“右”11、“下”13。
注意：“（2）在28到31时”中的“31"，它=27+（9-1）/2;

上述选择分组的“三段法”，可以用于任意的情况。这样，有了固定的模式，就省心了。
再看一个例子：称5次的情况，可找出坏球的球数范围是40到120。分为如下三段：
40到81；82到94；95到120。
注意：“82到94”中的“94”，它=81+（27-1）/2 。对照31=27+（9-1）/2。看明白了31和94这2个“段点”的来历了吗？
此外，要注意的是，第三段的那些m值，第一次称量后如果不平衡，要用到“混合分组”法，然后进行第二次称量。

“分组”问题，是解决“找坏球”问题的关键所在、是难点。要真正理解、掌握“递归”相关内容。
四，待续

大佬

此前说了：
一，定理
二，解说n=4
三，几点说明
下面继续：
理解了以上内容后，我们就可以对任意给定的m值，对下面问题：“有m个小球，其中有1个与其它（m-1）个球的重量不一样。用无码天平用尽量少的次数找出这坏球并判定它比好球偏轻还是偏重。”进行具体操作了。
为了运用方便，我把以上有关数据制成下表供查用.
四，数据

1，数据表

此前说了：
一，定理
二，解说n=4
三，几点说明
四，数据
下面继续：

五，操作
以上对“找坏球”的一般情况作了极为详尽地探究。关键点是3个引理，要理解其基本思路、掌握好递归思想、正确运用递归数据、说好递归过程。

具体操作过程是：分组、称量，再分组、再称量，……，很快地就把m值减少，直至最后称1次找出。可见，怎么分组是关键。再一个问题是怎么叙述让读者容易读懂。
实际上，操作过程的各次的分组可以有多种方法，整个叙述过程也有不同，可各取其便。
我下面要说的，是一种固定模式，自己清楚那是当然的，而且我想像，读者也容易读懂（当然是在基本上掌握了我在前面介绍的“递归”思想及相关数据）。
具体步骤简述：
第一次：尽量三等分、然后称量；
第二次：
（1）如果第一次平衡，那么，可在“下”取出3^n个与好球进行第二次称量，不管平衡与否，都可以递归到“小2级”的情况，继续进行；
（2）如果第一次不平衡，那么，可能同（1）那样进行，也可能要“混合分组”后进行第二次称量（哪种可能视m值而定），都可以递归到“小2级”的情况，
余下次数：按“递归”思想去叙述即可。
下次将举例说明（待发）

下面看几个例子。
为了阅读方便，把三个引理重述一下：
引理1
如果已知坏球比好球偏轻或偏重，那么，称n次可“找出这坏球”的最大值是3^n。也就是：m=3、9、27、81、243、729、2187、……
引理2
如果已知一堆球中有1个坏球但不知比好球偏轻还是偏重，且另有不少于3^（n-1）个的好球，那么，称n次可“找出这坏球并判定它比好球偏轻还是偏重”的最大值是（3^n-1）/2。也就是：1、4、13、40、121、364、1093、……
引理3
如果已知两堆球中有1个坏球，不知比好球偏轻还是偏重，但知道：“如果坏球在其中某一堆的话必是偏轻（疑轻）、坏球在其中另一堆的话必是偏重”（疑重），而且另有不少于3^（n-1）个的好球，那么，称n次可“找出这坏球并判定它比好球偏轻还是偏重”的最大值是（3^n-1）/2（指每一堆）。也就是：1、4、13、40、121、364、1093、……。
例1，m=80
解：
第一次：“左”26、“右”26、“下”28，称量之。
第二次、……：
（1）如果第一次平衡，那么，可在“下”取出27个与好球进行第二次称量，
①如果平衡，那么坏球就是“下”里剩下的那1个，再称1次可判定它轻重，共3次；
②如果不平衡，就确定了知道轻重的27个球，由引理1知，用3次可找出坏球，共5次；
（2）如果第一次不平衡，那么，可在“下”取出27个与好球进行第二次称量，必可以确定知道轻重的27个球，由引理1知，再称3次可找出坏球，共5次；
附注：40≤m≤81时，都可以类似进行。只需要用引理1。
例2，m=90 待续。