整数序列 $a_{1},a_{2},\ldots$ 满足下列条件：
（i）对每个整数 $j\geqslant 1$，有 $1\leqslant a_{j}\leqslant 2015$；
（ii）对任意整数 $1\leqslant k<l$，有 $k+a_{k}\neq l+a_{l}$．
证明：存在两个正整数 $b$ 和 $N$，使得 $\displaystyle \left|\sum\limits_{j=m+1}^{n}(a_{j}-b)\right|\leqslant 1007^{2}$ 对所有满足 $n>m\geqslant N$ 的整数 $m$ 和 $n$ 均成立．（澳大利亚）
（i）对每个整数 $j\geqslant 1$，有 $1\leqslant a_{j}\leqslant 2015$；
（ii）对任意整数 $1\leqslant k<l$，有 $k+a_{k}\neq l+a_{l}$．
证明：存在两个正整数 $b$ 和 $N$，使得 $\displaystyle \left|\sum\limits_{j=m+1}^{n}(a_{j}-b)\right|\leqslant 1007^{2}$ 对所有满足 $n>m\geqslant N$ 的整数 $m$ 和 $n$ 均成立．（澳大利亚）
【难度】
【出处】
2015年第56届IMO试题
【标注】
【答案】
略
【解析】
设 $s_n = n+a_n$．由条件可知，$n+1\leqslant s_n \leqslant n+2015$，
且 $s_1 , s_2 , \ldots$ 互不相同．
记 $S=\{s_1 , s_2 , \ldots \}$．我们首先说明集合 $M=\mathbb{N}^{*}\backslash S$ 是有限集，且 $1\leqslant |M|\leqslant 2015$．
显然 $1\in M$．若 $M$ 中有多于 $2015$ 个元素，设 $m_1 < m_2 <\ldots< m_{2016}$ 都属于 $M$，取一整数 $n>m_{2016}$．那么
$\begin{array}{c}{\left\{s_{1}, s_{2}, \ldots, s_{n}\right\} \subset\{1,2, \ldots, n+2015\}} \\ {\left\{m_{1}, m_{2}, \ldots, m_{2016}\right\} \subset\{1,2, \ldots, n+2015\}}\end{array}$
由 $M$ 的定义，$\{ s_1 , s_2 , \ldots , s_n \}$ 与 $\{m_1 , m_2 , \ldots , m_{2016}\}$ 不相交，而 $n+2016>n+2015$，
矛盾．因此 $M$ 是有限集，且 $1\leqslant |M|\leqslant 2015$．
令 $b=|M|$，任取整数 $N>\max M$，下面证明这样选取的 $b$ 和 $N$ 满足要求．
显然 $b,N$ 都是正整数，且前面证明 $1\leqslant b\leqslant 2015$．
对任意整数 $n\geqslant N$，有如下分拆
$
\{1,2, \ldots, n+2015\}=\left\{s_{1}, s_{2}, \ldots, s_{n}\right\} \cup M \cup C_{n}
$ ①
前面已经说明 $\{s_1 , s_2 , \ldots , s_n \}$ 和 $M$ 是 $\{1,2,\ldots , n+2015\}$ 的两个不相交的子集，设 $C_n$ 为剩余部分，
$|C_n |=2015-b$．对 $j\geqslant n+1$，$s_j = j+a_j \geqslant n+1+1=n+2$．若 $C_n$ 不是空集，一定有 $n+2<\min C_n$，否则 $\min C_n$ 不在 $S$ 中，也不在 $M$ 中，矛盾．于是
$
C_{n} \subseteq\{n+2, n+3, \ldots, n+2015\}
$ ②
这对 $C_n$ 是空集（即 $b=2015$）自然也成立．计算 ① 式两边的所有元素之和，用 $\sigma(X)$ 表示有限集合 $X$ 的所有元素之和，有
$\displaystyle
\sum\limits_{i=1}^{n+2015} i=\sum_{j=1}^{n} s_{j}+\sigma(M)+\sigma\left(C_{n}\right)
$
再将 $s_j = j+a_j $ 代入化简，有
$\displaystyle
\sum\limits_{i=n+1}^{n+2015} i=\sum_{j=1}^{n} a_{j}+\sigma(M)+\sigma\left(C_{n}\right)
$
对任意 $n>m\geqslant N$，在上式中用 $m$ 代替 $n$，并将两式作差，得
$\displaystyle
\sum\limits_{i=n+1}^{n+2015} i-\sum_{i=m+1}^{m+2015} i=\sum_{j=m+1}^{n} a_{j}+\sigma\left(C_{n}\right)-\sigma\left(C_{m}\right)
$
两边减去 $(n-m)b$，并化简得
$\displaystyle \sum\limits_{j=m+1}^{n}\left(a_{j}-b\right)=(2015-b)(n-m)+\sigma\left(C_{m}\right)-\sigma\left(C_{n}\right)$ ③
由 ② 以及 $|C_n | = 2015-b$ 可知，
$\displaystyle
\sum\limits_{i=n+2}^{n+2016-b} i \leqslant \sigma\left(C_{n}\right) \leqslant \sum_{i=n+b+1}^{n+2015} i
$
即
$
\left(n+1009-\frac{b}{2}\right)(2015-b) \leqslant \sigma\left(C_{n}\right) \leqslant\left(n+1008+\frac{b}{2}\right)(2015-b)
$
上述不等式将 $n$ 换成 $m$ 也成立．回到 ③ 式，利用上面的不等式估计 $\sigma(C_n )$ 和 $\sigma(C_m )$ 的上下界，有
$\begin{aligned}\sum_{j=m+1}^{n}\left(a_{j}-b\right) \leqslant&(2015-b)(n-m)+\left(m+1008+\frac{b}{2}\right)(2015-b)-\left(n+1009-\frac{b}{2}\right)(2015-b)\\ =&(2015-b)(b-1) \\ \leqslant & 1007^{2}\end{aligned}$
以及
$\begin{aligned}\sum_{j=m+1}^{n}\left(a_{j}-b\right) \geqslant&(2015-b)(n-m)+\left(m+1009-\frac{b}{2}\right)(2015-b)-\left(n+1008+\frac{b}{2}\right)(2015-b)\\ =&-(2015-b)(b-1) \\ \geqslant & -1007^{2}\end{aligned}$
结合这两个不等式，就有 $\displaystyle
\left|\sum\limits_{j=m+1}^{n}\left(a_{j}-b\right)\right| \leqslant 1007^{2}
$ 结论获证．
且 $s_1 , s_2 , \ldots$ 互不相同．
记 $S=\{s_1 , s_2 , \ldots \}$．我们首先说明集合 $M=\mathbb{N}^{*}\backslash S$ 是有限集，且 $1\leqslant |M|\leqslant 2015$．
显然 $1\in M$．若 $M$ 中有多于 $2015$ 个元素，设 $m_1 < m_2 <\ldots< m_{2016}$ 都属于 $M$，取一整数 $n>m_{2016}$．那么
$\begin{array}{c}{\left\{s_{1}, s_{2}, \ldots, s_{n}\right\} \subset\{1,2, \ldots, n+2015\}} \\ {\left\{m_{1}, m_{2}, \ldots, m_{2016}\right\} \subset\{1,2, \ldots, n+2015\}}\end{array}$
由 $M$ 的定义，$\{ s_1 , s_2 , \ldots , s_n \}$ 与 $\{m_1 , m_2 , \ldots , m_{2016}\}$ 不相交，而 $n+2016>n+2015$，
矛盾．因此 $M$ 是有限集，且 $1\leqslant |M|\leqslant 2015$．
令 $b=|M|$，任取整数 $N>\max M$，下面证明这样选取的 $b$ 和 $N$ 满足要求．
显然 $b,N$ 都是正整数，且前面证明 $1\leqslant b\leqslant 2015$．
对任意整数 $n\geqslant N$，有如下分拆
$
\{1,2, \ldots, n+2015\}=\left\{s_{1}, s_{2}, \ldots, s_{n}\right\} \cup M \cup C_{n}
$ ①
前面已经说明 $\{s_1 , s_2 , \ldots , s_n \}$ 和 $M$ 是 $\{1,2,\ldots , n+2015\}$ 的两个不相交的子集，设 $C_n$ 为剩余部分，
$|C_n |=2015-b$．对 $j\geqslant n+1$，$s_j = j+a_j \geqslant n+1+1=n+2$．若 $C_n$ 不是空集，一定有 $n+2<\min C_n$，否则 $\min C_n$ 不在 $S$ 中，也不在 $M$ 中，矛盾．于是
$
C_{n} \subseteq\{n+2, n+3, \ldots, n+2015\}
$ ②
这对 $C_n$ 是空集（即 $b=2015$）自然也成立．计算 ① 式两边的所有元素之和，用 $\sigma(X)$ 表示有限集合 $X$ 的所有元素之和，有
$\displaystyle
\sum\limits_{i=1}^{n+2015} i=\sum_{j=1}^{n} s_{j}+\sigma(M)+\sigma\left(C_{n}\right)
$
再将 $s_j = j+a_j $ 代入化简，有
$\displaystyle
\sum\limits_{i=n+1}^{n+2015} i=\sum_{j=1}^{n} a_{j}+\sigma(M)+\sigma\left(C_{n}\right)
$
对任意 $n>m\geqslant N$，在上式中用 $m$ 代替 $n$，并将两式作差，得
$\displaystyle
\sum\limits_{i=n+1}^{n+2015} i-\sum_{i=m+1}^{m+2015} i=\sum_{j=m+1}^{n} a_{j}+\sigma\left(C_{n}\right)-\sigma\left(C_{m}\right)
$
两边减去 $(n-m)b$，并化简得
$\displaystyle \sum\limits_{j=m+1}^{n}\left(a_{j}-b\right)=(2015-b)(n-m)+\sigma\left(C_{m}\right)-\sigma\left(C_{n}\right)$ ③
由 ② 以及 $|C_n | = 2015-b$ 可知，
$\displaystyle
\sum\limits_{i=n+2}^{n+2016-b} i \leqslant \sigma\left(C_{n}\right) \leqslant \sum_{i=n+b+1}^{n+2015} i
$
即
$
\left(n+1009-\frac{b}{2}\right)(2015-b) \leqslant \sigma\left(C_{n}\right) \leqslant\left(n+1008+\frac{b}{2}\right)(2015-b)
$
上述不等式将 $n$ 换成 $m$ 也成立．回到 ③ 式，利用上面的不等式估计 $\sigma(C_n )$ 和 $\sigma(C_m )$ 的上下界，有
$\begin{aligned}\sum_{j=m+1}^{n}\left(a_{j}-b\right) \leqslant&(2015-b)(n-m)+\left(m+1008+\frac{b}{2}\right)(2015-b)-\left(n+1009-\frac{b}{2}\right)(2015-b)\\ =&(2015-b)(b-1) \\ \leqslant & 1007^{2}\end{aligned}$
以及
$\begin{aligned}\sum_{j=m+1}^{n}\left(a_{j}-b\right) \geqslant&(2015-b)(n-m)+\left(m+1009-\frac{b}{2}\right)(2015-b)-\left(n+1008+\frac{b}{2}\right)(2015-b)\\ =&-(2015-b)(b-1) \\ \geqslant & -1007^{2}\end{aligned}$
结合这两个不等式，就有 $\displaystyle
\left|\sum\limits_{j=m+1}^{n}\left(a_{j}-b\right)\right| \leqslant 1007^{2}
$ 结论获证．
答案
解析
备注
