13-я Международная Жаутыковская олимпиада, 2017 год
Комментарий/решение:
Комментарии от администратора Комментарии от администратора №1. Решение. Для каждого n≥k рассмотрим множество всех натуральных
чисел, не превосходящих a1+a2+⋯+an, и те из них, которые не являются
суммами нескольких элементов множества {a1,a2,…,an}, назовём
{\it дырками}. Если множество дырок непусто, то an+1 — наименьшая
из них, в противном случае an+1=a1+a2+⋯+an+1. Докажем,
что с увеличением n на 1 количество дырок уменьшается хотя бы на 1.
Заметим, что если число t≤S=a1+a2+⋯+an является суммой
одного или нескольких из чисел a1, a2, …, an, то число S−t
тоже является такой суммой: это сумма всех ai, не входящих в сумму, равную t.
То, что an+1 — наименьшая дырка, означает, что все числа от 1 до an+1−1
являются суммами нескольких из чисел a1, a2, …, an. Поэтому
все числа от a1+⋯+an−an+1 до a1+⋯+an тоже являются такими
суммами. Добавляя an+1, получаем, что все числа от a1+⋯+an до
a1+⋯+an+an+1 являются суммами каких-то из чисел
a1, a2, …, an+1. Таким образом, при замене n на n+1 новых
дырок не появилось, а хотя бы одна старая (собственно an+1) пропала,
что и требовалось доказать.
Следовательно, начиная с какого-то момента дырок не останется.
Итак, при всех достаточно больших n выполнено равенство
an+1=a1+⋯+an+1. Тогда an+2=a1+⋯+an+an+1+1=(a1+⋯+an+1)+an+1=2an+1, что и требовалось доказать.
Давайте возьмём какой то большой n так, что an>ak.
Пусть an+1=2an−b (an>b∈N)
Так как n−ный член последовательности это an, то все числа до an (т.е. 1;2;3;...;an−1) могут быть представлены в виде сумм прошлых чисел. Значит an−b тоже может быть представлен в виде суммы прошлых чисел, тогда 2an−b=an+an−b не может быть an+1
Тогда сразу поймем, что an+1=2an подходит, и так как меньшего числа нету, это единственный вариант ЧТД
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.