|
|
 |
Условие
В левом нижнем углу клетчатой доски n×n стоит конь. Известно, что наименьшее число ходов, за которое конь может дойти до правого верхнего угла, равно наименьшему числу ходов, за которое он может дойти до правого нижнего угла. Найдите n.
Решение
Пусть n чётно. В этом случае левое нижнее поле имеет тот же цвет, что и правое верхнее, а правое нижнее – другой. После каждого хода конь оказывается на поле противоположного цвета. Поэтому любой путь из левого нижнего угла в правый верхний состоит из чётного количества ходов, а в правый
нижний – из нечётного. Следовательно, их длины различны.
: Пусть n = 4k + 1. Тогда, делая ходы поочередно по полям двух нижних горизонталей, конь достигнет правого нижнего угла за 2k ходов.
Покажем, что путь до правого верхнего угла длиннее. Каждым ходом конь сдвигается по горизонтали и вертикали в сумме на 3 поля. Даже двигаясь все время вправо-вверх, он за 2k ходов сдвинется на 6k полей. А суммарное расстояние по горизонтали и по вертикали от левого нижнего угла
до правого верхнего равно 2n – 2 = 8k > 6k. Поэтому кратчайший путь до правого верхнего поля длиннее.
Пусть n = 4k – 1. Тогда до правого нижнего поля можно дойти за 2k ходов следующим образом: первым ходом пойти на одно поле вправо и на два вверх, вторым – на одно вправо и на два вниз, а затем, как и в предыдущем случае, ходить поочередно по полям двух нижних горизонталей. За меньшее число ходов дойти нельзя. Действительно, коню нужно сдвинуться на n – 1 = 4k – 2 клеток вправо, при этом каждым ходом он сдвигается максимум на две клетки вправо. То есть число ходов не меньше 2k – 1. Но за 2k – 1 ход конь окажется на поле чужого цвета, а в нашем случае правый нижний угол имеет тот же цвет, что и левый нижний, значит, нужно сделать ещё по крайней мере один ход, то есть число ходов не меньше 2k.
Максимальный суммарный сдвиг вправо и вверх за 2k ходов по-прежнему равен 6k. А суммарное расстояние по горизонтали и по вертикали от левого нижнего поля до правого верхнего равно 2n – 2 = 8k – 4. При :k > 2 это больше чем 6k. При k = 1 (n = 3) нетрудно перебрать все варианты и убедиться, что этот случай не подходит. А вот при k = 2 (n = 7) оба кратчайших пути состоят из четырёх ходов, и это также нетрудно проверить.
Ответ
n = 7.
