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

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时命题也成立.