Задача 78234

Темы:    [ Принцип Дирихле ] [ Процессы и операции ] [ Раскладки и разбиения ]

Сложность: 4 Классы: 8,9,10

Условие

Число A делится на 1, 2, 3, ..., 9. Доказать, что если 2A представлено в виде суммы натуральных чисел, меньших 10,  2A = a₁ + a₂ + ... + a_k,  то из чисел a₁, a₂, ..., a_k можно выбрать часть, сумма которых равна 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).

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

олимпиада
Название	Московская математическая олимпиада
год
Номер	23
Год	1960
вариант
	1
Класс	10
Тур	2
задача
Номер	1