|
|
 |
Условие
В некоторых клетках доски 10×10 поставили k ладей, и затем отметили все клетки, которые бьёт хотя бы одна ладья (ладья бьёт и клетку, на которой стоит). При каком наибольшем k может оказаться, что после удаления с доски любой ладьи хотя бы одна отмеченная клетка окажется не под боем?
Решение
Оценка. Рассмотрим расстановку k ладей, удовлетворяющую условию. Возможны два случая.
1) В каждом столбце стоит хотя бы по одной ладье. Тогда вся доска находится под боем, и можно убрать ладью из любого столбца, в котором их хотя бы две. Значит, в этом случае в каждом столбце стоит ровно по одной ладье, и k = 10.
2) Есть пустая строка и пустой столбец. Тогда клетка на их пересечении не под боем. Заметим, что каждая ладья является единственной либо в своей строке, либо в своем столбце (иначе её можно убрать). Для каждой ладьи отметим эту
строку или этот столбец. Если отмечены не более восьми столбцов и не более восьми строк, то всего ладей не больше 8 + 8 = 16. Если же, для определенности, отмечены девять столбцов, то ладей всего девять (в каждом из девяти столбцов по одной, а в десятом столбце по предположению ладей нет).
Итак, k ≤ 16.
Пример для 16 ладей показан на рисунке.
