ЗАДАЧИ
problems.ru |
О проекте
|
Об авторах
|
Справочник
Каталог по темам | по источникам | |
|
Задача 115425
УсловиеВ некоторых клетках доски 10× 10 поставили k ладей, и затем отметили все клетки, которые бьет хотя бы одна ладья (считается, что ладья бьет клетку, на которой стоит). При каком наибольшем k может оказаться, что после удаления с доски любой ладьи хотя бы одна отмеченная клетка окажется не под боем?РешениеРассмотрим расстановку k ладей, удовлетворяющую условию. Возможны два случая.1. Пусть в каждом столбце стоит хотя бы по одной ладье. Тогда вся доска находится под боем, и можно убрать ладью из любого столбца, в котором их хотя бы две. Значит, в этом случае в каждом столбце стоит ровно по одной ладье, и k 2. Пусть теперь найдутся пустая строка и пустой столбец. Тогда клетка на их пересечении не под боем. Заметим, что каждая ладья является единственной либо в своей строке, либо в своем столбце (иначе ее можно выкинуть, и ее строка и столбец останутся под боем). Для каждой ладьи отметим эту строку или этот столбец. Если отмечены не более 8 столбцов и не более 8 строк, то всего ладей не больше 8+8=16 . Если же, для определенности, отмечены 9 столбцов, то ладей всего 9 (в каждом из 9 столбцов по одной, а в 10-м столбце по предположению ладей нет). Итого, во всех случаях мы получили k |
© 2004-...
МЦНМО
(о копирайте)
|
Пишите нам
|
![]() |