Переключения рядов

Квант 2017, №3 с. 40-45 Тег DI3H

МАТЕМАТИЧЕСКИЙ КРУЖОК

Переключения рядов

Е.БАКАЕВ

Начнем с такой задачи которую разумно рассматривать, это $2 \times 2$ . Выясним, какие ее заполнения из каких можно получить. Всего существует $2^{4} = 16$ способов заполнить клетки таблицы $2 \times 2$ плюсами и минусами. Можно все их рассмотреть и составить схему (граф). Два заполнения будем соединять линией (ребром), если одно можно получить из другого одним переключением ряда (рис.2).

Задача 1. Все клетки таблицы $8 \times 8$ заполнены плюсами и минусами (по одному знаку в клетке). Одной операцией разрешается выбрать любой ряд (строку или столбец) и в каждой из его клеток поменять знак на противоположный. Сначала все знаки были плюсами. Может ли после нескольких таких операций оказаться, что в таблице ровно один минус? На рисунке 1 показан пример проведения такой операции.

Рис. 1

Мы не только решим эту задачу, но и вообще разберемся, какие таблицы из каких можно получить с помощью этих операций. Строки и столбцы будем называть рядами. Операцию, описанную в задаче 1, будем называть переключением ряда.

Таблица $2 \times 2$

Вместо того чтобы решать задачу про таблицу $8 \times 8$ , разберемся сначала с таблицей маленького размера, для которой все возможные варианты перекрашивания можно перебрать вручную. Наименьшая таблица,

К задачам в статье даны решения, но стоит самостоятельно подумать над задачей перед тем, как читать ее решение, – это принесет больше пользы. Также в статье даны упражнения, они зачастую проще задач, их тоже стоит решать, это может помочь разобраться с последующим материалом. Ответы и указания к упражнениям даны в конце номера.

Рис. 2

Видно, что все заполнения разбились на две группы (две компоненты связности графа): заполнения одной группы нельзя получить из заполнений другой. Что общего у заполнений каждой группы? Чем отличаются заполнения разных групп? Можно заметить, что в заполнениях одной группы четное количество плюсов, а в заполнениях другой – нечетное. Это можно доказать и не перебирая все варианты заполнений. Действительно, каждым ходом мы меняем два знака, т.е. либо 2 плюса меняем на 2 минуса, либо 2 минуса меняем на 2 плюса, либо количество плюсов и минусов не меняется. Значит, количество плюсов при переключениях рядов сохраняет свою четность.

Упражнение 1. На столе стоят 5 стаканов донышком вверх. Разрешается одновременно переворачивать любые 2 стакана. Можно ли, повто-

КВАНТ 2017/№3

ряя эту операцию, поставить все стаканы правильно?

Четность количества плюсов

С таблицами $2 \times 2$ полностью разобрались. Аналогичные соображения помогут в решении задачи 1. Действительно, и в этом случае четность количества плюсов во всей таблице не будет меняться. Докажем это. Пусть в каком-то ряду x плюсов, тогда после его переключения в этом ряду станет 8 – x плюсов, а во всей остальной таблице плюсы останутся на месте. Но числа x и 8 – x одной четности. Значит, четность количества плюсов во всей таблице не поменяется – она является инвариантом. (Инвариантом называют свойство, которое не меняется при заданных преобразованиях.) Итак, сначала в таблице было 64 плюса, значит, их количество всегда будет четным и не сможет стать равным 63. Задача 1 решена.

ных клетках – плюсы. Можно ли с помощью переключений рядов добиться того, чтобы все знаки стали плюсами? Работает ли для них решение, аналогичное решению первой задачи? Нет: в задаче 2 каждый раз меняется 3 знака, значит, четность количества плюсов каждый раз меняется и может оказаться любой. В задаче 3 четность количества плюсов действительно является инвариантом, но это не дает противоречия – в начальном и конечном положениях их четность одинаковая. Как же решать задачу 2? Посмотрим на начальное и конечное положения (рис.3). Предположим, что из одного можно получить другое.

Рис. 3

Упражнения

