|
|
 |
Условие
В клетках таблицы n×n стоят плюсы и минусы. За один ход разрешается в произвольной строке или в произвольном столбце поменять все знаки на противоположные. Известно, что из начальной расстановки можно получить такую, при которой во всех ячейках стоят плюсы. Докажите, что этого можно добиться не более чем за n ходов.
Решение
В результате выполнения нескольких операций клетка изменит знак, если строка и столбец, её содержащие, менялись суммарно нечётное число раз. Значит, результат не зависит от порядка выполняемых операций. Кроме того, можно считать, что все строки и столбцы менялись не более одного раза. Предположим, что после замен знаков в k строках и m столбцах получились все плюсы. Если k + m > n, отметим ряды, где мы меняли знаки. Знак сменился только в клетках, принадлежащих ровно одному отмеченному ряду. Но эти же клетки принадлежат ровно одному неотмеченному ряду. Поэтому результат был бы такой же, если бы мы сменили знаки в неотмеченных рядах. А их число равно (n – k) + (n – m) = 2n – (k + m) < n.
Замечания
1. См. также задачу М2270 из Задачника "Кванта" ("Квант", 2012, №4).
2. 6 баллов.
