В каждой клетке таблицы \(m \times n\) стоит крестик или нолик. При этом в каждой строке стоит не меньше \(19\) крестиков, а в каждом столбце — не меньше \(19\) ноликов.
Докажите, что \(m + n \geqslant 76\).

Решение

При минимальном случае \(n \mathrel{\vdots} 19\) и \(m \mathrel{\vdots} 19\), поскольку любую расстановку плюсов и минусов можно свести к случаю \(n \mathrel{\vdots} 19\) и \(m \mathrel{\vdots} 19\). Тогда будем оценивать минимально возможный вариант выражением вида \(n = 19k, m = 19l\). При \(k = 1 l = 1\), разложение из условия невозможно, поскольку в таком случае клеток хватит только на то, чтобы расставить плюсы. При \(k = 2, l = 1\), ситуация, аналогичная предыдущему случаю, как и в случае \(k = 1, l = 2\). Получаем оценку \(k + l \geqslant 4\), то есть их сумма не меньше четырех, поскольку мы рассмотрели все возможные варианты \(k\) и \(l\) которые в сумме дают что-либо меньшее 4 мы рассмотрели.
Получаем оценку \(n + m \geqslant 19(k+l) \geqslant 76\).