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

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

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

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

Давайте рассмотрим каждую вертикаль если скажем что в каждой n-ной вертикали кол-во ладей a_n тогда допустим мы смогли поставить 39 ладей заметим что кол-во дырок в n-ной вертикали не меньше чем a_n -1 тогда сумма всех дырок не меньше чем 39-20 что равно 19 значит дырок не меньше 19 противоречие пример для 38 как в оригинальном решений

Пусть $x_i$ - кол-во вырезанных клеток для $i$-го столбца, $i=1,2,...,n$. Очевидно, что $x_1+x_2+...+x_{20}=18$. Оценим кол-во ладей: возьмем произвольный столбец $x_k$, в нем максимум $x_k + 1$ ладей, тогда суммарно в таблице максимум $(x_1+1)+...+(x_{20}+1)=18+20=38$ ладей