Эйлер атындағы олимпиада, 2014-2015 оқу жылы, аймақтық кезеңнің 1 туры

Өлшемі $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$ ладей