Олимпиада имени Леонарда Эйлера
2014-2015 учебный год, I тур регионального этапа


Разрешается вырезать из шахматной доски размером $20\times20$ любые $18$ клеток, а потом выставить на оставшиеся клетки несколько ладей, не бьющих друг друга. Какое наибольшее число ладей можно выставить таким образом? Ладьи бьют друг друга, если они стоят на одной горизонтали или вертикали доски и между ними нет вырезанных клеток. ( Р. Женодаров, О. Дмитриев )
посмотреть в олимпиаде

Комментарий/решение:

Комментарии от администратора Комментарии от администратора №1.     Ответ. 38 ладей.
Решение. Назовём вырезанные клетки дырками. Кроме них, добавим к каждой вертикали доски по дырке снизу, а к каждой горизонтали — по дырке справа; всего добавлено $2 \cdot 20 = 40$ дырок. Пусть на доске расставлено несколько ладей, не бьющих друг друга. Будем временно считать, что ладья бьёт только вправо и вниз. Тогда каждая ладья бьёт по одной дырке справа и снизу от себя (т. е. между ней и этими дырками нет ни других дырок, ни других ладей). С другой стороны, каждую из 18 исходных дырок на доске бьёт не более двух ладей (максимум по одной сверху и слева), а каждую из 40 добавленных дырок — не более одной ладьи. Значит, всего ладей на доске не более $ (18 \cdot 2+40)/2 = 38$.
Осталось привести пример расстановки 38 ладей, удовлетворяющей условию. Для этого вырежем все клетки одной из главных диагоналей доски, кроме двух угловых, и поставим ладьи на все клетки, соседние по сторонам с вырезанными. На рисунке ниже показан пример подобной расстановки на доске $6\times6$.