МОШ 2022, 9 класс, задача 4
Некоторые клетки доски покрашены в чёрный цвет. Во всех строках и столбцах, где есть чёрные клетки, их количество нечётно. В каждой строке, где есть чёрные клетки, поставим красную фишку в среднюю по счёту чёрную клетку. В каждом столбце, где есть чёрные клетки, поставим синюю фишку в среднюю по счёту чёрную клетку. Оказалось, что все красные фишки стоят в разных столбцах, а синие фишки — в разных строках. Докажите, что найдётся клетка, в которой стоят и синяя, и красная фишки.
(Б. Френкин)
Ответ
Решение. Удалим из доски все строки и столбцы, в которых нет чёрных клеток. Заметим, что после этого условие задачи продолжит выполняться. Теперь все чёрные клетки лежат внутри некоторого прямоугольника , в каждой строке и в каждом столбце которого есть хотя бы одна чёрная клетка. По условию в каждой из строк стоит ровно одна красная фишка. Тогда всего красных фишек . Но эти красных фишек должны находиться в разных столбцах, а значит . Аналогично, рассматривая синие фишки, приходим к выводу, что . Таким образом, . Раз красных фишек и столбцов поровну и красные фишки находятся в разных столбцах, то в каждом столбце есть ровно одна красная фишка. Аналогично в каждой строке есть ровно одна синяя фишка. Рассмотрим верхнюю строку, в ней есть синяя фишка. Рассмотрим столбец с этой синей фишкой. В этом столбце синяя фишка стоит в самой верхней клетке. Получается, что самая верхняя клетка этого столбца оказалась средней по счёту чёрной клеткой в этом столбце. Такое возможно лишь в случае, когда в столбце только одна чёрная клетка. Ранее доказано, что в любом столбце должна быть ровно одна красная фишка. Рассматривая найденный столбец с единственной чёрной клеткой, приходим к выводу, что красная фишка должна быть в этой клетке. Но в этой клетке уже есть синяя фишка. Таким образом, искомая клетка найдена.
Комментарий. Описанные в задаче конструкции существуют, причём не обязательно в каждой строке и в каждом столбце находится ровно одна чёрная клетка. Возможные примеры изображены на рисунке .
