用数学归纳法证明整除（分球）

1963年北京数学竞赛试题

这是高中数学竞赛试题，题目的意思是：球的个数可以是2、4、8、16、32、64……，（还有一个特别的是1，本来就是一堆，我们不考虑了）分的堆数也可以是任意的。操作的方式是，从球数多的堆往往球数少的堆移动，移动的个数与球数少的堆一样多。比如有一堆是5个，有一堆是3个，我们就可以从5个中拿出3个放到3个的堆中，这样，原来的5和3就变成了2和8。特别的，如果两堆一样多，就可以合并，比如4和4，我们可直接合并成8。

要我们证明的是：无论球数是多少（当然是指2、4、8、16、……），也无论最开始是如何分堆的，我们总可以用上面的操作，将其合并成一堆。

这里，球的总数在2、4、8、16……中很重要。比如，如果是3个球，开始被分成了1和2，那么，我们永远无法合并成一堆：我们能做的，只要从2个的堆中取一个放到1个的堆中，结果还是1和2，显然没法合并。

化繁为简！我们来看一个最简单的问题：如果是两个球呢？两个球，要么开始就是一堆，这自然不必再说，还有一种情况，开始时是1和1，很显然，直接合并就是了。也就是说，2个球的情况，经检验，上述结论是正确的。

让我们来看4个球的情况。我们可以来罗列一下最开始可能存在的分堆情况：

A：（4）

B：（3，1）

C：（2，2）

D：（2，1，1）

A情况不必多说，

C情况，可以直接合并。

B和D情况，通过一步挪动，即可转化为C情况。

从而可以确定：对于4个球，上述结论也是对的。

如果这样继续下去，就会没完没了。接下来的推理，将一次性解决问题。我们的目标是要一次性的、系统的说明：

如果结论对4个球是对的，那么对8个球也是对的。

如果结论对8个球是对的，那么对16个球也是对的。

如果结论对16个球是对的，那么对32个球也是对的。

……

总之，我们是要说明：

如果我们果然说清楚了上面的道理，那么因为我们验证了：结果对2个球的对的，从而——根据上面的说法——结论对4个球就是对的。然后——继续根据上面的说法——结论对8个球也是对的，再然后——再继续根据上面的说法——结论对16个球也是对的……

如此下去，我们就知道了，结论对球的个数为2、4、8、16、32、64、128……都是对的。

为了方便理解，我们还是讨论8个球。我们的目标是想说明，如果结论对4个球是对的，那么对8个球也是对的。我们不过再具体讨论每一种分法了，因为这样研究，我们没有办法利用“结论对4个球是正确的”这一结论。我们下面的讨论，目标是把8个球的情况转化为4个球的情况，从而利用4个球的结论解决问题。思路是这样的：

首先，8个球分堆的情况有两类：

第一类：每堆都是偶数。

第二类：有一些堆的个数是奇数。在这种情况下，因为所有球的总数是偶数，所有球的个数是奇数的堆数，应该是偶数。（如个有奇数堆，每堆个数是奇数，那么总数就不可能是偶数）

我们来考虑第二类情况。容易说明：对于两个奇数堆，通过一次挪动，就可以变成两个或一个偶数堆。比如3和5，通过一次挪动就可以变成6和2，比如3和3，通过一次挪动，就可以变成6。

因为奇数堆的堆数是偶数，我们两两配对后，每对进行一次上述操作，就可以消灭奇数堆。

现在，我们已经说明，无论8个球是怎样分堆的，我们都可以先通过一些操作，消灭其中球的个数是奇数的堆。

现在，已经只剩下偶数了。接下来就是最神奇的处理了：

既然都是偶数了，就把两个球捆在一起，移动时整捆整捆的移，也就是把一捆看成一个球。很显然，这时只剩下4个“球”了。4个球的问题已经解决了，所以8个球的问题就能解决。

对于16个球的情况，同样，先消灭球数为奇数的堆，再两个捆成一捆，就成了8个“球”了。

一般的，对于

个球的情况，先消灭球数为奇数的堆，再两个捆成一捆，就成了

个“球”了。即：

我们验证了，对

个球，即2个球，结论是对的，从而——反复利用上面的结论——象多米诺骨牌一样，4、8、16、32……个球的情况，全部是对的。

这个思路，就是所谓的数学归纳法，最简单的情况是：

如果想证明一个结论对所有的自然数都成对，我们只要说明两件事：

（1）验证：这个结论对第一个自然数（0）是成立的。

（2）说明：如果这个结论对N成立，那么这个结论对N+1也成立。

做成这两件事后，结论对0成立，从而——由（2）——对1成立，从而——再由（2）——对2成立……即以0成立为起点，反复运用（2），可得结论对所有自然数成立。