|
|
 |
Условие
Число 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) сумму вида A – mn, где 0 ≤ m ≤ 9. Недостаток mn можно дополнить, взяв m отмеченных чисел (столько отмеченных чисел найдётся, так как их сумма больше 81 ≥ mn).
