Республиканская олимпиада по математике, 2017 год, 11 класс


Бесконечная, строго возрастающая последовательность $\left\{ {{a}_{n}} \right\}$ натуральных чисел удовлетворяет условию ${{a}_{{{a}_{n}}}}\le {{a}_{n}}+{{a}_{n+3}}$, при всех $n\ge 1$. Докажите, что существуют бесконечно много троек $\left( k,l,m \right)$ натуральных чисел таких, что $k < l < m$ и ${{a}_{k}}+{{a}_{m}}=2{{a}_{l}}$. ( Сатылханов К. )
посмотреть в олимпиаде

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

Комментарии от администратора Комментарии от администратора №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{представимое}, противоречие.