На столе стоят 15 стаканов донышком вверх. Разрешается одновременно переворачивать любое четное количество стаканов. Можно ли, повторяя эту операцию, поставить все стаканы правильно? 3. Из таблицы А переключениями рядов получили таблицу Б. Докажите, что из таблицы Б переключениями рядов можно получить таблицу А. 4. Таблицу $8 \times 8$ заполнили плюсами и минусами, после чего сделали несколько переключений рядов. а) Может ли оказаться, что конечное заполнение таблицы знаками отличается от начального ровно в одной клетке? б) Могут ли конечное и начальное заполнения отличаться во всех клетках? в) Можно ли из заполнения одними плюсами получить «шахматную раскраску», т.е. такое заполнение, в котором любые два соседних по стороне знака различны?

Рассмотрим еще две задачи, похожие на первую. Задача 2. В таблице $3 \times 3$ в одной угловой клетке стоит минус, а в остальных стоят плюсы. Можно ли с помощью переключений рядов добиться того, чтобы все знаки стали плюсами? Задача 3. В таблице $8 \times 8$ в четырех угловых клетках стоят минусы, в осталь-

Рассмотрим левую верхнюю клетку. В ней был минус, а должен оказаться плюс. Значит, ее надо поменять нечетное количество раз. Знак меняется, когда переключается один из двух рядов, на пересечении которых он находится, поэтому один из рядов должен быть изменен нечетное количество раз, а другой – четное. Благодаря симметричности ситуации можно считать, что нечетное количество раз переключали строку, а четное количество раз – столбец (рис.4,а).

Рис. 4

Рассмотрим теперь средний знак в верхнем ряду. Он был плюсом и должен им и остаться. Значит, его надо поменять четное количество раз. Но первая строка меняется нечетное количество раз, а значит, второй столбец – тоже нечетное количество раз. Рассуждая аналогично, но рассмотрев теперь среднюю клетку первого столбца, можно сделать вывод, что вторая строка изменяется четное количество раз (рис.4,б).

МАТЕМАТИЧЕСКИЙ

Но тогда средний столбец и средняя строка изменятся в совокупности нечетное количество раз, значит, центральный знак таблицы поменяется нечетное количество раз и станет минусом, а не плюсом (рис.4,в). Получили противоречие – из одного положения нельзя получить другое переключениями рядов. Задача 2 решена. Заметим, что для получения противоречия нам достаточно было рассмотреть 4 знака, образующих квадрат $2 \times 2$ , а знаки в остальных клетках для решения были не важны. Вспомним, что при переключениях рядов в квадрате $2 \times 2$ четность количества плюсов в нем не меняется, потому что каждый раз меняется по 2 знака. Но это верно и для квадрата $2 \times 2$ , выделенного внутри большего квадрата! Соответственно, решение задачи 2 можно изложить короче, рассмотрев квадрат $2 \times 2$ (см. рис.4,в) и заметив, что четность количества плюсов в нем является инвариантом.

Упражнение 5. Убедитесь в том, что задача 3 решается аналогично.

Некоторые задачи решаются с помощью такого же, казалось бы, незамысловатого инварианта, как в задачах 2 и 3 (четность количества плюсов), но догадаться, для какой именно области (в нашем случае это был некоторый квадрат $2 \times 2 )$ такой инвариант работает, бывает непросто. Такие задачи можно найти в статье Ю.Ионина, Л.Курляндчика «Поиск инварианта» в «Кванте» №2 за 1976 год, смотрите также дополнительные задачи 2 и 3 в конце этой статьи.

Упражнения

В таблице $8 \times 8$ изначально все знаки были плюсами. Затем сделали несколько переключений рядов. Сколько плюсов может оказаться на главной диагонали после нечетного количества операций? 7. В таблице $8 \times 8$ изначально все знаки были плюсами. Затем сделали несколько переключений рядов, после чего часть знаков скрыли. а) Некоторые знаки известны (рис.5,а). Найдите знаки, отмеченные знаками вопроса. б) Аналогичный вопрос для таблицы на рисунке 5,б. в) Некоторые знаки известны (рис.5,в). Можно ли по этой информации выяснить, четное или нечетное количество операций было сделано? г) Некоторые знаки известны (рис.5,г). Найдите знак, отмеченный знаком вопроса.

КРУЖОК

Рис. 5

Количество действий

