50-я Международная Математическая OлимпиадаГермания, Бремен, 2009 год

Дана строго возрастающая последовательность целых положительных чисел ${{s}_{1}}$, ${{s}_{2}}$, ${{s}_{3}}$, $\ldots $ такая, что каждая из двух последовательностей ${{s}_{{{s}_{1}}}}$, ${{s}_{{{s}_{2}}}}$, ${{s}_{{{s}_{3}}}}$, $\ldots $ и ${{s}_{{{s}_{1}}+1}}$, ${{s}_{{{s}_{2}}+1}}$, ${{s}_{{{s}_{3}}+1}}$, $\ldots $ является арифметической прогрессией. Докажите, что последовательность ${{s}_{1}}$, ${{s}_{2}}$, ${{s}_{3}}$, $\ldots $ также является арифметической прогрессией.

Комментарий/решение

В силу возрастания прогрессии описанных в условиях, справедливо неравенство $s_{s_{t}}<s_{s_{t}+1} \leq s_{s_{t+1}}$ пусть прогрессии определены как $s_{s_{1}},d_{1}$ и $s_{s_{1}+1},d_{2}$ соответственно. Тогда неравенство выше можно записать как $s_{s_{1}}+d_{1}(n-1) < s_{s_{1}+1}+(n-1)d_{2} \leq s_{s_{1}}+nd_{1}$ или что тоже самое что $0<s_{s_{1}+1}-s_{s_{1}}+(n-1)(d_{2}-d_{1}) \leq d_{1}$ $(1)$ откуда $\dfrac{s_{s_{1}}-s_{s_{1}+1}+d_{1}(n-1)}{n-1}< d_{2} \leq \dfrac{s_{s_{1}}-s_{s_{1}+1}+d_{1}n}{n-1}$ при $n-> +\infty$ выполняется $d_{1} -> d_{2}$ при фиксированных $s_{s_{1}}, s_{s_{1}+1}$ то есть при $d_{1}>d_{2}, d_{1}<d_{2}$ неравенство $(1)$ выполняется не для всех $n$.

Рассмотрим случай когда $d_{1}=d_{2}=d$ , пусть $k_{t}>0$ целое не постоянное число на которое увеличивается индекс прогрессии $s_{s_{1}+k_{t}}$ так же пусть $s_{s_{1}}=a, s_{s_{1}+1}=b$ положим что $s_{1},s_{2},...s_{n}$ не арифметическая прогрессия, тогда если $b-a \ne d$ (следует из того что $s_{s_{t}+1} \ne s_{s_{t+1}} $ или $ b+d(n-1) \ne a+dn$) тогда $s_{s_{t}+1} \ne s_{s_{t+1}}$ тогда в таком построении $k_{t} \ne 1$ иначе $s_{s_{t}+1}=s_{s_{t+1}}$ что противоречит условия возрастания, в случае $b-a=d$ то $k_{t}=1$ но тогда это противоречит тому что прогрессия не арифметическая, так как последовательность $s_{1},s_{2},..s_{n}$ будет арифметической с разностью $1$.

