Задание №176951: Турнир городов

3. [5] Пусть n – натуральное число. Назовём последовательность a , a , ..., a интересной, если
1 2 n
для каждого i = 1, 2, ..., n верно одно из равенств a = i или a = i + 1. Назовём интересную
i i
последовательность чётной, если сумма её членов чётна, и нечётной – иначе. Для каждой
нечётной интересной последовательности нашли произведение её чисел и записали его на
первый листок. Для каждой чётной – сделали то же самое и записали на второй листок. На
каком листке сумма чисел больше и на сколько? (Дайте ответ в зависимости от n.)
Алексей Глебов
Ответ: при n  0, 1 (mod 4) сумма на втором листке больше на 1, при остальных n –
наоборот. Иными словами, больше на 1 та сумма, где присутствует слагаемое 23...n(n + 1).
Решение 1. Обозначив сумму, содержащую слагаемое 23...n(n + 1), через A , а другую –
n
через B , докажем равенство A – B = 1 по индукции. База. A – B = 2 – 1 = 1.
n n n 1 1
Шаг индукции. Представим сумму A в виде A + A, где A содержит все слагаемые вида
n
a a ...a (n + 1), а A – все слагаемые вида a a ...a n. Так как сумма A содержит слагаемое
1 2 n–1 1 2 n–1
23...n(n + 1), то для каждого её слагаемого a a ...a (n + 1) последовательность a , a , ..., a
1 2 n–1 1 2 n–1
имеет ту же чётность, что и последовательность 2, 3, ..., n. Следовательно, A = (n + 1)A .
n–1
Соответственно, в сумме A для каждого её слагаемого a a ...a n чётность
1 2 n–1
последовательности a , a , ..., a противоположна чётности последовательности 2, 3, ..., n.
1 2 n–1
Тогда A = nB , откуда A = A + A = (n + 1)A + nB . Аналогично, B = nA + (n + 1)B .
n–1 n n–1 n–1 n n–1 n–1
В результате получаем: A – B = (n + 1)A + nB – nA – (n + 1)B = A – B = 1.
n n n–1 n–1 n–1 n–1 n–1 n–1
Решение 2. Рассмотрим равенство 1 = (2 – 1)(3 – 2)...(n – (n – 1))((n + 1) – n).
Раскрыв все скобки в правой части, получим сумму из 2𝑛 слагаемых со знаками плюс и
минус, каждое из которых является произведением n чисел: по одному числу из каждой скобки.
Так как в i-й скобке выбирается число i + 1 или –i, то каждое слагаемое по модулю равно

произведению чисел какой-то интересной последовательности, при этом слагаемое входит в

сумму со знаком плюс, если множитель –i выбирается в чётном числе скобок, и со знаком
минус, если в нечётном. Значит, произведения тех интересных последовательностей, которые
имеют ту же чётность, что и последовательность 2, 3, ..., n, n + 1, входят в сумму со знаком
плюс, а произведения интересных последовательностей противоположной чётности входят в
сумму со знаком минус. Отсюда следует искомое равенство.