设非负整数的无穷数列 $a_{1}, a_{2}, \cdots$ 满足：对任意正整数 $m,n$，均有 $\displaystyle \sum\limits_{i=1}^{2 m} a_{i n} \leqslant m$．证明：存在正整数 $k、d$，满足 $\sum_\limits{i=1}^{2 k} a_{i d}=k-2014$．
【难度】
【出处】
2014第30届CMO试题
【标注】
【答案】
略
【解析】
由于 $a_{1}, a_{2}, \cdots$ 为非负整数数列，在条件中取 $m=1$，知对任意正整数 $n$，有 $0 \leqslant a_{n}+a_{2 n} \leqslant 1$．
故 $a_{n} \in\{0,1\}$，且有无穷多个 $n$，使得 $a_n =0$．
下面证明：有无穷多个正整数 $n$，使得 $a_{n}+a_{2 n}=0$．
否则，假设只有有限多个这样的 $n$．则存在正整数 $N$，使得 $n\geqslant N$ 时，总有 $a_{n}+a_{2 n}=1$．
由于对无穷多个 $n$ 有 $a_n =0$，故可取定一个正整数 $d>N$，使得 $a_d=0$．则对任意正整数 $m$，一方面，由条件知 $\displaystyle \sum\limits_{i=1}^{2 m} a_{i d}+\sum_{i=1}^{2 m} a_{2 i d} \leqslant m+m=2 m$ ①
另一方面，由于 $id >N$，故由假设知 $\displaystyle \sum\limits_{i=1}^{2 m} a_{i d}+\sum_{i=1}^{2 m} a_{2 i d}=\sum_{i=1}^{2 m}\left(a_{i d}+a_{2 i d}\right)=\sum_{i=1}^{2 m} 1=2 m$ ②
故由式 ①、②，知对任意正整数 $m$，有 $\displaystyle \sum\limits_{i=1}^{2 m} a_{i d}=m$ ③
而 $d>N$，故由假设知对所有整数 $r\geqslant 1$ 均有 $a_{r d}+a_{2 r d}=1$ ④
在式 ④ 中分别取 $r=1,2,4$ 可依次得到 $a_{2 d}=1-a_{d}=1, a_{4 d}=1-a_{2 d}=0$ 及 $a_{8 d}=1-a_{4 d}=1$．
由式 ③（取 $m=2$），知 $a_{3d}=1$．
于是，由式 ④（取 $r=3,6$）得 $a_{6 d}=1-a_{3 d}=0, a_{12 d}=1-a_{6 d}=1$．
再在式 ③ 中取 $m=3$，知 $a_{5d}=1$．
从而，$a_{10 d}=1-a_{5 d}=0$．
最后，由式 ③（分别取 $m=4,5$）得 $a_{7 d}=0, a_{9 d}=1$．
故 $a_{3 d}+a_{6 d}+a_{9 d}+a_{12 d}=1+0+1+1=3>2$．
这与已知条件（取 $n=3d,m=2$）矛盾．
因此，可证明有无穷多个 $n$，使得 $a_{n}+a_{2 n}=0$．
现在可取正整数 $t$，使得至少有 $4 028$ 个正整数 $n\geqslant t$，满足 $a_{n}+a_{2 n}=0$．
则 $\displaystyle \sum\limits_{i=1}^{t}\left(a_{i}+a_{2 i}\right) \leqslant t-4028$．
于是，$\displaystyle \sum\limits_{i=1}^{t} a_{i} \leqslant \dfrac{t}{2}-2014$ 或 $\displaystyle \sum\limits_{i=1}^{t} a_{2 i} \leqslant \dfrac{t}{2}-2014$．
总之，存在正整数 $t、d$（$d=1$ 或 $2$），使得 $\displaystyle \sum\limits_{i=1}^{t} a_{i d} \leqslant \dfrac{t}{2}-2014$．
令 $\displaystyle b_{s}=\sum\limits_{i=1}^{s} a_{i d}-\dfrac{s}{2}(s=1,2, \cdots, t)$．则 $b_{1}=a_{d}-\dfrac{1}{2} \geqslant-\dfrac{1}{2}, b_{t} \leqslant-2014$．
设 $l$ 为满足 $b_{l} \leqslant-2014$ 的最小正整数．则 $b_{l-1} \geqslant-2014+\dfrac{1}{2}$．
由 $b_{l}-b_{l-1}=a_{l d}-\dfrac{1}{2} \geqslant-\dfrac{1}{2}$，知 $b_{l} \geqslant b_{l-1}-\dfrac{1}{2} \geqslant-2014$．
故 $b_l=-2 014$，即 $\displaystyle \sum\limits_{i=1}^{l} a_{i d}=\dfrac{l}{2}-2014$．
由 $\displaystyle \sum\limits_{i=1}^{l} a_{i d}$ 为整数，知上式中 $l$ 为偶数．
记 $l=2k$．则ill $\displaystyle \sum\limits_{i=1}^{2 k} a_{i d}=k-2014$．
故 $a_{n} \in\{0,1\}$，且有无穷多个 $n$，使得 $a_n =0$．
下面证明：有无穷多个正整数 $n$，使得 $a_{n}+a_{2 n}=0$．
否则，假设只有有限多个这样的 $n$．则存在正整数 $N$，使得 $n\geqslant N$ 时，总有 $a_{n}+a_{2 n}=1$．
由于对无穷多个 $n$ 有 $a_n =0$，故可取定一个正整数 $d>N$，使得 $a_d=0$．则对任意正整数 $m$，一方面，由条件知 $\displaystyle \sum\limits_{i=1}^{2 m} a_{i d}+\sum_{i=1}^{2 m} a_{2 i d} \leqslant m+m=2 m$ ①
另一方面，由于 $id >N$，故由假设知 $\displaystyle \sum\limits_{i=1}^{2 m} a_{i d}+\sum_{i=1}^{2 m} a_{2 i d}=\sum_{i=1}^{2 m}\left(a_{i d}+a_{2 i d}\right)=\sum_{i=1}^{2 m} 1=2 m$ ②
故由式 ①、②，知对任意正整数 $m$，有 $\displaystyle \sum\limits_{i=1}^{2 m} a_{i d}=m$ ③
而 $d>N$，故由假设知对所有整数 $r\geqslant 1$ 均有 $a_{r d}+a_{2 r d}=1$ ④
在式 ④ 中分别取 $r=1,2,4$ 可依次得到 $a_{2 d}=1-a_{d}=1, a_{4 d}=1-a_{2 d}=0$ 及 $a_{8 d}=1-a_{4 d}=1$．
由式 ③（取 $m=2$），知 $a_{3d}=1$．
于是，由式 ④（取 $r=3,6$）得 $a_{6 d}=1-a_{3 d}=0, a_{12 d}=1-a_{6 d}=1$．
再在式 ③ 中取 $m=3$，知 $a_{5d}=1$．
从而，$a_{10 d}=1-a_{5 d}=0$．
最后，由式 ③（分别取 $m=4,5$）得 $a_{7 d}=0, a_{9 d}=1$．
故 $a_{3 d}+a_{6 d}+a_{9 d}+a_{12 d}=1+0+1+1=3>2$．
这与已知条件（取 $n=3d,m=2$）矛盾．
因此，可证明有无穷多个 $n$，使得 $a_{n}+a_{2 n}=0$．
现在可取正整数 $t$，使得至少有 $4 028$ 个正整数 $n\geqslant t$，满足 $a_{n}+a_{2 n}=0$．
则 $\displaystyle \sum\limits_{i=1}^{t}\left(a_{i}+a_{2 i}\right) \leqslant t-4028$．
于是，$\displaystyle \sum\limits_{i=1}^{t} a_{i} \leqslant \dfrac{t}{2}-2014$ 或 $\displaystyle \sum\limits_{i=1}^{t} a_{2 i} \leqslant \dfrac{t}{2}-2014$．
总之，存在正整数 $t、d$（$d=1$ 或 $2$），使得 $\displaystyle \sum\limits_{i=1}^{t} a_{i d} \leqslant \dfrac{t}{2}-2014$．
令 $\displaystyle b_{s}=\sum\limits_{i=1}^{s} a_{i d}-\dfrac{s}{2}(s=1,2, \cdots, t)$．则 $b_{1}=a_{d}-\dfrac{1}{2} \geqslant-\dfrac{1}{2}, b_{t} \leqslant-2014$．
设 $l$ 为满足 $b_{l} \leqslant-2014$ 的最小正整数．则 $b_{l-1} \geqslant-2014+\dfrac{1}{2}$．
由 $b_{l}-b_{l-1}=a_{l d}-\dfrac{1}{2} \geqslant-\dfrac{1}{2}$，知 $b_{l} \geqslant b_{l-1}-\dfrac{1}{2} \geqslant-2014$．
故 $b_l=-2 014$，即 $\displaystyle \sum\limits_{i=1}^{l} a_{i d}=\dfrac{l}{2}-2014$．
由 $\displaystyle \sum\limits_{i=1}^{l} a_{i d}$ 为整数，知上式中 $l$ 为偶数．
记 $l=2k$．则ill $\displaystyle \sum\limits_{i=1}^{2 k} a_{i d}=k-2014$．
答案
解析
备注
