ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 73697
Темы:    [ Принцип Дирихле (прочее) ]
[ Классическая комбинаторика (прочее) ]
Сложность: 3+
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Последовательность натуральных чисел  a1 < a2 < a3 < ... < an < ...  такова, что каждое натуральное число либо входит в последовательность, либо представимо в виде суммы двух членов последовательности, быть может, одинаковых. Докажите, что  ann²  для любого  n = 1, 2, 3, ...


Решение

  Рассмотрим первые  n – 1  членов последовательности   a1, ..., an–1     (1)
и все натуральные числа, которые можно представить в виде суммы двух из этих чисел:   a1 + a1a1 + a2,  ...,  an + an.     (2)
Общее количество чисел в (1) и (2) не превышает  n – 1 + ½ n(n – 1) < n².
  Таким образом, найдутся натуральные числа от 1 до n², которые не содержатся среди чисел (1) и (2). Поэтому  ann².

Замечания

Мы фактически доказали, что  an  ≤ ½ n(n + 1).
Возможность более точной оценки см. в решениях Задачника "Кванта".

Источники и прецеденты использования

журнал
Название "Квант"
год
Год 1972
выпуск
Номер 9
Задача
Номер М162

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .