#5 Инварианты II и моноинварианты

При одном ходе число чёрных монет либо увеличивается на \(2\), либо уменьшается на \(2\), либо не меняется. Поэтому его чётность сохраняется.

В начале число чёрных монет равно \(1\), то есть нечётно. В целевом положении оно равно \(0\), то есть чётно. Инвариант не совпадает, значит, такое положение недостижимо.

При шахматной раскраске каждое домино \(1\times2\) покрывает одну чёрную и одну белую клетку. Поэтому любая фигура, покрытая домино, содержит поровну чёрных и белых клеток.

В полной доске \(8\times8\) чёрных и белых клеток поровну. После удаления двух клеток одного цвета равенство нарушается. Значит, покрытие домино невозможно.

Будем считать \(+\) числом \(1\), а \(-\) числом \(-1\). Один ход меняет знаки у двух чисел, поэтому произведение всех трёх чисел умножается на \((-1)^2=1\).

Сначала произведение равно \(1\). Для состояния \(-,-,-\) произведение равно \(-1\). Инвариант различен, значит, такое состояние невозможно.

Каждый ход изменяет координату на число, кратное \(5\). Поэтому остаток координаты по модулю \(5\) сохраняется.

Начальная координата имеет остаток \(0\), а \(2026\equiv 1\pmod 5\). Следовательно, точка \(2026\) недостижима.

После хода размеры куч станут \(a-1\) и \(b+1\). Разность старой и новой сумм квадратов равна

\[a^2+b^2-(a-1)^2-(b+1)^2=2(a-b-1).\]

Так как \(a\ge b+2\), правая часть положительна. Значит, сумма квадратов строго уменьшается.

Обозначим числа красных, синих и зелёных камней через \(r,b,g\). При ходе, например, \(r\) и \(b\) уменьшаются на \(1\), а \(g\) увеличивается на \(2\). Разность \(r-b\) не меняется, а разности \(b-g\) и \(g-r\) меняются на кратные \(3\). Поэтому остатки всех попарных разностей по модулю \(3\) сохраняются.

В начале \(r-b=20-21=-1\), то есть \(r-b\equiv 2\pmod 3\). Если бы все камни стали одного цвета, то две из величин \(r,b,g\) были бы равны \(0\), а третья — \(63\), поэтому разности были бы кратны \(3\). Противоречие.

При замене пары \((a,b)\) на \((a-b,b)\) при \(a\ge b\) НОД не меняется: \(\gcd(a,b)=\gcd(a-b,b)\). То же верно при замене \(b\) на \(b-a\).

В начале \(\gcd(84,30)=6\). У пары \(7,7\) НОД равен \(7\). Поскольку НОД является инвариантом, такая пара недостижима.

Один ход меняет ровно два знака, значит, произведение всех знаков умножается на \((-1)^2=1\). Поэтому произведение является инвариантом.

В начале произведение равно \(-1\), так как отрицательный знак один. В состоянии, где все знаки положительны, произведение равно \(1\). Инвариант различен, значит, такое состояние недостижимо.

Раскрасим доску в шахматном порядке. Каждый ход коня переводит его на клетку противоположного цвета.

Если путь по всем \(25\) клеткам был бы замкнутым, то он образовал бы цикл нечётной длины \(25\), в котором цвета должны строго чередоваться. Но в замкнутом цикле с чередованием цветов длина должна быть чётной. Противоречие.

Рассмотрим чётность числа чёрных клеток в каждой строке. Один ход затрагивает две клетки в одной выбранной строке и две клетки в другой выбранной строке. Значит, чётность числа чёрных клеток в каждой строке сохраняется. Аналогично сохраняется чётность в каждом столбце.

В начале во всех строках и столбцах чётность равна \(0\). Если есть ровно одна чёрная клетка, то её строка и её столбец имеют нечётную чётность. Это невозможно.

Инверсией называется пара чисел, где большее стоит левее меньшего. Число инверсий — неотрицательное целое число.

Обмен соседней неправильной пары уменьшает число инверсий ровно на \(1\): эта пара перестаёт быть инверсией, а отношения этих двух чисел с остальными числами не меняют общего количества инверсий.

Значит, число инверсий строго убывает и не может убывать бесконечно. Процесс завершится.

Пусть \(S\) — сумма номеров клеток, в которых лежат камни, считая камни с кратностью. Каждый ход увеличивает \(S\) ровно на \(1\).

Если всего камней \(m\), то \(S\le mn\), потому что ни один камень не может оказаться правее \(n\)-й клетки. Значит, \(S\) строго возрастает, но ограничена сверху. Бесконечно много ходов невозможно.

Необходимость: один ход меняет два знака, поэтому чётность числа отрицательных знаков сохраняется. Если в конце отрицательных знаков \(0\), то в начале их должно быть чётное число.

Докажем достаточность. Возьмём остовное дерево графа и выберем в нём корень. Будем обрабатывать листья, кроме корня. Если в листе стоит минус, применим ход к ребру, соединяющему лист с его родителем; знак в листе станет плюсом, а знак родителя изменится. Если в листе плюс, ничего не делаем. После этого лист можно больше не трогать.

Так мы сделаем положительными все вершины, кроме, возможно, корня. Чётность числа отрицательных знаков сохранялась, а перед последним шагом вне корня отрицательных знаков нет. Поэтому корень тоже положителен. Значит, все знаки можно сделать положительными.

Нумеруем строки \(1,\ldots,10\), столбцы \(1,\ldots,14\). Пусть чёрными считаются клетки, для которых \(i+j\) нечётно. Обозначим через \(x_{ij}\) число \(0\) или \(1\), показывающее, отмечена ли клетка.

