Задача 115425

Темы:    [ Оценка + пример ] [ Шахматные доски и шахматные фигуры ]

Сложность: 4 Классы: 8,9,10,11

Условие

Автор: Берлов С.Л.

В некоторых клетках доски  10× 10 поставили k  ладей, и затем отметили все клетки, которые бьет хотя бы одна ладья (считается, что ладья бьет клетку, на которой стоит). При каком наибольшем  k может оказаться, что после удаления с доски любой ладьи хотя бы одна отмеченная клетка окажется не под боем?

Решение

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

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