Долгий путь короля

39

МАТЕМАТИЧЕСКИЙ КРУЖОК

Долгий путь короля

Н.БЕЛУХОВ (БОЛГАРИЯ)

«белой» доски Уэлча на «черную» или наоборот. Поэтому любой маршрут короля представляется как путь хромой ладьи по двум доскам Уэлча, прыгающей с одной доски на другую, когда король делает короткий ход. Число прыжков равно числу коротких ходов короля. Поскольку наша цель – наименьшее количество таких ходов, будем искать маршрут хромой ладьи по одной доске Уэлча, который состоит из наименьшего числа непрерывных участков. Покрасим доску Уэлча в шахматном порядке, как показано на рисунке 2. На любом участке пути нашей ладьи белые

Посвящается Евгению Гику

В«КВАНТЕ» №3 ЗА 2000 ГОД БЫЛА НАПЕЧАТАНА НЕБОЛЬ- шая заметка И.Акулича «Прогулки короля». В ней автор поставил несколько интересных открытых вопросов, в том числе и такой: Какова наибольшая возможная длина замкнутого пути короля, обошедшего шахматную доску $8 \times 8$? Более точно, пусть король обошел шахматную доску, побывав на каждой клетке по разу, и последним ходом вернулся в исходную клетку. Если соединить отрезками центры полей, которые он последовательно проходил, получится замкнутая ломаная (скорее всего, самопересекающаяся). Какова наибольшая возможная длина этой ломаной? Ясно, что ломаная стоит из отрезков двух типов – коротких (длины 1) и длинных (длины 2 ). Поэтому достаточно найти минимальное возможное количество коротких ходов короля. Этим мы и займемся. Фактически мы решим задачу в общем случае – для досок $2 n \times 2 n$ (задача для досок с нечетной длиной стороны решается, как мы скоро увидим, совсем просто). Рассмотрим шахматную доску $2 n \times 2 n$ и построим вспомогательную доску, которая называется доской Уэлча. Для этого уберем на исходной доске все клетки одного цвета, а каждую клетку другого цвета заменим на квадрат с длиной стороны в 2 раз больше, который повернут на $45^\circ$ вокруг центра клетки (рис.1).

Рис. 1

Пока король делает длинные, т.е. диагональные, ходы, он остается на клетках одного цвета. Более того, такие ходы короля соответствуют движению «хромой» ладьи по доске Уэлча (хромая ладья ходит как обычная, но за ход сдвигается только на соседние клетки). Если считать, что есть две доски Уэлча – по одной для белых и черных клеток исходной доски, то каждый короткий ход короля можно понимать как прыжок ладьи с

Рис. 2

и черные клетки чередуются, поэтому разница между количествами одних и других на любом участке не превосходит 1. Если исходная шахматная доска имеет размеры $( 2 n + 1 ) \times ( 2 n + 1 )$, то на одной из раскрашенных досок Уэлча клеток одного цвета будет больше, чем другого, причем не меньше чем на 2n + 1. Это означает, что потребуется не меньше 2n + 1 непрерывных кусков пути, чтобы посетить все клетки одной доски. Следовательно, будет не меньше 4n + 2 прыжков с одной доски на другую (по два прыжка на каждый кусок пути). Итак, если у шахматной доски нечетный размер, то король, обойдя доску по замкнутому пути, сделает не меньше 4n + 2 коротких ходов. Это достаточно большое число, и построить соответствующий пример пути не очень сложно.

Упражнение. Сделайте это.

Если же шахматная доска четного размера, то каждая из досок Уэлча содержит поровну белых и черных клеток. Но их расположение даст нам ключ к решению. Пусть при движении по доске Уэлча ладья оставляет след – линию, соединяющую центры клеток, которые ладья последовательно посещает. Когда ладья прыгает (на другую доску), линия прерывается, зато потом начнется новая. Если ладья посетила все клетки, то несколько таких линий «покрывают» всю доску. Мысленно разрежем доску, изображенную на рисунке 2, на две одинаковые части по отрезку AB. Этот отрезок делит некоторые линии на части. Заметим, что нижняя половина доски содержит на n черных клеток больше, чем белых. Это означает, что есть не меньше n линий или их частей, которые начинаются и заканчиваются в черной клетке. Аналогично, рассматривая верхнюю половину, получим, что есть не меньше n линий или их частей, которые начинаются и заканчиваются в белой клетке. Всего получается не меньше 2n линий или их частей. Но склеивание частей линий по отрезку AB уменьшит их количество не больше чем на n (ведь есть только n возможных мест склейки).