|
|
 |
Условие
Некоторые клетки доски $100 \times 100$ покрашены в чёрный цвет. Во всех строках и столбцах, где есть чёрные клетки, их количество нечётно. В каждой строке, где есть чёрные клетки, поставим красную фишку в среднюю по счёту чёрную клетку. В каждом столбце, где есть чёрные клетки, поставим синюю фишку в среднюю по счёту чёрную клетку. Оказалось, что все красные фишки стоят в разных столбцах, а синие фишки — в разных строках. Докажите, что найдётся клетка, в которой стоят и синяя, и красная фишки.Решение
Удалим из доски все строки и столбцы, в которых нет чёрных клеток. Заметим, что после этого условие задачи продолжит выполняться. Теперь все чёрные клетки лежат внутри некоторого прямоугольника $n \times m$, в каждой строке и в каждом столбце которого есть хотя бы одна чёрная клетка.
По условию в каждой из $n$ строк стоит ровно одна красная фишка. Тогда всего красных фишек $n$. Но эти $n$ красных фишек должны находиться в разных столбцах, а значит, $m \geqslant n$. Аналогично, рассматривая синие фишки, приходим к выводу, что $n \geqslant m$. Таким образом, $n = m$. Раз красных фишек и столбцов поровну и красные фишки находятся в разных столбцах, то в каждом столбце есть ровно одна красная фишка. Аналогично в каждой строке есть ровно одна синяя фишка.
Рассмотрим верхнюю строку, в ней есть синяя фишка. Рассмотрим столбец с этой синей фишкой. В этом столбце синяя фишка стоит в самой верхней клетке. Получается, что самая верхняя клетка этого столбца оказалась средней по счёту чёрной клеткой в этом столбце. Такое возможно лишь в случае, когда в столбце только одна чёрная клетка.
Ранее доказано, что в любом столбце должна быть ровно одна красная фишка. Рассматривая найденный столбец с единственной чёрной клеткой, приходим к выводу, что красная фишка должна быть в этой клетке. Но в этой клетке уже есть синяя фишка. Таким образом, искомая клетка найдена.
Замечания
Описанные в задаче конструкции существуют, причём не обязательно в каждой строке и в каждом столбце находится ровно одна чёрная клетка. Возможные примеры изображены на рисунке.
