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\]