设 $a_{1},a_{2},\ldots,a_{n}$ 是互不相同的正整数．$M$ 是有 $n-1$ 个元素的正整数集，且不含数 $s=a_{1}+a_{2}+\ldots+a_{n}$．一只蚱蜢沿着实数轴从原点 $0$ 开始向右跳跃 $n$ 步，它的跳跃距离是 $a_{1},a_{2},\ldots,a_{n}$ 的某个排列．证明：可以选择一种排列，使得蚱蜢跳跃落下的点所表示的数都不在集 $M$ 中．（俄罗斯）
【难度】
【出处】
2009年第50届IMO试题
【标注】
【答案】
略
【解析】
采用数学归纳法对 $n$ 进行归纳．
当 $n=1$ 时，$M$ 中无元素，结论显然成立．
当 $n=2$ 时，$M$ 至少不包含 $a_1,a_2$ 中的一个数，则蚱蜢先跳这个数，再跳另一个数即可．
假设当 $n\in\mathbb{N^+},n<m$ 时，本题结论也成立．若不然，则存在 $m$ 个不同正整数 $a_1,a_2,\cdots,a_m$ 及由 $m-1$ 个数组成的集合 $M$，使得蚱蜢无法按照规则跳跃．
假设蚱蜢最多自原点开始向右跳跃 $k$ 步，使得每一步跳跃的长度都是 $a_1,a_2,\cdots,a_m$ 中不同的数，且蚱蜢跳跃落下的点所表示的数都不在 $M$ 中．由于 $M$ 中只有 $m-1$ 个数，第一步必然能够跳跃，又由前面假设蚱蜢无法完成 $m$ 步的跳跃，因此 $1\leqslant k\leqslant m-1$．由条件知 $a_1+a_2+\cdots+a_m$ 不在 $M$ 中，即蚱蜢如果能跳 $m-1$ 步，则必然能跳 $m$ 步，因此 $1\leqslant k\leqslant m-2$．
取这样的 $k$ 步跳跃中，步长之和最小的一种（若有相同的则可任取一种），设这 $k$ 步依次为 $b_1,b_2,\cdots,b_k$，并设 $b_{k+1}<b_{k+2}<\cdots<b_m$ 是 $b_1b_2,\cdots,b_k$ 后剩下的数，则
$\{a_1,a_2,\cdots,a_m\}=\{b_1,b_2,\cdots,b_m\}$．
由假设易知对任意 $k+1\leqslant j\leqslant m,b_1+b_2+\cdots+b_k+b_j$ 都在 $M$ 中，即 $M$ 中不小于 $b_1+b_2+\cdots+b_{k+1}$ 的数至少有 $m-k$ 个，故 $M$ 中不小于 $b_1+b_2+\cdots+b_{k+1}$ 的数至多有 $k-1$ 个．
记集合
$A=\{b_i|1\leqslant i\leqslant k+1,i\in\mathbb{Z},b_1+b_2+\cdots+b_{k+1}-b_i\not\in M\}$，则 $b_{k+1}\in A$．对任意 $b_i\in A$，从 $b_1,b_2,\cdots,b_{k+1}$ 中去掉 $b_i$ 还剩下 $k$ 个数，它们的和不在 $M$ 中，且
$|M\bigcap \{1,2,\cdots,b_1+b_2+\cdots+b_{k+1}-b_i\}|\leqslant k-1$
由 $k<m$ 及原题的归纳假设易知存在这些数的排列 $c_1,c_2,\cdots,c_k$，使得
$c_1,c_1+c_2,\cdots,c_1+c_2+\cdots+c_k$
都不在 $M$ 中，这样蚱蜢也可以按照 $c_1,c_2,\cdots,c_k$ 的顺序连跳 $k$ 步．由 $b_1,b_2,\cdots,b_k$ 的取法知
$b_1+b_2+\cdots+b_k\leqslant c_1+c_2+\cdots+c_k$
即 $b_i\leqslant b_{k+1}$．
令 $A=\{x_1,x_2,\cdots,x_t\}$，其中 $x_1<x_2<\cdots<x_t=b_{k+1}$．由 $A$ 的定义知 $M$ 中小于 $b_1+b_2+\cdots+b_{k+1}$ 的数至少有 $k+1-t$ 个；由于对任意 $k+1\leqslant j\leqslant m,b_1+b_2+\cdots+b_k+b_j$ 都在 $M$ 中，故 $M$ 在区间
$[b_1+b_2+\cdots+b_{k+1},b_1+b_2+\cdots+b_k+b_m]$
内的数至少有 $m-k$ 个．
另一方面，对于任意 $x_i\in A$，
$b_1+b_2+\cdots+b_{k+1}-x_i+b_m$
都应在 $M$ 中（否则由于 $k\leqslant m-2$，$b_m$ 与 $b_1,b_2,\cdots,b_{k+1}$ 均不同，蚱蜢就可以跳 $k+1$ 步了）．对于每个 $1\leqslant i\leqslant t-1$，
$b_1+b_2+\cdots+b_{k+1}-x_i+b_m$
是互不相同且大于 $b_1+b_2+\cdots+b_k+b_m$ 的数，因此 $M$ 中大于 $b_1+b_2+\cdots+b_k+b_m$ 的数至少有 $t-1$．故 $M$ 中至少有
$(k+1-t)+(m-k)+(t-1)=m$
个数，这与 $M$ 中只有 $m-1$ 个数矛盾．
因此，假设不成立，即当 $n=m$ 时本题结论也成立，故本题结论对所有正整数 $n$ 均成立．证毕．
当 $n=1$ 时，$M$ 中无元素，结论显然成立．
当 $n=2$ 时，$M$ 至少不包含 $a_1,a_2$ 中的一个数，则蚱蜢先跳这个数，再跳另一个数即可．
假设当 $n\in\mathbb{N^+},n<m$ 时，本题结论也成立．若不然，则存在 $m$ 个不同正整数 $a_1,a_2,\cdots,a_m$ 及由 $m-1$ 个数组成的集合 $M$，使得蚱蜢无法按照规则跳跃．
假设蚱蜢最多自原点开始向右跳跃 $k$ 步，使得每一步跳跃的长度都是 $a_1,a_2,\cdots,a_m$ 中不同的数，且蚱蜢跳跃落下的点所表示的数都不在 $M$ 中．由于 $M$ 中只有 $m-1$ 个数，第一步必然能够跳跃，又由前面假设蚱蜢无法完成 $m$ 步的跳跃，因此 $1\leqslant k\leqslant m-1$．由条件知 $a_1+a_2+\cdots+a_m$ 不在 $M$ 中，即蚱蜢如果能跳 $m-1$ 步，则必然能跳 $m$ 步，因此 $1\leqslant k\leqslant m-2$．
取这样的 $k$ 步跳跃中，步长之和最小的一种（若有相同的则可任取一种），设这 $k$ 步依次为 $b_1,b_2,\cdots,b_k$，并设 $b_{k+1}<b_{k+2}<\cdots<b_m$ 是 $b_1b_2,\cdots,b_k$ 后剩下的数，则
$\{a_1,a_2,\cdots,a_m\}=\{b_1,b_2,\cdots,b_m\}$．
由假设易知对任意 $k+1\leqslant j\leqslant m,b_1+b_2+\cdots+b_k+b_j$ 都在 $M$ 中，即 $M$ 中不小于 $b_1+b_2+\cdots+b_{k+1}$ 的数至少有 $m-k$ 个，故 $M$ 中不小于 $b_1+b_2+\cdots+b_{k+1}$ 的数至多有 $k-1$ 个．
记集合
$A=\{b_i|1\leqslant i\leqslant k+1,i\in\mathbb{Z},b_1+b_2+\cdots+b_{k+1}-b_i\not\in M\}$，则 $b_{k+1}\in A$．对任意 $b_i\in A$，从 $b_1,b_2,\cdots,b_{k+1}$ 中去掉 $b_i$ 还剩下 $k$ 个数，它们的和不在 $M$ 中，且
$|M\bigcap \{1,2,\cdots,b_1+b_2+\cdots+b_{k+1}-b_i\}|\leqslant k-1$
由 $k<m$ 及原题的归纳假设易知存在这些数的排列 $c_1,c_2,\cdots,c_k$，使得
$c_1,c_1+c_2,\cdots,c_1+c_2+\cdots+c_k$
都不在 $M$ 中，这样蚱蜢也可以按照 $c_1,c_2,\cdots,c_k$ 的顺序连跳 $k$ 步．由 $b_1,b_2,\cdots,b_k$ 的取法知
$b_1+b_2+\cdots+b_k\leqslant c_1+c_2+\cdots+c_k$
即 $b_i\leqslant b_{k+1}$．
令 $A=\{x_1,x_2,\cdots,x_t\}$，其中 $x_1<x_2<\cdots<x_t=b_{k+1}$．由 $A$ 的定义知 $M$ 中小于 $b_1+b_2+\cdots+b_{k+1}$ 的数至少有 $k+1-t$ 个；由于对任意 $k+1\leqslant j\leqslant m,b_1+b_2+\cdots+b_k+b_j$ 都在 $M$ 中，故 $M$ 在区间
$[b_1+b_2+\cdots+b_{k+1},b_1+b_2+\cdots+b_k+b_m]$
内的数至少有 $m-k$ 个．
另一方面，对于任意 $x_i\in A$，
$b_1+b_2+\cdots+b_{k+1}-x_i+b_m$
都应在 $M$ 中（否则由于 $k\leqslant m-2$，$b_m$ 与 $b_1,b_2,\cdots,b_{k+1}$ 均不同，蚱蜢就可以跳 $k+1$ 步了）．对于每个 $1\leqslant i\leqslant t-1$，
$b_1+b_2+\cdots+b_{k+1}-x_i+b_m$
是互不相同且大于 $b_1+b_2+\cdots+b_k+b_m$ 的数，因此 $M$ 中大于 $b_1+b_2+\cdots+b_k+b_m$ 的数至少有 $t-1$．故 $M$ 中至少有
$(k+1-t)+(m-k)+(t-1)=m$
个数，这与 $M$ 中只有 $m-1$ 个数矛盾．
因此，假设不成立，即当 $n=m$ 时本题结论也成立，故本题结论对所有正整数 $n$ 均成立．证毕．
答案
解析
备注