Покажем что если в данной прогрессии есть $k_{t}=2$ то найдется и $k_{t'}=1$ (которая не удовлетворяет условию)

Доказательство: если $k_{t}=2$ тогда между каким-то членами последовательности $s_{n}$ а именно $s_{s_{\alpha}+1}$ и $s_{s_{\alpha+1}}$ которая удовлетворяет условию $q=s_{\alpha+1}-s_{s_{\alpha}+1} = a+d-b-1$ должно уместиться $q$ количество наборов чисел что $s_{s_{\alpha}+1}+k_{1}+k_{2}+...k_{q} = s_{s_{\alpha+1}}$ но тогда $\dfrac{s_{s_{\alpha+1}}-s_{s_{\alpha}+1}}{q} = \dfrac{a+d-b}{a+d-b-1} = 1+\dfrac{1}{a+d-b-1} <2$ тогда по принципу Дирихле в $q$ найдется как минимум одно $k_{t'}=1$.

Значит $k_{t}=2$ не может быть в прогрессии $s_{s_{t}}$, тогда $k_{t} \geq 3$. Рассмотрим при каких $k$ можно будет расположить в системе двух а.п такие $k_{t} \geq 3$, для этого условия требуется чтобы $s_{s_{l}+1}$ до $s_{s_{l+1}}=s_{s_{l}+k_{t}}$ выполнялось для индексов условие $s_{s_{l}+1}+3(k-1) \leq s_{s_{l}+k_{t}}$ или $k \leq [\dfrac{a+d-b+3}{3}]$ то есть при $3 \leq k \leq [\dfrac{a+d-b+3}{3}]$ следует что $k_{t} \geq 3 $ аналогично при $x \leq k \leq [\dfrac{a+d-b+x}{x}]$ для $k_{t} \geq x$ $(2)$ , расставив числа которые может принимать $k_{t}$ в ряд $[3,4,5,...,\dfrac{a+d-b+3}{3}]$ , если $a+d-b>6$ то следует из того что $ \dfrac{a+d-b}{3-1}>\dfrac{a+d-b+3}{3}$ то какие то значение $k$ выйдет за пределы $\dfrac{a+d-b+3}{3-1}$ а это значит они попадут в предел значения $k_{t} \geq 2$ то есть какие то $k_{t}=2$ по принципу Дирихле (что нельзя), случай $a+d-b<6$ рассматривается аналогично, так продолжая и отсекая числа которые может принимать $k$ по тому же принципу получим что какие бы не брали $k$ из списка, процесс всегда будет последовательно приводит к $k_{t}=1$ (что нельзя) по построению.

Единственный возможный случай когда $\dfrac{a+d-b}{k-1}=k$ так как по принципу Дирихле оно не попадет не в одно из стертых чисел в ряду, то есть получили $k+k+k+...+k=a+d-b$ где всего $k-1$ слагаемых, если убавлять и прибавлять по $1$ то обязательно попадет в одно из стертых чисел, которая приведет как было раннее сказано к случаю $k_{t}=1$, но тогда $k$ постоянная , то есть арифметическая прогрессия, тогда $s_{1},s_{2},...s_{n}$ прогрессия с разностью $d'=k$.

Пусть $s(m)=s_m.$ Из условия следует, что $s(m)-s(n)\ge m-n,\forall m \ge n\in\mathbb N.$

Claim 1. Последовательности $\{s(s_i)\}_{i\ge 1}$ и $\{s(s_i + 1)\}_{i\ge 1}$ имеют одинаковую разность $d.$

Пусть $s(s_{i+1})-s(s_i)=A$ и $s(s_{i+1} + 1)-s(s_i + 1)=B$ $\implies s(s_i) = s(s_1) + A(i-1)$ и $s(s_i + 1) = s(s_1 + 1) + B(i-1)$

Выпишем следующие неравенства:

$$s_{i+1} \ge s_i + 1 > s_i \implies s(s_{i+1}) \ge s(s_i + 1) > s(s_i)$$

$$\implies s(s_1)+Ai \ge (s(s_1 + 1) - B) + Bi > (s(s_1)-A)+Ai$$

$$\implies (s(s_1 + 1) - B) - (s(s_1)-A) > (A-B)i \ge (s(s_1 + 1) - B) - s(s_1), \forall i\in \mathbb N.$$

То есть $(A-B)i$ ограничен с обоих сторон для любого натурального $i,$ значит $A=B=d.$ $\ \square$

Отсюда можем заметить, что $\boxed {s(s_k + 1) - s(s_k) = s(s_1 + 1) - s(s_1)=const.}$

(ii) Заменим $s_{i+1}-s_i = d_i>0.$ Заметим, что

$d=s(s_{i+1})-s(s_i) \ge s_{i+1} - s_i = d_i,$

откуда последовательность $d_i$ ограничена. Пусть $\min d_i = m$ и $\max d_i = M.$

(iii) Давайте оценим $d= s(s_{j+1})-s(s_j):$

$$ \left\{ \begin{gathered} (1,j): d = s(s_{j+1})-s(s_j) = \sum_{i=s_j}^{s_{j+1}-1} d_i \ge \sum_{i=s_j}^{s_{j+1}-1} m = m(s_{j+1}-s_j)=md_j, \forall j\in\mathbb N \\ (2,j): d = s(s_{j+1})-s(s_j) = \sum_{i=s_j}^{s_{j+1}-1} d_i \le \sum_{i=s_j}^{s_{j+1}-1} M = M(s_{j+1}-s_j)=Md_j, \forall j\in\mathbb N. \\ \end{gathered} \right. $$

Откуда подбирая $u$ и $v,$ что $d(u)=M$ и $d(v)=m$ из $(1,u)$ и $(2,v)$ выводим, что $mM\le d \le mM\implies d=mM.$

Откуда $d_i=m,\forall i=s_u,...,s_{u+1}-1\implies m=s(s_u+1)-s(s_u)=const.$

Также $d_i=M,\forall i=s_v,...,s_{v+1}-1\implies M=s(s_v+1)-s(s_v)=const.$

Значит $m=M\implies d_i=M,\forall i\in\mathbb N,$ следовательно $\{s_i\}$ $-$ арифметическая прогрессия.

не понял, но выглядит жестока