XIX математическая олимпиада «Шелковый путь», 2024 год

$\{a_{n}\}_{n \ge 1}$ — қатаң өспелі натурал сандар тізбегі болсын. Кез келген $n$ үшін, $a_{n}$ санын $c_{1} a_{1} + \ldots + c_{n-1} a_{n-1}$ түрінде көрсете алмайтынымыз белгілі, мұнда $c_{i} \in\{0,1\}$. Натурал $m$ саны үшін $f(m)$ арқылы $\{a_{n}\}_{n \ge 1}$ тізбегіндегі $m$-нен үлкен емес мүшелер санын белгілейік. Барлық натурал $m$ және $k$ сандары үшін $$f(m) \leq a_{k} + \frac{m}{k + 1}$$ екенін дәлелдеңіз.

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

Зафиксируем $k$ и возьмем $: a_\ell \leq m \mid a_{\ell+1} > m$

\[\color{red}{( ! )} \quad m - \ell \geq m - \dfrac{m}{k+1} - a_k \ \to \color{red}{( ! )} \ \ m \geq (\ell-a_k)(k+1) \quad ( \ \star \ )\]

Утверждение: $ S_n = \sum \limits_{t=1}^{n} a_t\ \to \ S_{k_i} + a_i \ne S_{k_j} + a_j \ ( \ \forall \ k_i\ne k_j \mid t > k_t\ )$

\[ \left ( \sum \limits_{t=\min {(k_i+1,k_j+1)}}^{\max{(k_i, k_j)}} a_t \right )+ \min{(a_i,a_j)} \ne \max{(a_i, a_j)} \quad \blacksquare\]

Тогда все они различны и $:$

\[ S^k \in \{\ S_i + a_j \mid \forall \ 1\leq i<j\leq k \ \} \cup \{\ S_i + a_j \mid \forall \ 1 \leq i < k+1 \leq j \leq \ell \ \}\]

Все элементы $S^k$ не входят в последовательность следовательно $:$

\[m+S_k - \ell \geq m+S_k - f(m+S_k)\geq \mid S^k \mid \geq \dfrac{k(k-1)}{2} + k(\ell - k)\]

Преобразим неравенство $:$

\[ m+S_k + \dfrac{k(k+1)}{2} \geq \ell(k+1) \mid (\ \star \ )\ \to \ \color{red}{( ! )} \ \ a_k(k+1) \geq S_k+\dfrac{k(k+1)}{2} \]

Что равносильно $:$

\[ a_k + \sum \limits_{t=1}^{k} a_k - a_t \geq k + \sum \limits_{t=1}^{k} a_k-a_t \geq k+ \sum \limits_{t=1}^{k} a_k-(a_k-t) = \dfrac{k(k+1)}{2} \quad \square\]