|
|
 |
Условие
Натуральные числа a1, a2, ..., an таковы, что каждое не превышает своего номера (ak ≤ k) и сумма всех чисел – чётное число.
Доказать, что одна из сумм a1 ± a2 ± ... ± an равна нулю.
Решение
Докажем это утверждение индукцией по n.
База (n = 2) очевидна, так как единственный возможный набор a1 = a2 = 1.
Шаг индукции. Возьмём удовлетворяющий условию набор a1, a2, ..., an, an+1. Если an = an+1, то сумма a1 + ... + an–1 чётна; учитывая предположение индукции, заключаем, что одна из сумм a1 ± a2 ± ... ± an–1 + an − an+1 равна нулю.
Если же an ≠ an+1, заменим данный набор набором a1, a2,..., an–1, |an − an+1|. Для нового набора выполнены все условия: число |an − an+1| имеет
ту же чётность, что и an + an+1; из an ≠ an+1, 1 ≤ an ≤ n и 1 ≤ an+1 ≤ n + 1 вытекает 1 ≤ |an − an+1|. По предположению индукции одна из сумм
a1 ± a2 ± ... ± |an − an+1| равна нулю. Остаётся "раскрыть модуль": |an − an+1| = ± (an − an+1).
Замечания
В Задачнике "Кванта" задача дана в следующей формулировке.
Даны такие натуральные числа a1, a2, ..., an, ни одно из которых не превосходит своего номера, что сумма всех их чётна. Докажите, что сумма нескольких данных чисел равна сумме остальных.
