|
|
 |
Условие
а) Из любых двухсот целых чисел можно выбрать сто чисел, сумма которых делится на 100. Докажите это.
б) Из любых 2n – 1 целых чисел можно выбрать n, сумма которых делится на n. Докажите это.
Решение
б) Лемма 1. Если утверждение задачи верно для n = a и для n = b, то оно верно и для n = ab.
Доказательство. Заметим, что свойство "сумма n целых чисел x1, ..., xn делится на n" можно формулировать и так: "среднее арифметическое чисел x1, ..., xn – целое число".
Пусть даны произвольные 2ab – 1 целых чисел. Поскольку утверждение верно при n = b и 2ab – 1 > 2b – 1, из данных 2ab – 1 чисел можно выбрать b, сумма которых делится на b. Затем из оставшихся (если их не меньше 2b – 1) выберем еще b чисел, обладающих этим свойством, и так далее. Поскольку 2ab – 1 = (2a – 1)b = (b –1), то эту операцию можно повторить 2a – 1 раз и получить 2a – 1 наборов по b чисел, в каждом из которых среднее арифметическое b чисел – целое.
Поскольку утверждение верно для n = a, из этих 2a – 1 средних арифметических можно выбрать a, сумма которых делится на a. Тогда сумма ab чисел, составляющих соответствующие a наборов по b чисел, делится на ab.
Из леммы 1 следует, что достаточно доказать наше утверждение для простых чисел.
Пусть p – простое число. Будем рассматривать все числа "по модулю p.
Лемма. Пусть даны k целых чисел b1, b2, ..., bk; 0 < k < p, 0 < bi < p для всех i = 1, 2, ..., k. Тогда из этих чисел можно составить по крайней мере k + 1 сумм, дающих различные остатки при делении на p (разрешается брать сумму "пустого множества слагаемых", которая считается равной нулю, и суммы из одного слагаемого).
Доказательство. Индукция по k. База (k = 1) очевидна: суммы дают остатки 0 и b1.
Шаг индукции. Предположим, что это утверждение верно для k < p – 1 и неверно для k + 1. Пусть суммы из k слагаемых b1, b2, ..., bk дают k + 1 различных остатков 0, s1, ..., sk. Тогда, поскольку после присоединения b = bk+1 количество различных остатков не должно увеличилось, все суммы 0 + b, s1 + b, ..., sk + b (по модулю p) содержатся во множестве {0, s1, ..., sk}.
Другими словами, если к любому элементу этого множества прибавить b, то снова получится элемент того же множества. Таким образом, это множество заведомо содержит элементы 0, b, 2b, 3b, ..., (p – 1)b. Но ясно, что все эти элементы различны (по модулю): разность ib – jb = (i – j)b, где 0 < i – j < p и 0 < b < p, не может делиться на p, поскольку p – простое.
Таким образом, множество {0, s1, ..., sk} содержит все p различных элементов. Это противоречит тому, что k + 1 < p.
Пусть a1 ≤ a2 ≤ ... ≤ a2p–1 – остатки от деления данных 2p – 1 чисел на p. Рассмотрим p – 1 чисел ap+1 – a2, ap+2 – a3, ..., a2p–1 – ap. (*)
Если какое-нибудь одно из них равно нулю, например, ap+q – aq+1 = 0, то aq+1 = aq+2 = ... = ap+q и сумма соответствующих p чисел делится на p. Осталось рассмотреть случай, когда все числа (*) отличны от нуля.
Найдём остаток x от деления суммы a1 + a2 + ... + ap на p.
Если x = 0, то все ясно.
Если x ≠ 0, то по лемме 2 можно составить из разностей (*) сумму, дающую остаток p – x при делении на p. Добавив соответствующие разности к a1 + a2 + ... + ap и проведя очевидные сокращения, мы получим сумму p слагаемых, делящуюся на p.
Замечания
Из доказанного нетрудно вывести, что утверждение "Из любых a целых чисел можно выбрать b чисел, сумма которых делится на c" верно тогда и только тогда, когда b делится на c и a ≥ b + c – 1.
