Раскраски

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

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