Как мы уже выяснили, знак в клетке поменяется, только если операций, содержащих эту клетку, было сделано нечетное количество. Отсюда следует, во-первых, что порядок операций не влияет на результат. Во-вторых, имеет значение только четность количества таких операций, т.е. результат не поменяется, например, если менять ряд не 13 раз, а 1 раз. Значит, можно считать, что каждый ряд можно либо вообще не переключать, либо переключить один раз, а переключать его большее количество раз бессмысленно. Получается, что если какое-то заполнение таблицы $n \times n$ возможно получить из другого, то это можно сделать не более чем за 2n операций (так как всего рядов 2n). Но верна и более сильная оценка. Задача 4 (А.Канель-Белов, XXXIII Турнир городов, 2012 г.). В клетках таблицы $n \times n$ стоят плюсы и минусы. За один ход разрешается в произвольной строке или в произвольном столбце поменять все знаки на противоположные. Известно, что из начальной расстановки можно получить такую, при которой во всех ячейках стоят плюсы. Докажите, что этого можно добиться не более чем за n ходов. Мы уже показали, что всегда можно уложиться в 2n ходов. Но когда нам может понадобиться ровно 2n ходов? Когда мы переключили каждый ряд по одному разу. Но тогда каждый знак поменяется 2 раза, ведь менялись его строчка и его столбец. А значит, заполнение таблицы останется прежним, поэтому его можно было получить быстрее – не делая ни одного хода! Таким

КВАНТ 2017/№3

образом, мы доказали, что 2n ходов делать излишне. Идем дальше. Когда может понадобиться ровно 2n – 1 ходов? Когда переключали все ряды, кроме одного. Тогда знаки этого ряда поменяются по 1 разу, а остальные знаки – по 2 раза. Опять же, такое заполнение можно было получить быстрее – достаточно переключить только один ряд, который мы не переключали. Но то же можно сделать и в других случаях! Предположим, что мы переключили какие-то x рядов. Если переключать не эти ряды, а все остальные, то ходов станет 2n – x, а результат не поменяется (если знак менялся 2 раза, то теперь не будет меняться; если не менялся, то он будет меняться 2 раза; если знак менялся 1 раз, то он и сейчас поменяется 1 раз). Соответственно, если ходов было больше n, то после такой «инверсии» наших действий мы получим тот же результат меньше чем за n действий. Задача 4 решена.

Упражнение 8. Можно ли усилить оценку в задаче 4? Иными словами, всегда ли желаемого можно добиться не более чем за n – 1 ходов?

Критерий реализуемости

Вернемся к вопросу, какие заполнения из каких можно получить. Будем называть заполнение реализуемым, если его можно получить с помощью переключений рядов из заполнения, в котором все знаки – плюсы. При решении задачи 2 мы уже выяснили, что если в заполнении есть квадрат $2 \times 2$ , в котором нечетное количество плюсов, то оно не реализуемое. Вместо квадрата $2 \times 2$ можно рассматривать любые 4 клетки, являющиеся вершинами прямоугольника со сторонами, параллельными сторонам таблицы (пример таких четырех клеток – на рисунке 5,а). В таких четырех клетках четность количества плюсов также не меняется, так что если изначально они все были плюсами, то среди них всегда будет четное количество плюсов. Значит, если найдутся такие 4 клетки, в которых стоит нечетное количество плюсов, то заполнение не реализуемое. Но если они не найдутся, значит ли это, что оно реализуемое? Да, оказывается, что верен следующий критерий реализумости. Равносильны та-

кие три свойства заполнения (т.е. если одно из этих свойств выполняется, то выполняются и два других): 1) оно реализуемо; 2) в любом квадрате $2 \times 2$ четное количество плюсов; 3) в любых 4 клетках, являющихся вершинами прямоугольника со сторонами, параллельными сторонам таблицы, четное количество плюсов. Второе свойство прямо следует из третьего, ведь квадрат $2 \times 2$ – частный случай такого прямоугольника. Как из первого свойства следуют второе и третье, мы уже показали. Для завершения доказательства равносильности трех свойств покажем, как из второго следует первое. Рассмотрим произвольное заполнение, для которого выполняется второе свойство: в нем в любом квадрате $2 \times 2$ четное количество плюсов. Докажем, что оно реализуемо, т.е. покажем, что переключениями рядов его можно привести к ситуации, когда все знаки – плюсы. Сделаем такие пере- Рис. 6 ключения рядов, чтобы все знаки первого столбца и первой строки стали плюсами. Смотрите пример на рисунке 6.

Упражнение 9. Докажите, что такие переключения всегда можно сделать.

