На бесконечной клетчатой плоскости некоторые клетки покрашены в красный цвет, некоторые \(-\) в синий, а некоторые остались непокрашенными. Известно, что в каждой строчке, где есть хотя бы одна синяя клетка, есть также хотя бы \(5\) красных, а в каждом столбце, где есть хотя бы одна красная клетка, есть хотя бы \(6\) синих. Какое наименьшее положительное число покрашенных клеток может быть на плоскости?

В этой задаче правильный ответ с примером оценивается в 1 балл из 5, большая часть баллов ставится за доказательство того, что меньше закрашенных клеток быть не может.

Решение

Докажем утверждение, что меньше 120 закрашенных клеток не может быть.
Если в каком-то столбце есть закрашенные клетки, то по условию они либо только синие, либо обоих цветов. При этом, если в каком-то столбце все закрашенные клетки синие, можно превратить их все в незакрашенные. При этом условие задачи сохранится, а количество закрашенных клеток уменьшится (но не до нуля, так как в строчках с этими синими клетками останутся какие-то красные.)
Аналогичным образом можно избавиться от строчек, в которых есть красные клетки, но нет синих. Теперь можно считать, что во всех строчках и столбцах, где есть закрашенные клетки, присутствуют клетки обоих цветов.

Пусть у нас \(x\) красных клеток и \(y\) синих, при этом закрашенные клетки находятся в \(m\) строчках и \(n\) столбцах. Так как в каждом из этих \(n\) столбцов присутствуют хотя бы \(6\) синих клеток, выполняется неравенство \(y\geqslant 6n\), или, что то же самое, \(n\leqslant \dfrac{y}{6}\). Аналогично \(x\geqslant 5m\) или, что то же самое, \(m\leqslant\dfrac{x}{5}\). Также заметим, что в каждой строчке есть хотя бы одна синяя клетка и \(5\) красных, значит, \(n\geqslant6\). Аналогично \(m\geqslant7\).

Сравним числа \(6x\) и \(5y\).
Пусть \(6x\geqslant5y\), то есть \(x\geqslant\dfrac{5}{6}y\). В каждом столбце присутствуют хотя бы \(6\) синих клеток. Из взятого в качестве предположения неравенства следует, что в каком-то столбце количество красных клеток хотя бы \(\dfrac{5}{6}y\) от количества синих, то есть хотя бы \(5\), поэтому общее количество закрашенных клеток в данном столбце хотя бы \(11\), откуда \(m\geqslant11\) и, следовательно, \(x\geqslant55\). Если \(y\geqslant65\), \(x+y\geqslant120\) и оценка доказана.

Предположим \(y<65,\) тогда \(n<11\), то есть не превосходит \(10\).
Тогда в каком-то из наших (не более чем \(10\)) столбцов присутствуют хотя бы \(6\) красных клеток (\(x\geqslant55\)). Так как в нём должно быть ещё и \(6\) синих, мы получаем, что общее количество закрашенных клеток в этом столбце хотя бы 12, то есть \(m\geqslant12 \) и \(x\geqslant5m\geqslant60\). Тогда, чтобы \(x+y\) было меньше \(120\), необходимо \(y\leqslant59\). Продолжим эти рассуждения.

Поскольку \(y\leqslant59\), значит \(n\leqslant9\). Значит, в каком-то столбце присутствуют хотя бы \(\dfrac{60}{9}\), то есть хотя бы \(7\) красных клеток, откуда \(m\geqslant7+6=13\), \(x\geqslant5m\geqslant65,\) \(y\leqslant54\).

Поскольку \(x\geqslant65,\) в каком-то столбце присутствуют хотя бы \(\dfrac{65}{9}\), то есть хотя бы \(8\) красных клеток, откуда \(m\geqslant8+6=14,\) \(x\geqslant5m\geqslant70\), \(y\leqslant49.\)

Поскольку \(y\leqslant49\), значит \(n\leqslant8\). Значит, в каком-то столбце присутствуют хотя бы \(\dfrac{65}{8}\), то есть хотя бы \(9\) красных клеток, откуда \(m\geqslant9+6=15\), \(x\geqslant5m\geqslant75,\) \(y\leqslant44\).

Поскольку \(y\leqslant44\), значит \(n\leqslant7\). Значит, в каком-то столбце присутствуют хотя бы \(\dfrac{75}{7}\), то есть хотя бы \(11\) красных клеток, откуда \(m\geqslant11+6=17\), \(x\geqslant5m\geqslant85,\) \(y\leqslant34\).

Поскольку \(y\leqslant34\), значит \(n\leqslant6\). Значит, в каком-то столбце присутствуют хотя бы \(\dfrac{85}{6}\), то есть хотя бы \(15\) красных клеток, откуда \(m\geqslant15+6=21\), \(x\geqslant5m\geqslant105,\) \(y\leqslant 14\). Отсюда получаем, что \(n\leqslant2\), что противоречит доказанному ранее.

Аналогично разбираем случай, когда \(6x<5y\), то есть \(x<\dfrac{5}{6}y\).
В каждой строчке присутствуют хотя бы \(5\) красных клеток. Из взятого в качестве предположения неравенства следует, что в какой-то строке есть хотя бы \(6\) синих клеток, то есть общее количество закрашенных клеток в данной строке хотя бы \(11\), откуда \(n\geqslant11\) и, следовательно, \(y\geqslant66\). Если \(x\geqslant54\), \(x+y\geqslant 120\) и оценка доказана.

Предположим \(x<54\), тогда \(m<11\), то есть не превосходит \(10\).
Но раз \(m\leqslant 10,\) а \(y\geqslant66,\) в какой-то из наших (не более чем \(10\)) строк присутствуют хотя бы \(7\) синих клеток. Так как в ней должно быть ещё и \(5\) красных, мы получаем, что общее количество закрашенных клеток в этой строке хотя бы \(12\), то есть \(n\geqslant12\) и \(y\geqslant6n\geqslant 72\). Тогда, чтобы \(x+y\) было меньше \(120\), необходимо \(x\leqslant47\). Продолжим эти рассуждения.

Поскольку \(y\geqslant72,\) в какой-то строке присутствуют хотя бы \(\dfrac{72}{9}\), то есть хотя бы \(8\) синих клеток, откуда \(n\geqslant8+5=13\), \(y\geqslant5n\geqslant78,\) \(x\leqslant 41\).

Поскольку \(x\leqslant41\), значит \(m\leqslant8\). Значит, в какой-то строке присутствуют хотя бы \(\dfrac{78}{8}\), то есть хотя бы \(10\) синих клеток, откуда \(n\geqslant10+5=15,\) \(y\geqslant5n\geqslant90,\) \(x\leqslant 29\). Отсюда получаем, что \(m\leqslant 5\), что противоречит доказанному ранее.

Таким образом мы разобрали оба случая и доказали, что ситуация, в которой \(x+y<120\) невозможна.
Примеров для 120 несколько, они все отличаются перестановкой строк и столбцов. Например, можно взять прямоугольник \(12\times 10\) и раскрасить его в шахматном порядке в красный и синий цвет.

Ответ: \(120\).