设 $s_{1},s_{2},s_{3},\ldots$ 是一个严格递增的正整数数列，使得它的两个子数列 $s_{s_{1}},s_{s_{2}},s_{s_{3}},\ldots~~~\text{和}~~~s_{s_{1}+1},s_{s_{2}+1},s_{s_{3}+1},\ldots$ 都是等差数列．证明：数列 $s_{1},s_{2},s_{3},\ldots$ 本身也是一个等差数列．（美国）
【难度】
【出处】
2009年第50届IMO试题
【标注】
【答案】
略
【解析】
由条件易知 $s_{s_1},s_{s_2},s_{s_3},\cdots$ 与 $s_{s_1+1},s_{s_2+1},s_{s_3+1},\cdots$ 均为严格递增的正整数数列．
设 $S_{S_k}=a+(k-1)d_1,S_{S_k+1}=b+(k-1)d_2,k=1,2,\cdots$，其中 $a,b,d_1,d_2$ 是正整数．
由 $s_k<s_k+1\leqslant s_{k+1}$ 及 $\{S_n\}$ 的单调性知对任意正整数 $k$，有
$S_{S_k}<S_{S_k+1}\leqslant S_{S_{k+1}}$
即 $a+(k-1)d_1<b+(k-1)d_2\leqslant a+kd_1$
即 $a-b<(k-1)(d_2-d_1)\leqslant a+d_1-b$．
由 $k$ 的任意性知 $d_2-d_1=0$，即 $d_2=d_1$，两者记其为 $d$，并记 $b-a=c\in \mathbb{N^+}$．
若 $d=1$，则由 $\{S_n\}$ 的单调性知 $S_{S_{k+1}}=S_{S_k}+1\leqslant S_{S_k+1}$，故 $s_{k+1}\leqslant s_k+1$，又由于 $s_{k+1}>s_k$，故 $s_{k+1}=s_k+1$，即 $\{s_n\}$ 为等差数列，结论已成立，下设 $d>1$．
我们证明对于任意正整数 $k$，均有 $s_{k+1}-s_k=c$．
若不然，则分两种情况讨论．
情况一：存在正整数 $k$，使得 $s_{k+1}-s_k<c$，由于 $s_{k+1}-s_k$ 只能取整值，则其中必有最小者．不妨设 $s_{i+1}-s_i=c_0$ 最小，则
$\begin{aligned}
S_{a+id}-S_{a+(i-1)d+1}&=S_{S_{S_{i+1}}}-S_{S_{S_i}+1}\\
&=(a+(s_{i+1})d)-(b+(s_i-1)d)\\
&=c_0d-c
\end{aligned}$ ①
另一方面，由
$(a+jd)-(a+(j-1)d+1)=d-1$
（这里用到了 $c_1$ 的最大性），与 ② 式比较得 $c_1\leqslant c$，矛盾．
因此，对于任意正整数 $k$，均有 $s_{k+1}-s_k=c$，即 $\{s_n\}$ 为等差数列．证毕．
设 $S_{S_k}=a+(k-1)d_1,S_{S_k+1}=b+(k-1)d_2,k=1,2,\cdots$，其中 $a,b,d_1,d_2$ 是正整数．
由 $s_k<s_k+1\leqslant s_{k+1}$ 及 $\{S_n\}$ 的单调性知对任意正整数 $k$，有
$S_{S_k}<S_{S_k+1}\leqslant S_{S_{k+1}}$
即 $a+(k-1)d_1<b+(k-1)d_2\leqslant a+kd_1$
即 $a-b<(k-1)(d_2-d_1)\leqslant a+d_1-b$．
由 $k$ 的任意性知 $d_2-d_1=0$，即 $d_2=d_1$，两者记其为 $d$，并记 $b-a=c\in \mathbb{N^+}$．
若 $d=1$，则由 $\{S_n\}$ 的单调性知 $S_{S_{k+1}}=S_{S_k}+1\leqslant S_{S_k+1}$，故 $s_{k+1}\leqslant s_k+1$，又由于 $s_{k+1}>s_k$，故 $s_{k+1}=s_k+1$，即 $\{s_n\}$ 为等差数列，结论已成立，下设 $d>1$．
我们证明对于任意正整数 $k$，均有 $s_{k+1}-s_k=c$．
若不然，则分两种情况讨论．
情况一：存在正整数 $k$，使得 $s_{k+1}-s_k<c$，由于 $s_{k+1}-s_k$ 只能取整值，则其中必有最小者．不妨设 $s_{i+1}-s_i=c_0$ 最小，则
$\begin{aligned}
S_{a+id}-S_{a+(i-1)d+1}&=S_{S_{S_{i+1}}}-S_{S_{S_i}+1}\\
&=(a+(s_{i+1})d)-(b+(s_i-1)d)\\
&=c_0d-c
\end{aligned}$ ①
另一方面，由
$(a+jd)-(a+(j-1)d+1)=d-1$
（这里用到了 $c_1$ 的最大性），与 ② 式比较得 $c_1\leqslant c$，矛盾．
因此，对于任意正整数 $k$，均有 $s_{k+1}-s_k=c$，即 $\{s_n\}$ 为等差数列．证毕．
答案
解析
备注
