ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 79396
Темы:    [ Индукция (прочее) ]
[ Четность и нечетность ]
[ Неравенства с модулями ]
Сложность: 4-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Автор: Ненашев С.

Натуральные числа 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+1n + 1  вытекает  1 ≤ |an − an+1|.  По предположению индукции одна из сумм
a1 ± a2 ± ... ± |an − an+1|  равна нулю. Остаётся "раскрыть модуль":  |an − an+1| = ± (an − an+1).

Замечания

В Задачнике "Кванта" задача дана в следующей формулировке.
  Даны такие натуральные числа a1, a2, ..., an, ни одно из которых не превосходит своего номера, что сумма всех их чётна. Докажите, что сумма нескольких данных чисел равна сумме остальных.

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

журнал
Название "Квант"
год
Год 1981
выпуск
Номер 6
Задача
Номер М688
олимпиада
Название Московская математическая олимпиада
год
Номер 44
Год 1981
вариант
Класс 9
задача
Номер 2

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .