Олимпиадная задача о последовательности с условием суммы (Ерошкин Ю. Г
Последовательность натуральных чисел a1 < a2 < a3 < ... < an < ... такова, что каждое натуральное число либо входит в последовательность, либо представимо в виде суммы двух членов последовательности, быть может, одинаковых. Докажите, что an ≤ n² для любого n = 1, 2, 3, ...
Разобрать решение
Рассмотрим первые n – 1 членов последовательности a1, ..., an–1 (1)
и все натуральные числа, которые можно представить в виде суммы двух из этих чисел: a1 + a1, a1 + a2, ..., an + an. (2)
Общее количество чисел в (1) и (2) не превышает n – 1 + ½ n(n – 1) < n².
Таким образом, найдутся натуральные числа от 1 до n², которые не содержатся среди чисел (1) и (2). Поэтому an ≤ n².
Обсуждение
0Комментариев пока нет.
Чтобы оставить комментарий, войдите в аккаунт.