Question

设有2ⁿ个球分成许多堆,我们可以任意选甲乙两堆按以下规则挪动.若甲堆的球数是p,不少于乙堆的球数q,则从甲堆里拿q个球放到乙堆里,这样算挪动一次.证明可以经过有限次挪动,把所有的球合并成一堆.

Answer 1

证明:(1)当n=1时,有两个球,分为两堆,挪动一次就行了,即命题成立.

(2)假设当n=k,即有2^k个球时命题成立.当n=k+1时,有2^k+1=2·2^k个球,显然球的个数为偶数,把它们两两配对可分成2^k对.这时只需将每对球看成一个整体,即2^k个“球”,于是问题就变成n=k时的情形了,由归纳假设知n=k+1时命题也成立.