Олимпиада имени Леонарда Эйлера
2014-2015 учебный год, I тур регионального этапа
Комментарий/решение:
Комментарии от администратора Комментарии от администратора №1. Ответ. 38 ладей.
Решение. Назовём вырезанные клетки дырками. Кроме них, добавим к каждой вертикали доски по дырке снизу, а к каждой горизонтали — по дырке справа; всего добавлено 2⋅20=40 дырок. Пусть на доске расставлено несколько ладей, не бьющих друг друга. Будем временно считать, что ладья бьёт только вправо и вниз. Тогда каждая ладья бьёт по одной дырке справа и снизу от себя (т. е. между ней и этими дырками нет ни других дырок, ни других ладей). С другой стороны, каждую из 18 исходных дырок на доске бьёт не более двух ладей (максимум по одной сверху и слева), а каждую из 40 добавленных дырок — не более одной ладьи. Значит, всего ладей на доске не более (18⋅2+40)/2=38.
Осталось привести пример расстановки 38 ладей, удовлетворяющей условию. Для этого вырежем все клетки одной из главных диагоналей доски, кроме двух угловых, и поставим ладьи на все клетки, соседние по сторонам с вырезанными. На рисунке ниже показан пример подобной расстановки на доске 6×6.
Давайте рассмотрим каждую вертикаль если скажем что в каждой n-ной вертикали кол-во ладей a_n тогда допустим мы смогли поставить 39 ладей заметим что кол-во дырок в n-ной вертикали не меньше чем a_n -1 тогда сумма всех дырок не меньше чем 39-20 что равно 19 значит дырок не меньше 19 противоречие пример для 38 как в оригинальном решений
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.