Олимпиада имени Леонарда Эйлера 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$.