Задача
COM-B2-M05-P020 Переключение строк и столбцов
На доске \(m\times n\) все клетки белые. За ход можно выбрать строку или столбец и поменять цвет всех клеток в ней. Докажите, что достижимая раскраска имеет свойство: в углах любого прямоугольника чёрных клеток чётное число. Докажите также обратное: если раскраска обладает этим свойством, то её можно получить такими ходами.
Запишите цвет клетки как сумму по модулю \(2\) переменной строки и переменной столбца.
Обозначим цвет клетки числом \(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\). Раскраска достижима.
Это полноценный критерий достижимости, поэтому задача уровня 5.