51-я Международная Математическая OлимпиадаКазахстан, Астана, 2010 год

Дана последовательность ${{a}_{1}}$, ${{a}_{2}}$, ${{a}_{3}}$, $\ldots $, состоящая из положительных действительных чисел. Известно, что для некоторого фиксированного целого положительного $s$ при всех $n > s$ выполняется равенство ${{a}_{n}}=\max \{{{a}_{k}}+{{a}_{n-k}}|1\le k\le n-1\}.$ Докажите, что существуют целые положительные числа $\ell $ и $N$ такие, что $\ell \le s$, и ${{a}_{n}}={{a}_{\ell }}+{{a}_{n-\ell }}$ при всех $n\ge N$.

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

Допустим это неверно. Но по условию это надо доказать, что значит, что это является верным утверждением. А значит это противоречие предположению. Поэтому это верно => доказано

Утверждение: $\ \forall \ n > s \quad \exists \ i < s \ \to \ a_n = a_i+a_{n-i}$

\[ \]

Доказательство:

\[ a_n = a_k+a_{n-k}\left ( \dfrac{n}{2} \geq k > s \right ) \ \to \ a_n = a_i+(a_{k-i} + a_{n-k})\leq a_i+a_{n-i}\leq a_n \quad \blacksquare\]

Следовательно верно что $:$

\[ \forall n \in \mathbb{N} \quad \exists \ \epsilon_i \in \mathbb{N_0} \quad \sum \limits_{i=1}^{s} \epsilon_i\cdot i = n \mid a_n = \epsilon_1 a_1 + \epsilon_2 a_2 + \dots \epsilon_s a_s \quad (\ \star \ )\]

Из $( \ \star \ )$ следует что последовательность $a_n$ дискретная.

\[ b_i = \dfrac{a_i}{i} \mid b_\ell \geq b_j \quad \forall \ 1 \leq j \leq s\]

Утверждение: $\ b_\ell \geq b_n \quad \forall \ n\in \mathbb{N}$

\[ \]

Доказательство:

\[ (\ \star \ ) \ \to \ a_n = nb_n = \sum \limits_{i=1}^{s} \epsilon_i \cdot a_i = \sum \limits_{i=1}^{s} \epsilon_i \cdot i b_i \leq b_\ell \sum \limits_{i=1}^{s} \epsilon_i\cdot i = nb_\ell \quad \blacksquare\]

Возьмем $:$

\[ c_n = na_\ell - \ell a_n =n\ell \cdot (b_\ell - b_n)\geq 0 \mid c_\ell = 0\]

Утверждение: $ \ c_n \geq c_{n+\ell} $

\[ \]

Доказательство:

\[ c_{n+\ell}=(n+\ell)a_\ell - \ell a_{n+\ell} \leq (n+\ell)a_\ell - \ell(a_n+a_\ell) = na_\ell - \ell a_n = c_n \quad \blacksquare\]

Также заметим $:$

\[ c_n = \underbrace{na_\ell - \ell a_n = \sum \limits_{i=1}^{s} \epsilon_i( ia_\ell - \ell a_i)}_{( \ \star \ )}\]

Следовательно последовательность $c_n$ также является дискретной тогда $:$

\[ S = \{ \ c_i \mid \ \forall \ n \in \mathbb{N}\ \} \ \to \ \mid S \mid \leq C\]

Утверждение: $\ \exists \ N_0 \ \to \ \forall \ n \geq N_0 \quad c_n = c_{n+\ell}$

\[ \]

Доказательство:

От обратного, допустим существует бесконечно много $: c_k > c_{k+\ell}$

\[ \mid \ S \mid \ \to \ \ \infty \ \ \to \ \ \varnothing \quad \blacksquare\]

Тогда $:$

\[ \forall \ n \geq N_0 \ \to \ c_n = c_{n+\ell} \quad \quad a_{n+\ell}=a_n+a_\ell \quad \square \]