Подсчеты в клетчатых задачах

Оценка. Предположим, что в строчках стоят белых клеток, а в столбцах — белых клеток. Рассмотрим -ую строку. Заметим, что в пересечении с столбцами у неё стоят черные клетки. Значит, в каждом из этих столбцов не менее белых клеток. Просуммируем такие величины по всем строкам. Заметим, что белую клетку из -ого столбца мы посчитали не более раз. То есть имеем неравенство

Раскрыв скобки и перенеся все в левую сторону, а также воспользовавшись тем, что имеем

Оценим Аналогично

Тогда

Обозначим количество белых клеток через Тогда после сокращения на получаем

С другой стороны То есть

откуда получаем

Пример. Пусть в первой строчке белыми будут клетки во второй — …(то есть на каждой следующей строчке сдвигаем все на вправо, возможно, с переносом в начало). Таким образом, в каждой строчке и в каждом столбце будет ровно белых клеток. Оставшиеся клетки будут черными, в кресте каждой из них будет ровно пустых клеток.