$n(n \geqslant 4)$ 个盘子里放有总数不少于 $4$ 的糖块,从任选的两个盘子中各取一块糖,放入另一个盘子中去,称为一次操作问能否经过有限次操作,把所有糖块集中到一个盘子里去?证明你的结论.
【难度】
【出处】
1994第9届CMO试题
【标注】
  • 知识点
    >
    二试组合部分
【答案】
【解析】
能经过有限次操作,把所有糖块集中到一个盘子里去,对糖块总数 $m(m \geqslant 4)$ 进行归纳.当 $m=4$ 时,盛有糖块的盘子不多于 $4$ 个.去掉 $n-4$ 个空盘,在剩下 $4$ 个盘子里,糖块分布有以下 $4$ 种情况要考虑:
$\begin{array}{ll}{\text { (1) }(1,1,1,1)} & {\text { (2) }(1,2,1,0)} \\ {\text { (3) }(2,2,0,0)} & {\text { (4) }(1,3,0,0)}\end{array}$
对于第一种情况,可进行如下几次操作,使糖块集中到一个盘子里:$(1,1,1,1) \rightarrow(3,1,0,0) \rightarrow(2,0,2,0) \rightarrow(1,0,1,2) \rightarrow(0,0,0,4)$
从上述操作可以看到:对于第二,三,四种情况,糖块亦能集中到一个盘子里.
假设当 $m=k(k \geqslant 4)$ 时,所有糖块能集中到一个盘子里.当 $m=k+1(k \geqslant 4)$ 时,在盛糖块的一个盘子里固定一块糖,暂不去考虑它.对于剩下的 $k(k \geqslant 4)$ 块糖,利用数学归纳法,可知这 $k$ 块糖是能够集中到一个盘子里的.如果这个盘子恰是盛有固定糖块的盘子,则结论已经成立.否则,恰有两个盘子盛有糖块,一个盘子里只有一块糖,另一个盘子里有 $k$ 块糖.再取两个空盘,进行如下的操作:$(1, k, 0,0) \rightarrow(0, k-1,2,0) \rightarrow(0, k-2,1,2) \rightarrow(2, k-3,0,2) \rightarrow(1, k-1,0,1) \rightarrow(0, k+1,0,0)$ 所有糖块在一个盘子里了.结论成立.
答案 解析 备注
0.110875s