Назад
Задача

ЧислоAделится на 1, 2, 3, ..., 9. Доказать, что если 2Aпредставлено в виде суммы натуральных чисел, меньших 10,  2A=a1+a2+ ... +ak,  то из чиселa1,a2, ...,akможно выбрать часть, сумма которых равнаA.

Решение

Заметим, что  2A≥ 2·НОК(2, ..., 9) = 2·2520 > 4500.  Поэтому найдётся такое  n= 1, 2, ..., 9 , что среди наших чисел найдутся несколько, равныхn, с суммой не меньше 100 (иначе сумма всех чисел не превышает 100·(1 + ... + 9) = 4500). Отметим минимальное количество таких чиселn, обеспечивающих сумму, большую 90; поскольку среди чисел от 91 до 99 найдутся кратные любому из чисел 1, ..., 9, сумма отмеченных чисел меньше 100. Неотмеченные числа разобьём на группы поnштук так, чтобы в каждой группе все числа были равны (сумма чисел в каждой группе кратнаnи не больше 81). При этом могут остаться "лишними" не более восьми чисел каждой величины – в противном случае из них можно выделить ещё одну группу изnчисел. Общая сумма лишних и отмеченных чисел не превосходит  8·(1 + ... + 9) + 100 <A,  поэтому общая сумма чисел в группах большеA. Будем складывать эти группы, добавляя каждый раз по одной, пока сумма не превыситA. Убрав последнюю группу, мы получим (посколькуAкратноn) сумму вида  Amn,  где  0 ≤m≤ 9.  Недостатокmnможно дополнить, взявmотмеченных чисел (столько отмеченных чисел найдётся, так как их сумма больше  81 ≥mn).

Ответ

Ответ задачи отсутствует

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Комментариев нет