Максимальное число ладей и отмеченные клетки — олимпиадная задача по оценке и примеру

Рассмотрим расстановку k ладей, удовлетворяющую условию. Возможны два случая.

1. Пусть в каждом столбце стоит хотя бы по одной ладье. Тогда вся доска находится под боем, и можно убрать ладью из любого столбца, в котором их хотя бы две. Значит, в этом случае в каждом столбце стоит ровно по одной ладье, и k 10. Аналогично, если в каждой строке есть ладья, то тоже k 10.

2. Пусть теперь найдутся пустая строка и пустой столбец. Тогда клетка на их пересечении не под боем. Заметим, что каждая ладья является единственной либо в своей строке, либо в своем столбце (иначе ее можно выкинуть, и ее строка и столбец останутся под боем). Для каждой ладьи отметим эту строку или этот столбец. Если отмечены не более 8 столбцов и не более 8 строк, то всего ладей не больше 8+8=16. Если же, для определенности, отмечены 9 столбцов, то ладей всего 9 (в каждом из 9 столбцов по одной, а в 10-м столбце по предположению ладей нет). Итого, во всех случаях мы получили k 16. Пример для 16 ладей показан на рисунке; для каждой ладьи стрелкой указана клетка, которая останется не под боем, если эту ладью убрать.