ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 116691
Темы:    [ Числовые таблицы и их свойства ]
[ Четность и нечетность ]
Сложность: 3+
Классы: 10
В корзину
Прислать комментарий

Условие

В клетках таблицы n×n стоят плюсы и минусы. За один ход разрешается в произвольной строке или в произвольном столбце поменять все знаки на противоположные. Известно, что из начальной расстановки можно получить такую, при которой во всех ячейках стоят плюсы. Докажите, что этого можно добиться не более чем за n ходов.


Решение

В результате выполнения нескольких операций клетка изменит знак, если строка и столбец, её содержащие, менялись суммарно нечётное число раз. Значит, результат не зависит от порядка выполняемых операций. Кроме того, можно считать, что все строки и столбцы менялись не более одного раза. Предположим, что после замен знаков в k строках и m столбцах получились все плюсы. Если  k + m > n,  отметим ряды, где мы меняли знаки. Знак сменился только в клетках, принадлежащих ровно одному отмеченному ряду. Но эти же клетки принадлежат ровно одному неотмеченному ряду. Поэтому результат был бы такой же, если бы мы сменили знаки в неотмеченных рядах. А их число равно  (n – k) + (n – m) = 2n – (k + m) < n.

Замечания

1. См. также задачу М2270 из Задачника "Кванта" ("Квант", 2012, №4).
2. 6 баллов.

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Номер 75
Год 2012
класс
Класс 10
задача
Номер 2
олимпиада
Название Турнир городов
Турнир
Дата 2011/2012
Номер 33
вариант
Вариант весенний тур, сложный вариант, 8-9 класс
Задача
Номер 4

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .