|
|
 |
Условие
В каждой клетке одной из главных диагоналей доски $90\times90$ стоит конь. За какое наименьшее число ходов кони могут занять все клетки другой главной диагонали?
Решение 1
Пример. Пусть кони стояли на диагонали, идущей из левого верхнего угла в правый нижний.
За 1 вертикальный ход и 44 горизонтальных конь может перейти из левого верхнего угла в правый верхний (и аналогично из правого нижнего в левый нижний); так переведём двух угловых коней.
За 43 горизонтальных хода конь может перейти на доске $88\times88$ из угла в клетку, соседнюю (по диагонали) с другим углом; так мы переведём пару соседних коней на одном конце диагонали новой доски на два соответствующих соседних места другой диагонали, аналогично с парой на другом конце.
Аналогично за 41 ход можно перевести коня на доске $84\times84$ из угла в клетку, соседнюю (по диагонали) с другим углом, и так далее.
Всего получается $2\cdot45 + 4(43 + 41 + \ldots + 1)=2\cdot45+44^2=45^2+1=2026$ ходов.
Оценка. Занумеруем клетки одной диагонали от 45 до 1, считая от центра, а другой — от 46 до 90. Пусть конь с клетки $x \leqslant 45$ занял клетку $y > 45$. Число $y-x$ равно модулю разности номеров строк или столбцов, поэтому конь сделал не менее $(y-x)/2$ ходов. Значит, всего ходов не менее $(46 + \ldots + 90) - (1 + \ldots + 45) = 45^2$. Так как главная и побочная диагонали разных цветов, то каждый конь сделал нечётное число ходов. Поэтому общее число ходов чётно и оно не меньше $45^2 + 1$.
Решение 2
Пусть кони стояли на белой диагонали (идущей из левого верхнего угла). Она разбивается на две части — верхнюю и нижнюю. Обозначим клетки верхней части $Б_1$, $Б_2$, …, $Б_{45}$, начиная от центра, клетки нижней — так же. Аналогично обозначим клетки чёрной диагонали: $Ч_{45}$, …, $Ч_1$, $Ч_1$, …, $Ч_{45}$.
Оценка. Заметим, что коню для перехода с клетки $Б_i$ на клетку $Ч_j$ потребуется не менее $\frac12(i + j - 1)$ ходов. Действительно, если обе клетки лежат в верхней части доски, то он должен сдвинуться на $i + j - 1$ клетку вправо, а каждый ход сдвигает его не более чем на 2 клетки. Если $Б_i$ в верхней части, а $Ч_j$ в нижней, он должен сдвинуться на $i + j - 1$ клетку вниз и т.д. Просуммировав эти оценки по всем 90 коням, получим удвоенную сумму чисел от 1 до 45 минус 45, то есть $45\cdot46 - 45 = 45^2 = 2025$. Поскольку кони переходили с белых клеток на чёрные, каждый из 90 коней сделал нечётное число ходов, а в сумме они сделали чётное число ходов, то есть не меньше 2026.
Пример. Покажем, как переставить коней с верхней части белой диагонали на верхнюю часть чёрной за 1013 ходов. При $n$ от 1 до 22 переставим коня с клетки $Б_{2n}$ на $Ч_{2n-1}$, а с $Б_{2n-1}$ — на $Ч_{2n}$, сдвигаясь каждым ходом на две клетки вправо и одну клетку вверх или вниз (рис. слева). Получится $2n - 1$ ход для каждого из двух коней. Для перехода с $Б_{45}$ на $Ч_{45}$ хватит 45 ходов (рис справа). Итого $2\cdot(1+3+\ldots+43)+45=1013$ ходов. Перестановку коней с нижней части белой диагонали на нижнюю часть чёрной проводим аналогично.
Ответ
За 2026 ходов.
