Математикадан республикалық олимпиада, 2016-2017 оқу жылы, 11 сынып

Шексіз, қатаң түрде өспелі $\left\{ {{a}_{n}} \right\}$ натурал сандар тізбегі ${{a}_{{{a}_{n}}}}\le {{a}_{n}}+{{a}_{n+3}}$ шартын қанағаттандырады, бұл жерде $n$ — натурал сан. $k < l < m$ теңсіздігі мен ${{a}_{k}}+{{a}_{m}}=2{{a}_{l}}$ теңдігі орындалатындай шексіз көп $\left( k,l,m \right)$ натурал үштіктері бар екенін дәлелдеңіздер. ( Сатылханов К. )

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

Комментарии от администратора Комментарии от администратора №1.     Решение.
Лемма 1. ${{a}_{n}}\le 2n+6$, для бесконечно многих $n$.
Доказательство. От противного, пусть существует $M > 100$ такое, что ${{a}_{n}}\ge 2n+7 \forall n\ge M$, тогда $${{a}_{n+3}}\ge {{a}_{{{a}_{n}}}}-{{a}_{n}}\ge {{a}_{n}}+7. \qquad (1)$$ Пусть $l\in \left\{ 3,4,5 \right\}$ такое число, что ${{a}_{n}}-n-l\vdots 3$. Так как ${{a}_{n}}\ge 2n+7 > n+l$, тогда из (1) следует, что ${{a}_{n}}\ge {{a}_{{{a}_{n}}}}-{{a}_{n+3}}\ge {{a}_{{{a}_{n}}}}-{{a}_{n+l}}\ge \frac{7}{3}\left( {{a}_{n}}-n-l \right)\Rightarrow 7\left( n+l \right)\ge 4{{a}_{n}}\ge 4\left( 2n+7 \right)\Rightarrow n\le 7l-28\le 7$, противоречие. $\square$
Множество $X=\{{{x}_{1}} < {{x}_{2}} < \ldots < {{x}_{n}}\}$ назовем \textit{представимым}, если существуют $1\le i < j < k\le n$ такие, что ${{x}_{i}}+{{x}_{k}}=2{{x}_{j}}$. Обозначим $\overline{X}=\{{{x}_{i}}+{{x}_{j}}|1\le i < j\le n\}$.
Лемма 2. Если $X=\{{{x}_{1}} < {{x}_{2}} < \ldots < {{x}_{n}}\}$ непредставимое множество, то $\left| \overline{X} \right|\ge 3\left| X \right|-7$.
Доказательство. Докажем индукцией по $n$. Если $n\le 2$, то $\left| \overline{X} \right|\ge 0 > 3\left| X \right|-7$. Если $n=3$, так как ${{x}_{1}}+{{x}_{2}} < {{x}_{1}}+{{x}_{3}} < {{x}_{2}}+{{x}_{3}}$, то $\left| \overline{X} \right|=3 > 3\left| X \right|-7$. Если $n=4$, так как ${{x}_{1}}+{{x}_{2}} < {{x}_{1}}+{{x}_{3}} < {{x}_{1}}+{{x}_{4}} < {{x}_{2}}+{{x}_{4}} < {{x}_{3}}+{{x}_{4}}$, то $\left| \overline{X} \right|\ge 5=3\left| X \right|-7$. Пусть утверждение верно для всех чисел меньше $n\left( n\ge 5 \right)$. Докажем для $n$. Пусть $S=\{{{x}_{1}} < {{x}_{2}} < \ldots < {{x}_{n-1}}\}$ и $A=\{{{x}_{i}}+{{x}_{n}}|1\le i < n\}$. Предположим, что $\left| \overline{X} \right|\le 3n-8$. Тогда по предположению индукции $3n-8\ge \left| \overline{X} \right|=\left| \overline{S}\cup A \right|=\left| \overline{S} \right|+\left| A\backslash \overline{S} \right|\ge 3n-10+\left| A\backslash \overline{S} \right|\Rightarrow \left| A\backslash \overline{S} \right|\le 2$. Заметим, что ${{x}_{n-2}}+{{x}_{n-1}}$ наибольший элемент $\overline{S}$ и ${{x}_{n-2}}+{{x}_{n-1}} < {{x}_{n-2}}+{{x}_{n}} < {{x}_{n-1}}+{{x}_{n}}\Rightarrow {{x}_{n-2}}+{{x}_{n}},{{x}_{n-1}}+{{x}_{n}}\in A\backslash \overline{S}\Rightarrow {{x}_{1}}+{{x}_{n}},{{x}_{2}}+{{x}_{n}},\ldots ,{{x}_{n-3}}+{{x}_{n}}\in \overline{S}\Rightarrow $ ${{x}_{n-3}}+{{x}_{n}}={{x}_{n-2}}+{{x}_{n-1}}\Rightarrow {{x}_{n}}-{{x}_{n-1}}={{x}_{n-2}}-{{x}_{n-3}}\ne {{x}_{n-3}}-{{x}_{n-4}}$ и ${{x}_{n}}-{{x}_{n-2}}={{x}_{n-1}}-{{x}_{n-3}}\ne {{x}_{n-3}}-{{x}_{n-4}}\Rightarrow {{x}_{n-4}}+{{x}_{n}}\notin \left\{ {{x}_{n-1}}+{{x}_{n-3}},{{x}_{n-2}}+{{x}_{n-3}} \right\}\Rightarrow {{x}_{n-4}}+{{x}_{n}}\notin \overline{S}\Rightarrow \left| A\backslash \overline{S} \right|\ge 3$, противоречие. $\square$
Лемма 3. Пусть $n > 100$ и $1\le {{x}_{1}} < {{x}_{2}} < \ldots < {{x}_{n}}\le 2n-1$ — целые числа. Тогда множество $X=\{{{x}_{1}} < {{x}_{2}} < \ldots < {{x}_{n}}\}$ \textit{представимое}.
Доказательство. От противного. Пусть $B\subset X$ подмножество состоящая из всех четных элементов $X$, а $C=X\backslash B$. Пусть $\left| B \right|=m$, тогда $\left| C \right|=n-m$. Заметим, что если $x\in \overline{B}$ или $x\in \overline{C}$, то $x$ четно и $4\le x\le 4n-4\Rightarrow \overline{B}\cup \overline{C}\subset \left\{ 4,6,\ldots ,4n-4 \right\}$. По предположению множества $B$ и $C$ \textit{непредставимые}, следовательно $2{{x}_{1}},2{{x}_{2}},\ldots ,2{{x}_{n}}\notin \overline{B}\cup \overline{C}\Rightarrow \left| \overline{B}\cup \overline{C} \right|\le \left| \left\{ 4,6,\ldots ,4n-4 \right\}\backslash \left\{ 2{{x}_{1}},2{{x}_{2}},\ldots ,2{{x}_{n}} \right\} \right|\le n-1$.
По лемме 2 $\left| \overline{B}\cap \overline{C} \right|=\left| \overline{B} \right|+\left| \overline{C} \right|-\left| \overline{B}\cup \overline{C} \right|\ge 3m-7+3\left( n-m \right)-7-\left( n-1 \right)=2n-15 > \left| \overline{B}\cup \overline{C} \right|$, противоречие. $\square$
Предположим, что количество троек удовлетворяющих условию конечно, т.е. существует $M\in N$ что ${{a}_{k}}+{{a}_{m}}\ne 2{{a}_{l}}$ для любых $m > l > k > M$. По лемме 1 существует бесконечная последовательность натуральных чисел $M < {{n}_{1}} < {{n}_{2}} < \ldots $ такие, что ${{a}_{{{n}_{i}}}}\le 2{{n}_{i}}+6$ и ${{n}_{i+1}}-{{n}_{i}} > 100$ для каждого $i\in N$. Предположим, что $${{a}_{{{n}_{i+1}}}}-{{a}_{{{n}_{i}}}}\ge 2\left( {{n}_{i+1}}-{{n}_{i}} \right)+1, \quad \mbox{для любого } i\in N. \qquad (2)$$ Пусть $r > 2{{n}_{1}}-{{a}_{{{n}_{1}}}}+7$ — натуральное число. Просуммировав неравенства (2) для $i=1,2,\ldots ,r-1$ получаем, что ${{a}_{{{n}_{r}}}}-{{a}_{{{n}_{1}}}}\ge 2\left( {{n}_{r}}-{{n}_{1}} \right)+r-1\Rightarrow r\le {{a}_{{{n}_{r}}}}-2{{n}_{r}}+2{{n}_{1}}-{{a}_{{{n}_{1}}}}+1\le 2{{n}_{1}}-{{a}_{{{n}_{1}}}}+7 < r$, что невозможно. Значит ${{a}_{{{n}_{i+1}}}}-{{a}_{{{n}_{i}}}}\le 2\left( {{n}_{i+1}}-{{n}_{i}} \right)$ при каком-то $i\in N$. Обозначим $m={{n}_{i}},k={{n}_{i+1}}-{{n}_{i}} > 100$. Тогда ${{a}_{m}} < {{a}_{m+1}} < \ldots < {{a}_{m+k}}\le {{a}_{m}}+2k$, следовательно по лемме 3 множество $\left\{ {{a}_{m}},{{a}_{m+1}},\ldots ,{{a}_{m+k}} \right\}$ \textit{представимое}, противоречие.

