8-я Международная Жаутыковская олимпиада, 2012 год

Множество (единичных) клеток таблицы $n\times n$ назовём удобным , если в каждой строке и каждом столбце таблицы есть по крайней мере две клетки этого множества. При каждом $n\geq 5$ найдите наибольшее $m$, для которого найдётся удобное множество из $m$ клеток, которое перестает быть удобным при удалении любой из его клеток.

Комментарий/решение

Решение из книги:

Ответ: $4n-8$

Пример: покрасим первые $n-2$ клеток первой и второй строки, а также все клетки, стоящие снизу квадрата $2 \times 2$ в правом вверхнем углу. Очевидно, что такой набор нам подходит.

Оценка: назовем линию (строку или столбец) редкой, если в ней не более $2$ отмеченных клеток. Заметим, что любая отмеченная клетка находится в какой-то редкой линии, иначе можно было удалить эту клетку. Следовательно, количество отмеченных клеток не превышает удвоенного количества редких линий (если для каждой отмеченной клетки назначить редкую линию, то всего таких обозначений будет = кол-во отмеченных клеток, но каждая линия повторится максимум дважды).

Теперь докажем, что это у нас не более $4n-8$

Если, БОО, все $n$ столбцов редкие, то клеток у нас не более $2 \cdot n \leq 4n-8$

Если, БОО, $n-1$ столбов редкие, то всего у нас не более $2 \cdot (n-1)+n$ отмеченных клеток. Но заметим, что если в последнем столбце ровно $n$ отмеченных клеток, то в каждой строке не более $2$ отмеченных, тогда опять $2n \leq 4n-8$, поэтому в оставшемся столбце не более $n-1$ отмеченной клетки, тогда их суммарно не более $2 \cdot (n-1)+(n-1) \leq 4n-8$,

$n \geq 5$

Пусть теперь их не более $n-2$. Аналогично и для строк, тогда их суммарно не более $2n-4$,

$(2n-4) \times 2 = 4n-8$, ЧТД