В прошлой статье мы познакомились с понятием инварианта и разобрали пример с числом и учениками, где инвариантом было чередование четности. Но четность может прятаться в самых разных местах: в сумме чисел, в их количестве, в произведении и даже расположении фишек.

Сегодня разберем задачи, где инвариант не так очевиден, но стоит повнимательнее приглядеться – и решение находится само.

Немного теории

Для начала приведем здесь некоторые факты о четности суммы и произведения, которые можем найти, например, в замечательной книге Л.Э. Медникова (рекомендую ее всем, у кого, как и у меня, были сложности с четностью):

  • Общий вид чётного числа: $2n$.
  • Общий вид нечётного числа: $2n+1$ или $2n-1$.

Из определения чётного числа сразу следует, что произведение любого (целого) числа на чётное число чётно: $m\cdot2n=2(mn)$.

Несколько менее очевидно, что произведение двух нечётных чисел нечётно: $(2m+1)(2n+1)=2(2mn+m+n)+1$.

Как определить чётность суммы?

  • Сумма двух чисел разной чётности нечётна: $2m+(2n+1)=2(m+n)+1$.
  • Сумма двух чисел одинаковой чётности чётна: $2m+2n=2(m+n), (2m+1)+(2n+1)=2(m+n+1)$.

Теперь приведем наиболее общую формулировку: чётность суммы совпадает с чётностью количества нечётных слагаемых и перейдем к задачам.

Инвариант – чётность суммы

Задача 1. (для разминки). На доске записана последовательность чисел 1, 2, 3, …, 1998. За один ход разрешается стереть любые два числа и вместо них записать модуль их разности. Можно ли в конце получить число 0?

Подсчитаем сумму чисел исходной последовательности (воспользуемся формулой арифметической прогрессии):

$S_0=1+2+3+…+1998=n\cdot\frac{(a_1+a_n)}{2}=1998\cdot(1+1998)/2=999\cdot1999$.

Эта сумма оказалась нечётной. Выполняя очередное преобразование, мы заменяем сумму двух произвольных чисел на модуль из разности, а как известно, разность двух чисел имеет ту же чётность, что и их сумма, поэтому общая сумма записанных чисел останется нечётной.

Следовательно, никакими действиями получить 0 в конце мы не можем.

Задача 2. Круг разделен на 6 секторов, в каждом из которых стоит фишка. Разрешается за один ход сдвинуть любые две фишки в соседние с ними сектора. Можно ли с помощью таких операций собрать все фишки в одном секторе?

Круг, разделенный на 6 секторов

Введем круговую систему координат (пронумеруем сектора от 0 до 5, как показано на рисунке выше, это у нас будут координаты фишек). Изначальная сумма координат фишек $S_0=0+1+2+3+4+5=15$, нечётное число.

На каждом шаге можно передвигать 2 фишки. Пусть $a,b$ - координаты двух произвольно выбранных фишек. Тогда при выполнении разрешенных действий (передвигании двух фишек) их координаты изменяются на $±1$, т.е. становятся $a±1,b±1$. За дельту обозначим, на сколько изменяется сумма координат всех фишек при очередном ходе: $\Delta=[(a\pm1-a)+(b\pm1-b)]=(\pm1)+(\pm1)$. Получаем, что $\Delta$ принимает при любом ходе одно значение из набора ${-2,0,2}$ и остается чётным.

Теперь посмотрим на целевую позицию (сумму координат фишек), когда все 6 фишек собрались в секторе с номером $n$: $S_1=n+n+n+n+n+n=6\cdot{n}$. Это получается чётное число.

Делаем вывод: $S_0$ – нечётное число, целевая позиция $S_1$ – чётное число, на каждом ходу $\Delta$ не меняет чётности суммы, поэтому фишки никогда не соберутся в одном секторе.

Инвариант – чётность произведения

Прежде чем перейти к задачам, вспомним ключевой факт, на котором основано применение этого инварианта.

Знак произведения нескольких (отличных от нуля) чисел определяется чётностью количества отрицательных сомножителей:

  • Если число отрицательных сомножителей четно, то произведение положительно.

  • Если число отрицательных сомножителей нечетно, то произведение отрицательно.

Это правило позволяет в некоторых задачах заменить объекты числами $+1$ и $–1$, и следить за поведением их произведения или знака произведения.

Задача 1. На доске написаны 8 плюсов и 11 минусов. Разрешается стереть любые два знака и написать вместо них плюс, если они одинаковы, и минус, если они различны. Какой знак останется на доске после 18 таких операций?

Заменим каждый + и - на числа $+1$, $-1$. Произведение 19 чисел равно -1.

Разберем три возможные ситуации при очередном ходе:

  1. Замена двух плюсов на плюс;
  2. Замена двух минусов на минус;
  3. Замена плюса и минуса на минус.

Заметим, что каждый из таких ходов не меняет знака произведения всех чисел, а значит, он является инвариантом.

Значит, в конце, когда останется одно число, оно должно равняться –1, то есть на доске останется минус.

Задача 2. Квадрат 5×5 заполнен числами так, что произведение чисел в каждой строке отрицательно. Доказать, что найдется столбец, в котором произведение чисел также отрицательно.

Рассмотрим произведение всех чисел в квадрате, его мы можем получить, перемножив произведения строк. По условию, произведение в каждой строке отрицательно, значит, произведение всех чисел отрицательно.

С другой стороны, это же произведение можно получить, перемножив произведения столбцов.

Как было сказано выше, знак произведения определяется четностью количества сомножителей, а поскольку число столбцов является нечётным числом, то в квадрате обязательно найдется столбец с отрицательным произведением. Заметим, что их может быть 1, 3 или 5.

Задачи для самостоятельного решения

Задача 1. Имеется следующий набор чисел: $1,2,3,4,5,6$. Можно ли в нём все числа сделать равными, если разрешено неограниченное количество раз проделывать следующую операцию: прибавить к каким-то двум числам по 1.

Подсказка Следите за чётностью суммы всех фишек на каждом ходу.


Задача 2. Дано три кучки камней: в первой - 10, во второй - 15, в третьей - 20. За ход разрешается разбить любую кучку на две меньшие части; играют двое, проигрывает тот, кто не сможет сделать хода. Введите в поле ответа номер (1 или 2) того игрока, который выиграет, как бы ни играл другой игрок.

Подсказка Общее число камней -- нечётное число. Количество кучек на каждом ходу увеличивается на 1, а максимальное количество кучек -- 42 (чётное число).


Задача 3. На столе стоят 16 стаканов. Из них 15 стаканов стоят правильно, а один перевернут донышком вверх. Разрешается одновременно переворачивать любые четыре стакана. Можно ли, повторяя эту операцию, поставить все стаканы правильно?

Подсказка Следите за чётностью количества перевернутых стаканов.


Что дальше?

В следующей статье мы рассмотрим применение остатка от деления для нахождения инвариантов в задачах.