8-шы халықаралық Жәутіков олимпиадасы, 2012 жыл

Өлшемі $n \times n$ болатын кестенің (бірлік) шаршыларының жиыны мына шартты қанағаттандыратын болса, ыңғайлы деп аталады: кестенің әрбір қатарында және әрбір бағанында осы жиынның кемінде екі шаршысы табылады. Әрбір $n \ge 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$, ЧТД