13-я Международная Жаутыковская олимпиада, 2017 год

Первые $k$ членов $a_1$, $a_2$, $\ldots$, $a_k$ последовательности $(a_n)$ — различные натуральные числа, а при $n > k$ число $a_n$ — наименьшее натуральное число, не представимое в виде суммы нескольких (возможно, одного) из чисел $a_1$, $a_2$, $\ldots$, $a_{n-1}$. Докажите, что $a_n=2a_{n-1}$ при всех достаточно больших $n$. ( А. Голованов )

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

Комментарии от администратора Комментарии от администратора №1.     Решение. Для каждого $n\geq k$ рассмотрим множество всех натуральных чисел, не превосходящих $a_1+a_2+\dots+a_n$, и те из них, которые не являются суммами нескольких элементов множества $\{a_1, a_2, \ldots, a_n\}$, назовём {\it дырками}. Если множество дырок непусто, то $a_{n+1}$ — наименьшая из них, в противном случае $a_{n+1}=a_1+a_2+\dots+a_n+1$. Докажем, что с увеличением $n$ на 1 количество дырок уменьшается хотя бы на 1.
Заметим, что если число $t\leq S=a_1+a_2+\dots +a_n$ является суммой одного или нескольких из чисел $a_1$, $a_2$, $\ldots$, $a_n$, то число $S-t$ тоже является такой суммой: это сумма всех $a_i$, не входящих в сумму, равную $t$.
То, что $a_{n+1}$ — наименьшая дырка, означает, что все числа от 1 до $a_{n+1}-1$ являются суммами нескольких из чисел $a_1$, $a_2$, $\ldots$, $a_n$. Поэтому все числа от $a_1+\dots+a_n-a_{n+1}$ до $a_1+\dots+a_n$ тоже являются такими суммами. Добавляя $a_{n+1}$, получаем, что все числа от $a_1+\dots+a_n$ до $a_1+\dots+a_n+a_{n+1}$ являются суммами каких-то из чисел $a_1$, $a_2$, $\ldots$, $a_{n+1}$. Таким образом, при замене $n$ на $n+1$ новых дырок не появилось, а хотя бы одна старая (собственно $a_{n+1}$) пропала, что и требовалось доказать.
Следовательно, начиная с какого-то момента дырок не останется.
Итак, при всех достаточно больших $n$ выполнено равенство $a_{n+1}=a_1+\dots+a_n+1$. Тогда $a_{n+2}=a_1+\dots+a_n+a_{n+1}+1= (a_1+\dots+a_n+1)+a_{n+1}=2a_{n+1},$ что и требовалось доказать.