Идея решения почти очевидна, но нужно много технических деталей

Предположим, что условие задачи неверно, тогда существует такое $N$, что ${{a}_{k}}+{{a}_{m}} \neq 2{{a}_{l}} \text{, } \forall m>l>k \geq N$

$\textbf{Утверждение 1.}$ $a_{n+8} \geq a_{n}+17 \text{, } \forall n \geq N$

Легко доказать, что $a_{n+2} \geq a_{n} + 3$, иначе найдется требуемая тройка. Теперь $a_{n+4} \geq a_{n} + 6$, но если равенство достигается, тогда $a_{n+2}-a_{n}=3$ и $a_{n+4}-a_{n+2}=3$, что также дает требуемую тройку. Но тогда $a_{n+4} \geq a_{n}+7$. Теперь, если и тут достигается равенство, то рассмотрим ряд из разностей соседних членов последовательности от $a_{n}$ до $a_{n+4}$, состоящий из $4$ членов. В таком ряду не должно быть двух подряд идущих последовательностей чисел с одинаковыми суммами, иначе требуемая тройка найдется. Заметим, что суммы первых двух и последних двух должны быть $3$ и $4$ в каком то порядке, БОО можем взять, что сначала идет $3$. Тройку можно получить только как $1$ и $2$, а четверку только как $1$ и $3$ (потому что $2$ и $2$ быть не может). $3$ может быть только в конце (иначе она равна сумме первых двух), значит на третьей позиции $1$, на второй позиции $2$ (иначе две единицы подряд), но тогда сумма чисел на второй и третьих позициях равна числу на четвертой, откуда противоречие. Значит $a_{n+4} \geq a_{n}+8$, тогда $a_{n+8} \geq a_{n}+16$, но аналогично предыдущему, можно усилить до $a_{n+8} \geq a_{n}+17$, что и требовалось

$\textbf{Утверждение 2.}$ Для всех достаточно больших $n$, $a_{n} \geq 2,1n$

Пусть существует достаточно большое $k$, что $a_{k}<2,1k$, тогда $a_{k} \geq a_{k-8m} + 17m > 17m$, $\forall m: k-8m \geq N$. Возьмем такое максимальное $m$, тогда для него $k-8m-8 < N$. Тогда $2,1k > a_{k} > 17m > \frac{17}{8}k-17-\frac{17}{8}N \Rightarrow k<const$, но мы могли выбрать $k$ сколь угодно большим

Теперь, для достаточно большого $n$, $a_n+a_{n+3} \geq a_{a_n} \geq 2,1a_{n} \Rightarrow a_{n+3} \geq 1,1a_{n}$, тогда $a_{n+30} \geq {1,1}^{10}a_{n} > (1+10*\frac{1}{10})a_{n}=2a_{n}$, то есть $a_{a_n} \leq a_{n}+a_{n+3} \leq 2a_{n+3} < a_{n+33} \Rightarrow a_n < n+33$ для достаточно больших $n$, но $a_{n} \geq 2,1n \geq n+33$ при достаточно больших $n$, что ведет к противоречию.