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

Проект МЦНМО
при участии
школы 57
Задача 116700
Темы:    [ Геометрическая прогрессия ]
[ Индукция (прочее) ]
[ Числовые неравенства. Сравнения чисел. ]
Сложность: 4+
Классы: 11
В корзину
Прислать комментарий

Условие

Для  n = 1, 2, 3  будем называть числом n-го типа любое число, которое либо равно 0, либо входит в бесконечную геометрическую прогрессию
1,  (n + 2),  (n + 2)²,  ..., либо является суммой нескольких различных её членов. Докажите, что любое натуральное число можно представить в виде суммы числа первого типа, числа второго типа и числа третьего типа.


Решение 1

  Пусть  a1, a2, a3, ...  – неубывающая последовательность натуральных чисел. Для  k ≥ 2  обозначим через  Sk = a1 + ... + ak–1  сумму  k – 1  первых членов этой последовательности и положим  S1 = 0.
  Докажем, что каждое натуральное число представимо в виде суммы различных членов последовательности {ak} тогда и только тогда, когда для любого k выполнено неравенство   akSk + 1   (*).
  Действительно, если  ak > Sk + 1,  то натуральное число  Sk + 1  нельзя представить в требуемом виде.
  Для проверки достаточности докажем по индукции, что любое натуральное число от 1 до Sk включительно можно представить в требуемом виде, используя только члены  a1, a2, ..., ak–1.
  База. Из неравенства  a1 S1 + 1 = 1  следует, что  a1 = 1,  S2 = a1 = 1  и для  k = 2  утверждение верно.
  Шаг индукции. Без использования ak мы, по индукционному предположению, можем получить все числа от 1 до Sk. Добавляя  ak к этим числам, мы сможем получить все натуральные числа от  ak + 1  до  ak + Sk = Sk+1,  и само ak также представимо в нужном виде. Отрезки  [1, Sk]  и  [ak, Sk+1]  покрывают все натуральные числа от 1 до Sk+1.

  В исходной задаче последовательность {ak}, состоит из членов геометрических прогрессий 1, 3, 3², 3³, ..., 1, 4, 4², 4³, ... и 1, 5, 5², 5³, ..., расположенных в порядке неубывания: 1, 1, 1, 3, 4, 5, 9, 16, 25, 27, ...
  Проверим неравенство (*). Для  k = 1, 2, 3  оно выполнено ввиду  a1 = a2 = a3 = 1.  Пусть для  k > 3  сумма Sk состоит ровно из n членов первой геометрической прогрессии (от 30 до 3n–1), m – второй (от 40 до 4m–1) и l – третьей (от 50 до 5l–1). Тогда следующее число последовательности ak равно минимальному из чисел 3n, 4m, 5l. Имеем  


Решение 2

  Индукция. База. Непосредственной проверкой убедимся в том, что для чисел 1, 2, ..., 9 доказываемое утверждение верно.
  Шаг индукции. Пусть  N > 9.  и для всех натуральных чисел, меньших N, утверждение уже доказано.
  Пусть 3k, 4l и 5m – наибольшие из членов указанных в условии трёх прогрессий, не превосходящие N. Если  N < 2·3k,  то  N – 3k < 3k.  Число  N – 3k  можно по предположению индукции представить в виде суммы чисел трёх типов. Прибавляя к числу первого типа 3k, мы (поскольку  N – 3k < 3k)  получим новое число первого типа, сумма которого с прежними числами второго и третьего типов будет равна N. Аналогично можно получить представление числа N в виде суммы чисел трёх типов, когда  N < 2·4l  или  N < 2·5m.
  Пусть теперь  N ≥ max {2·3k, 2·4l, 2·5m}.  Обозначим через a, b и c соответственно наибольшее, среднее и наименьшее из чисел 3k, 4l и 5m. Тогда
N/2abc  и  Nab > 0.  Если  N – a – b < c,  то, представляя число  N – a – b  в виде суммы чисел трёх типов и добавляя к соответствующим слагаемым числа a и b, мы получим нужное представление числа N. Если же  Na – b ≥ c,  то или  N = a + b + c  (и требуемое представление уже получено), или  N – a – b – c > 0.  В последнем случае либо  N – a – b – c < c  (и тогда требуемое представление числа N можно получить из представления в виде суммы для числа  N – a – b – c),  либо  N – a – b – c ≥ c.
  Так как  3k+1 > N,  4l+1 > N  и  5m+1 > N,  то  c > N/5,  и в последнем случае

     N – a – b – c ≥ c > N/5 > N/6 ≥ 3k–1   и   N – a – b – c < N – N/3N/4N/5 < 2N/9 < 2· 3k–1.

  Итак,  0 < N – a – b – c – 3k–1 < 3k–1 . Представив  N – a – b – c – 3k–1  в виде суммы чисел трёх типов и добавив затем к первому числу  3k–1 + 3k,  ко второму – 4l, а к третьему – 5m, получим требуемое представление для числа N.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 75
Год 2012
класс
Класс 11
задача
Номер 5

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

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