Для каких прямоугольников $latex m\times n $ на клетчатой бумаге, в клетках которых расставлены нули и единицы, можно получить из любой расстановки любую другую, если разрешается изменять числа одновременно в каждой строке, каждом столбце и на каждой прямой, параллельной диагоналями клеток (в частности, в угловых клетках)?
Решение: это всегда возможно для прямоугольников $latex m\times n $, лишь если $latex m $ и $latex n $ не больше 3. поскольку операцию можно выполнять в обратном порядке, достаточно выяснить, для каких таблиц $latex m\times n $ из любой расстановки можно получить таблицу из одних едениц.
Легко видеть, что для прямоугольников $latex 1\times n $, $latex 2\times n $ и $latex 3\times n $ заменами знаков можно получить таблицу из одних единиц: на рисунке 1 указан порядок, в котором нули, стоящие в некоторых клетках, можно заменить на единицы(цветные линии показывают какой именно — вертикальный или диагональный — «ход» следует делать).
С другой сторны, в прямоугольнике $latex m\times n $, где m и n не меньше 4, можно выделить фигуру из восьми клеток, показанных на рисунке 2 штриховкой; четность количества единиц не меняется в этих клетках при всех разрешенных преобразованиях — является, как говорят, инвариантом. Таким образом, если в одной из таких фигур стоит нечетное число единиц, то прийти к таблице заполненной единицами, невозможно.
Представляем читателям выяснить, образуют ли такие таблицы из 8 клеток полную систему инвариантов, также следует ли из четности количества единиц в каждой из них возможность преобразовать таблицу в состояние «все единицы», а заодно выяснить, сколько существует классов (неэквивалентных друг другу) таблиц относительно разрешенных в условии преобразований.
А.Галочкин