Теперь докажем, что после таких переключений и все остальные знаки таблицы стали плюсами. В любом квадрате $2 \times 2$ по-прежнему четное количество плюсов, так как переключения рядов не нарушают этого свойства. Теперь рассмотрим левый верхний квадрат $2 \times 2$ (рис.7,а). Три его знака – плюсы,

Рис. 7

значит и четвертый – плюс. Рассмотрим следующий квадрат $2 \times 2$ , сдвинувшись на клетку вправо (рис.7,б), для него ситуация аналогична. Рассматривая последовательно все такие квадраты, получим, что все знаки таблицы – плюсы.

МАТЕМАТИЧЕСКИЙ

Упражнения

Равносильность второго и третьего свойств можно доказать, не используя ни первое свойство, ни переключения знаков вообще. Попробуйте это сделать. 11. В одной из строк реализуемого заполнения таблицы $8 \times 8$ стоит x плюсов. Докажите, что в каждой строке этого заполнения x или 8 – x плюсов. 12. Рассмотрим некоторое реализуемое заполнение таблицы $8 \times 8$ . Пусть в одной из его строк x минусов, а в одном из столбцов – y минусов, причем на их пересечении стоит плюс. Сколько всего минусов в этом заполнении? 13. Существует ли реализуемое заполнение таблицы $8 \times 8$ , в котором ровно 6 плюсов?

Количество реализуемых заполнений

Заполним первую строку и первый столбец таблицы $m \times n$ произвольным образом. Тогда: во-первых, оставшиеся клетки можно заполнить так, чтобы заполнение было реализуемым; во-вторых, это можно сделать единственным образом.

Упражнение 14. Докажите эти утверждения. Указание. Используйте критерий реализуемости и результат упражнения 9.

Таким образом, количество способов заполнить таблицу плюсами и минусами так, чтобы заполнение было реализуемым, равно количеству способов заполнить произвольным образом ее первую строку и первый столбец. В первой строке и первом столбце таблицы $m \times n$ в совокупности m + n – 1 клеток, значит, реализуемых заполнений такой таблицы существует $2 m + n - 1$ .

Графы заполнений

В разделе про таблицу $2 \times 2$ мы строили граф, в котором ребром соединялись вершины, соответствующие таким заполнениям таблицы, которые можно получить друг из друга одним переключением ряда. Можно рассмотреть такой же граф, но для таблицы $m \times n$ (в нем $2^{mn}$ вершин). Каждое заполнение принадлежит какойто компоненте связности этого графа. Два заполнения относятся к одной компоненте, если одно можно получить из другого переключениями рядов.

КРУЖОК

Упражнения

Сколько заполнений в компоненте связности, в которой находится заполнение, где все знаки – плюсы? 16. Сколько в этом графе компонент связности и сколько в каждой из них заполнений? Указание. Любое заполнение можно привести переключениями рядов к заполнению, в котором в первой строке и первом столбце все знаки – плюсы. При этом не поменяется четность количества плюсов в любых 4 клетках, являющихся вершинами прямоугольника со сторонами, параллельными сторонам таблицы.

Нахождение количества реализуемых заполнений составляет пункт б) задачи М665 «Задачника «Кванта». Ее решения смотрите в «Кванте» №9 за 1981 год.

Вспомогательные переключения знаков

В условии следующей задачи ничего не говорится об операциях, меняющих знаки, тем не менее можно рассмотреть такие операции, и тогда задачу поможет решить критерий реализуемости. Задача 5 (Е.Бакаев, XXXIV Турнир городов, 2012 г., М2289). В некоторых клетках квадрата $11 \times 11$ стоят плюсы, причем всего плюсов четное количество. В каждом квадратике $2 \times 2$ тоже четное число плюсов. Докажите, что четно и число плюсов в 11 клетках главной диагонали квадрата. Для таблицы из этой задачи выполняется второе свойство, а значит, ее заполнение реализуемо. Тогда можно рассмотреть последовательность переключений рядов, которые позволяют получить данное заполнение из заполнения одними плюсами. Рассмотрим количество плюсов во всей таблице. Каждое переключение ряда меняет 11 знаков, а значит, меняет четность количества плюсов во всей таблице. Раз по условию плюсов во всей таблице четное количество, а изначально число плюсов $11^{2} = 121$ – нечетно, то операций было нечетное количество. Каждая операция меняет один знак на диагонали и, тем самым, меняет четность числа плюсов на диагонали. Раз плюсов изначально было 11, а операций было нечетное количество, то на диагонали будет четное количество плюсов.

