Задача
COM-B2-M05-P018 Критерий для блоков \(2\times2\)
На доске \(m\times n\), где \(m,n\ge2\), все клетки белые. За ход можно выбрать квадратный блок \(2\times2\) из соседних клеток и поменять цвет всех четырёх его клеток. Докажите, что раскраска достижима тогда и только тогда, когда в каждой строке и каждом столбце чёрных клеток чётное число.
Необходимость очевидна по паритету строк и столбцов. Для достаточности исправляйте клетки слева направо и сверху вниз.
Необходимость: один ход меняет две клетки в каждой из двух соседних строк и две клетки в каждом из двух соседних столбцов. Поэтому чётность числа чёрных клеток в каждой строке и каждом столбце сохраняется. В начале все эти чётности равны \(0\).
Докажем достаточность. Пусть целевая раскраска имеет чётные строки и столбцы. Будем строить её из белой доски. Для \(i=1,\ldots,m-1\) и \(j=1,\ldots,n-1\) идём по клеткам слева направо, сверху вниз. Если в текущий момент клетка \((i,j)\) отличается от целевой, применяем ход к блоку с левым верхним углом \((i,j)\). После этого клетка \((i,j)\) совпадает с целью, и дальнейшие ходы уже не будут её менять, потому что они начинаются не выше и не левее неё.
После такой процедуры все клетки вне последней строки и последнего столбца совпадают с целью. Остаётся проверить последнюю строку и последний столбец. В каждой строке и каждом столбце текущей доски чётность чёрных клеток чётна, и у целевой доски тоже. Поэтому в каждой уже почти заполненной строке последняя клетка вынуждена совпадать с целевой. Аналогично совпадают клетки последней строки. Значит, вся раскраска достижима.
Сложность в том, что нужен не только инвариант, но и алгоритм построения.