Processing math: 100%

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


Первые k членов a1, a2, , ak последовательности (an) — различные натуральные числа, а при n>k число an — наименьшее натуральное число, не представимое в виде суммы нескольких (возможно, одного) из чисел a1, a2, , an1. Докажите, что an=2an1 при всех достаточно больших n. ( А. Голованов )
посмотреть в олимпиаде

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

Комментарии от администратора Комментарии от администратора №1.     Решение. Для каждого nk рассмотрим множество всех натуральных чисел, не превосходящих a1+a2++an, и те из них, которые не являются суммами нескольких элементов множества {a1,a2,,an}, назовём {\it дырками}. Если множество дырок непусто, то an+1 — наименьшая из них, в противном случае an+1=a1+a2++an+1. Докажем, что с увеличением n на 1 количество дырок уменьшается хотя бы на 1.
Заметим, что если число tS=a1+a2++an является суммой одного или нескольких из чисел a1, a2, , an, то число St тоже является такой суммой: это сумма всех ai, не входящих в сумму, равную t.
То, что an+1 — наименьшая дырка, означает, что все числа от 1 до an+11 являются суммами нескольких из чисел a1, a2, , an. Поэтому все числа от a1++anan+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, что и требовалось доказать.

  0
4 месяца 1 дней назад #

Давайте возьмём какой то большой n так, что an>ak.

Пусть an+1=2anb  (an>bN)

Так как nный член последовательности это an, то все числа до an (т.е. 1;2;3;...;an1) могут быть представлены в виде сумм прошлых чисел. Значит anb тоже может быть представлен в виде суммы прошлых чисел, тогда 2anb=an+anb не может быть an+1

Тогда сразу поймем, что an+1=2an подходит, и так как меньшего числа нету, это единственный вариант ЧТД