Упражнение 17. Решите задачу 5 по-другому, не рассматривая операции смены знаков.

КВАНТ 2017/№3

Попробуйте решить с помощью вспомогательного переключения рядов следующую задачу.

Упражнение 18 (В.Произволов, XXIII Всесоюзная олимпиада, М1181). На шахматной доске расставлены 8 ладей так, что они не бьют друг друга. Докажите, что на черных полях расположено четное число ладей.

Стертые знаки

Как мы уже выяснили, по m + n – 1 знакам таблицы можно восстановить остальные, если известно, что заполнение реализуемо. Например, это можно сделать по знакам одной строки и одного столбца. Но m + n – 1 знаков, по которым можно восстановить реализуемое заполнение, могут быть расположены иначе, в чем можно убедиться, решив упражнение 19.

Упражнения

Докажите, что все неизвестные знаки заполнения на рисунке 5,г восстанавливаются однозначно. 20. По любым ли 50 знакам таблицы $8 \times 8$ заполнение восстанавливается однозначно?

Итак, при некоторых расположениях m + n – 1 известных знаков по ним можно однозначно восстановить остальные знаки. Но верно ли, что это наименьшее необходимое количество знаков? Да, верно, и именно об этом была задача 15 Конкурса имени А.П.Савина (см. «Квант» №1 за 2017 г.). Задача 6. Петя нарисовал таблицу $10 \times 10$ и заполнил все ее клетки плюсами. Затем он сделал несколько действий по следующему правилу. Каждым действием он наугад выбирал ряд (строку или столбец) и менял каждый из 10 его знаков на противоположный (плюс на минус, минус на плюс). Когда после этого Петя вышел, хулиган Вася часть знаков стер – осталось только N знаков. Для какого наименьшего N может оказаться, что получившуюся у Пети таблицу можно однозначно восстановить по оставшимся данным? Приведем решение более общего случая – для таблицы $m \times n$ . Ответ: m + n – 1 (соответственно, для таблицы $10 \times 10$ ответ: 19). Итак, осталось доказать, что если известно меньше m + n – 1 знаков, то заполнение нельзя однозначно восстановить.

Рассмотрим граф, в котором вершины соответствуют рядам (всего m + n вершин) и две вершины соединены ребром в том и только в том случае, когда на пересечении этих двух рядов стоит известный знак. В этом графе m + n вершин, а ребер столько же, сколько известных знаков, значит, их меньше m + n – 1. Из такого соотношения количества вершин и ребер можно сделать вывод, что граф несвязный. Рассмотрим одну из компонент связности, назовем все ее вершины (и все соответствующие им ряды) красными, а все остальные вершины (и их ряды) – синими. Предположим, что по известным знакам получилось однозначно восстановить все заполнение. Рассмотрим его. Последовательно переключим знаки в каждом из красных рядов. Каждый известный знак стоит либо на пересечении двух синих рядов, либо двух красных, значит, при такой последовательности действий каждый известный знак либо не поменяется вообще, либо поменяется 2 раза, в любом случае он останется прежним. При этом заполнение не осталось прежним, так как каждый знак, стоящий на пересечении красного и синего рядов, поменялся. Таким образом, мы получили другое заполнение, в котором известные знаки точно такие же. Значит, заполнение нельзя однозначно восстановить по известным знакам. Разным задачам с такой идеей решения (рассмотрение вспомогательного графа и использование его связности или несвязности) посвящена статья П.Кожевникова, А.Шаповалова «Свяжитесь с графом» в «Кванте» №4 за 2014 год. Рассмотрим теперь похожую задачу М112 «Задачника «Кванта». Задача 7. В таблице размером $m \times n$ записаны числа так, что для любых двух строк и любых двух столбцов сумма чисел в двух противоположных вершинах образуемого ими прямоугольника равна сумме чисел в двух других его вершинах. Часть чисел стерли, но по оставшимся можно восстановить стертые. Докажите, что осталось не менее (n + m – 1) чисел. В задаче 6 речь шла о реализуемом заполнении, а значит, в нем во всех таких же четверках клеток, стоящих на пересечении 2 строк и 2 столбцов, количество плюсов четно. Здесь же не идет речь о перекрашивани-

МАТЕМАТИЧЕСКИЙ