По модулю \(2\) число отмеченных чёрных клеток равно

\[\sum_{i,j}(i+j)x_{ij}=\sum_i i\sum_j x_{ij}+\sum_j j\sum_i x_{ij}.\]

В каждой строке и в каждом столбце сумма отметок нечётна, то есть равна \(1\) по модулю \(2\). Поэтому искомая чётность равна

\[\sum_{i=1}^{10} i+\sum_{j=1}^{14} j=55+105=160\equiv 0\pmod 2.\]

Значит, отмеченных чёрных клеток чётное число.

В начальной раскраске в каждой строке и каждом столбце чёрных клеток \(0\), то есть чётное число.

Один ход выбирает две строки и две колонки. В каждой выбранной строке меняются цвета ровно двух клеток, поэтому чётность числа чёрных клеток в этой строке сохраняется. В остальных строках ничего не меняется. То же рассуждение верно для столбцов.

Следовательно, после любого числа ходов все строки и столбцы сохраняют чётность \(0\).

Рассмотрим сумму квадратов размеров всех куч. Если камень перекладывается из кучи размера \(a\) в кучу размера \(b\), где \(a\ge b+2\), то вклад этих двух куч меняется с \(a^2+b^2\) на \((a-1)^2+(b+1)^2\). Как было вычислено, старая сумма больше новой на \(2(a-b-1)>0\).

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

Если в конечном состоянии две кучи отличались бы хотя бы на \(2\), ход всё ещё был бы разрешён. Значит, в конце любые две кучи отличаются не более чем на \(1\).

НОД пары не меняется при замене \((a,b)\) на \((a-b,b)\) или \((a,b-a)\), потому что общие делители сохраняются в обе стороны.

Если числа не равны, то один ход уменьшает сумму \(a+b\): большее число заменяется на положительно меньшее число. Сумма — положительное целое число, поэтому процесс не может продолжаться бесконечно.

Когда ходов больше нет, числа равны: пусть это \(c,c\). НОД всё время сохранялся, значит, \(c=\gcd(c,c)=\gcd(a,b)=d\). Итак, конечная пара равна \(d,d\).

Необходимость: один ход меняет две клетки в каждой из двух соседних строк и две клетки в каждом из двух соседних столбцов. Поэтому чётность числа чёрных клеток в каждой строке и каждом столбце сохраняется. В начале все эти чётности равны \(0\).

Докажем достаточность. Пусть целевая раскраска имеет чётные строки и столбцы. Будем строить её из белой доски. Для \(i=1,\ldots,m-1\) и \(j=1,\ldots,n-1\) идём по клеткам слева направо, сверху вниз. Если в текущий момент клетка \((i,j)\) отличается от целевой, применяем ход к блоку с левым верхним углом \((i,j)\). После этого клетка \((i,j)\) совпадает с целью, и дальнейшие ходы уже не будут её менять, потому что они начинаются не выше и не левее неё.

После такой процедуры все клетки вне последней строки и последнего столбца совпадают с целью. Остаётся проверить последнюю строку и последний столбец. В каждой строке и каждом столбце текущей доски чётность чёрных клеток чётна, и у целевой доски тоже. Поэтому в каждой уже почти заполненной строке последняя клетка вынуждена совпадать с целевой. Аналогично совпадают клетки последней строки. Значит, вся раскраска достижима.

Нумеруем строки \(1,\ldots,14\), столбцы \(1,\ldots,18\). Пусть белыми считаются клетки, для которых \(i+j\) чётно. Обозначим через \(x_{ij}\) индикатор отмеченности клетки.

Число отмеченных белых клеток по модулю \(2\) равно

\[\sum_{i,j}(1+i+j)x_{ij}.\]

Раскрывая сумму по модулю \(2\), получаем

\[\sum_{i,j}x_{ij}+\sum_i i\sum_j x_{ij}+\sum_j j\sum_i x_{ij}.\]

Общее число отмеченных клеток имеет чётность \(14\), потому что в каждой из \(14\) строк отмечено нечётное число клеток; значит, этот вклад равен \(0\). Строчные и столбцовые суммы отметок нечётны, поэтому остаётся

\[\sum_{i=1}^{14}i+\sum_{j=1}^{18}j=105+171=276\equiv0\pmod2.\]

Следовательно, отмеченных белых клеток чётное число.

Обозначим цвет клетки числом \(0\) для белой и \(1\) для чёрной. Если мы переключали строки с параметрами \(r_i\in\{0,1\}\) и столбцы с параметрами \(c_j\in\{0,1\}\), то цвет клетки \((i,j)\) равен \(r_i+c_j\pmod2\).

Для углов прямоугольника \((i,j),(i,l),(k,j),(k,l)\) сумма цветов равна

\[(r_i+c_j)+(r_i+c_l)+(r_k+c_j)+(r_k+c_l)\equiv0\pmod2.\]

Значит, чёрных углов всегда чётное число.

Докажем обратное. Пусть раскраска \(a_{ij}\) имеет это свойство. Выберем \(r_i=a_{i1}\) для каждой строки и \(c_j=a_{1j}+a_{11}\) для каждого столбца. Тогда для клетки \((i,j)\) прямоугольное условие, применённое к строкам \(1,i\) и столбцам \(1,j\), даёт

\[a_{ij}+a_{i1}+a_{1j}+a_{11}\equiv0\pmod2.\]

Отсюда \(a_{ij}=r_i+c_j\pmod2\). Значит, достаточно переключить все строки с \(r_i=1\) и все столбцы с \(c_j=1\). Раскраска достижима.