Скрыть решение
Решение
Пусть для определённости конь стоит на чёрной клетке. Все клетки, куда он может
попасть за 2 хода, изображены на рис. Случай
n = 1 исключительный. При
n > 1
множество клеток, куда может попасть конь за 2
n ходов, устроено следующим
образом. Возьмём квадрат со стороной 8
n + 1 (конь стоит в центре этого
квадрата). Отрежем от этого квадрата четыре уголка со стороной 2
n (на рис. соответствующая фигура изображена для
n = 2). За 2
n ходов конь может попасть в точности во все чёрные клетки полученной фигуры.
Докажем это. Прежде всего заметим, что после нечётного числа ходов конь
попадает на белую клетку, а после чётного — на чёрную. Индукцией по
m
несложно доказать, что если
m
3, то за
m ходов конь попадает в любую
клетку соответствующего цвета (чёрного при чётном
m и белого при нечётном
m) фигуры, которая получается при отрезании от квадрата со стороной 4
m + 1
четырёх уголков со стороной
m. При
m = 3 это легко проверяется, а шаг
индукции очевиден.