Олимпиадная задача о натуральных числах и нулевой сумме от Ненашева
Натуральные числа 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).
Обсуждение
0Комментариев пока нет.