ях или о плюсах и минусах, но снова накладывается условие на все такие четверки клеток. Попробуем решить эту задачу аналогично. Рассмотрим такой же несвязный граф. Снова назовем вершины одной компоненты красными, а все остальные синими. В предыдущей задаче речь шла о переключениах рядов, здесь же ни о каких операциях в условии не сказано, но мы сами можем ввести некоторые вспомогательные операции с рядами. Что мы хотим от этих операций? Хотим, чтобы числа в клетках на пересечении одноцветных рядов не поменялись, а на пересечении разноцветных – поменялись. При этом операция не должна нарушать то свойство, что для любых двух строк и любых двух столбцов сумма чисел в двух противоположных вершинах образуемого ими прямоугольника равна сумме чисел в двух других его вершинах. Например, подойдет такая операция: для столбца – все числа в столбце увеличиваем на 1, а для строки – все числа в строке уменьшаем на 1. Несложно проверить, что эта операция удовлетворяет необходимым требованиям. Следовательно, проведя по одной такой операции с каждым красным рядом, получим таблицу, в которой известные знаки те же, а некоторые неизвестные поменялись. Значит, таблицу нельзя восстановить однозначно, зная менее n + m – 1 чисел. Эта задача – о единственности решения системы линейных уравнений. Другое решение этой задачи, как раз использующее линейную алгебру, приведено в «Кванте» №8 за 1972 год. Предыдущая задача – это, по сути, та же задача, но вместо привычных линейных уравнений – сравнения по модулю 2. Этому подходу (рассмотрению задач про переключение знаков с точки зрения линейной алгебры) посвящена статья В.Дорофеева, А.Спивака «Раскраски графов и линейные уравнения» в «Кванте» №4 за 2011 год. Рекомендуем ее для дальнейшего изучения вопроса.

Дополнительные задачи

30 пятаков лежат гербом вверх. Разрешено за раз перевернуть любые 29 из них. Можно ли добиться, чтобы все пятаки лежали гербом вниз? 2 (IX Турнир городов, 1987 г.). Правильный треугольник разбит прямыми, параллельными

КРУЖОК

его сторонам, на равные между собой правильные треугольники. Один из маленьких треугольников черный, остальные – белые. Разрешается перекрашивать одновременно все треугольники, пересекаемые прямой, параллельной любой стороне исходного треугольника. Всегда ли можно с помощью нескольких таких перекрашиваний добиться того, чтобы все маленькие треугольники стали белыми? 3 (Е.Бакаев, Турнир матбоев памяти А.П.Савина, 2015 г.). Дан клетчатый квадрат: а) $5 \times 5$ ; б) $8 \times 8$ . Одной операцией можно выбрать любой квадрат $3 \times 3$ , или любую строку, или любой столбец и поменять цвета всех клеток этой области на противоположные. С помощью таких операций из полностью белого квадрата получили квадрат, в котором ровно одна черная клетка. Где может оказаться эта клетка? Укажите все варианты. 4. Сколькими способами можно раскрасить клетки таблицы $10 \times 10$ в черный и белый цвета так, чтобы в любом квадрате $3 \times 3$ было четное число черных клеток? 5 (А.Зелевинский, Московская олимпиада, 1970 г., М32). Во всех клетках таблицы размером $100 \times 100$ стоят плюсы. Разрешено одновременно изменить знаки во всех клетках одной строки или во всех клетках одного столбца. Можно ли, проделав такие операции несколько раз, получить таблицу, где ровно 1970 минусов? 6 (В.Алексеев, Московская олимпиада, 2007 г.). В таблице размером $n \times n$ клеток две противоположные угловые клетки черные, а остальные – белые. Какое наименьшее количество белых клеток достаточно перекрасить в черный цвет, чтобы после этого с помощью преобразований, состоящих в перекрашивании всех клеток какого-либо столбца или какой-либо строки в противоположный цвет, можно было сделать черными все клетки таблицы? 7 (А.Быстриков, XXV Турнир городов, 2003 г.). В таблице $m \times n$ расставлены плюсы и минусы. За один ход разрешается поменять знаки на противоположные в любой строке или столбце или на любой диагонали (угловые клетки тоже считаются диагоналями). Докажите, что если таблица такими действиями не приводится к таблице из одних плюсов, то в ней есть квадрат $4 \times 4$ , который тоже не приводится.