Олимпиада имени Леонарда Эйлера 2022-2023 учебный год, II тур дистанционного этапа

На клетчатую доску размером $100\times 100$ поставили 1975 ладей (каждая ладья занимает одну клетку, разные ладьи стоят на разных клетках). Какое наибольшее количество пар ладей, бьющих друг друга, могло при этом получиться? Напомним, что ладья может бить на любое число клеток по горизонтали и вертикали, но не бьёт ладью, загороженную другой ладьёй. ( И. Рубанов )

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

Комментарии от администратора Комментарии от администратора №1.    
Ответ. 3861.
Решение. По очереди удалим из доски $100\times 100$ вертикали и горизонтали, в которых нет ладей, каждый раз сплачивая края удаленной полоски. Получим прямоугольник $\pi$, в каждой вертикали и каждой горизонтали которого есть хотя бы по одной ладье (очевидно, количество пар ладей, бьющих друг друга, при этом не изменится). Пусть в нём $a$ горизонталей и $b$ вертикалей. Заметим, что если в горизонтали или вертикали стоит $k > 0$ ладей, то в ней ровно $k-1$ пара ладей, бьющих друг друга. Суммируя по всем горизонталям и вертикалям, получаем, что количество пар бьющих друг друга ладей равно $1975\cdot 2-(a+b) (*)$. При этом площадь прямоугольника $\pi$ не меньше числа ладей. Получаем, что $a+b\ge 2\sqrt{ab}\ge 2\sqrt{1975}>2\sqrt{1936}=88$, откуда $a+b \ge 89$. Таким образом, количество пар бьющих друг друга ладей не больше, чем $1975\cdot 2-89 = 3861$. Чтобы получить пример, когда их ровно 3861, достаточно произвольным образом расставить 1975 ладей в некотором прямоугольнике размером $45\times 44$. Это возможно, так как $45\times 44 = 1980 > 1975$.