Метрика коня

Квант 1981, №10 с. 13-16 Тег ZC9G

Д. Коэн

Метрика коня

Нас здесь будет интересовать ходы коня на шахматной доске, которую мы вначале будем предложать бесконечной. Обозначим клетки доски параметных чисел (координатами центра клетки — см. рис. 1). Ход коня, находящемся в начале координат (0;0), — это переход в одну из 8 клеток с координатами (±1; ±2), (±2; ±1). Если же конь находится в клетке (x; y), то один ход переводит его в одну из клеток (x±1; y±2), (x±2; y±1).

Определим расстояние от клетки P до клетки Q как мин и мал но е число ходов коня, необходимое для того, чтобы перейти из P в Q. Обозначим это число через q (P, Q). Например,

Автор — американский математик — написал эту статью для «Кванта» по-английски. Перевод под редакцией А. Сосинского.

Рис. 1.

мер, расстояние от начала O(0;0) до клетки E(1;0) равно расстоянию от начала до клетки F(3;6) — оба они равны 3. Функция q, определяная на множество пар (P, Q) клеток, обладает треяя основными свойствами расстояния*):

q(P, Q) > 0, при P ≠ Q; q(P, P) = 0;
q(P, Q) = q(Q, P); (II)
q(P, R) ≤ q(P, Q) + q(Q, R). (III)

Первые два свойства оченьидны, а третье — его называют неравенством треугольника — следует из того, что может найти путь из P в R, не проходящей через Q и более короткий, чем любой путь из P в R, проходящий через Q.

Это расстояние — метрика коня — порождает весма необучную «геометрию». В ней можно определить понятие отрезка [AB]** как множество клеток M таких, что q(A, M) + λ(M, B) = q(A, B), но отрезки получаются весма уродливыми (два отрезка могут пересекаться в нескольких клетках). Можно определить и окружности радиуса r, которые выглядят несколько более прилично (по крайней мере, при r ≥ 5).

А пока отметим следующее оцененное свойство функции q:

q((x; y), (x’; y’)) =
= q((0; 0), (x’ − x; y’’ − y)). (*)

он позволяет вместе функции q от пар клеток изучать функцию от одной клетки — расстояние от начала:

d(P) = q(O, P).

Проставим в каждой клетке P значение функции d(P). Вообразим, что мы это сделали на листке кальки. Тогда свойство (*) означает, что, если мы параллельно свинием кальку, совместим на начало O с точкой P, на кальке над точкой Q будет написано q(P, Q).

На рисунке 2 прославлены все значения d(P), меньше или равны 4. Рисунок подсказывает следующее:

*) См. «Геометрия 6—8», п. 4 — прим. ред.
**) См. «Геометрия 6—8», пп. 5—6 — прим. ред.

Формула расстояния $d((a; b))$
В силу свойств (1) и (2) достаточно вычислить $d((a; b))$ в случае, когда $0 \leq a \leq b$ . Кроме того, чтобы избежать путаницы, существуют около начала отсчета, мы будем предполагать, что $a+b \geq 6$ . Расстоянием два случая в зависимости от того, лежит ли клетка $P(a; b)$ в горизонтальной полосе $n$ -го пояса, то есть $2a \leq b$ . При фиксированном $d=d((a; b))$ у точки $P$ имеются 4 разные возможные.

Первый случай: клетка $P(a; b)$ лежит в горизонтальной полосе $n$ -го пояса, то есть $2a \leq b$ . При фиксированном $d=d((a; b))$ у точки $P$ имеются 4 разные возможные.

Мы предлагаем доказательство, несколько отличия от авторского (прим. ред.)

Рис. 2.
шце свойства функции $d$ :
$d((a; b))=d((b; a)),$
(1)
$d((a; b))=d((|a| |b|)),$
(2)
числа $d((a; b))$ и $a+b$
имеют одинаковую четность, (3) которые, очевидно, следует из определения.

Заметим далее, что на рисунке 2 внутри красной линии стоит числа 0, 1, 2, 3, 4, изрядно переупятные, хотя и симметрично расположенные (из-за свойств (1) и (2)). В порядке между красной и синей линиими стоит только четверки и значок $\times$ (на самом деле $\times=5$ ). В следующем таким поясе будет стоять только 5 и 6, в следующем — 6 и 7 и т. д. (рис. 3). На рисунке 4 изображена только первая четверть $(x, y \geq 0)$ . На этом рисунке также показан участок $n-20$ пояса, в котором стоит только числа $n$ и $n+1$ .

Грубо говоря, $n$ -й пояс имеет форму границы квадрата (со стороны длины $4n+1$ ) со среданным углам (отрезаны равноведенные прямогольные треугольники с боковой стороны длины $n-1$ ). Пояс составлен из горизонтальных и вертикальных полос толщины 2 и четырех диагональных участков в виде лесенки; один из них выделен на рисунке цветом.

Таким образом, если отвлечется от путаницы, существующий вблизи начала отсчета, геометрическая картина метрики коня проясилась. Однако этого нам мало: мы хотим научиться находить $d((a; b))$ чисто аналогичски — по числам $a$ и $b$ . Короче, нам нужна

Рис. 3.
Рис. 4.

ности в зависимости от ее уровня по вертикали (рис. 5). На самом верхнем уровня точка $P$ достигается минимальный целочкой из $d$ ходов, увеличивающих вторую координату на 2; на следующем уровне — целочкой из $d-1$ ходов этого типа и одним ходом, увеличивающим вторую координату на 1; на следующем уровне требуется $d-2$ и 2 хода этих типов; на нижнем уровне — соответственно $d-3$ и 3. В этих случаях высота $b$ равняется $2d$ , $2(d-1)+1=2d-1$ , $2(d-2)+2=2d-2$ , $2(d-3)+3=2d-3$ соответственно. Отсюда можно было бы выразить $d$ через $b$ , но $b$ — целое, и мы не можем записать ответ, не зная четности $b!$ Как бы?

Оказывается, правильный ответ дает одно из чисел $[(b+1)/2]$ или $[(b+1)/2]+1$ (здесть квадратные скобки обозначают целую часть), а именно то, чья четность совпадает с четностью числа $a+b$ (см. свойство (3)). Читатель легко проверит это, воспользовавшись рисунком 5 и подписью к нему.

Второй случай: клетка $P(a; b)$ лежит на диагональном участке $n$ -го пояса, то есть $2a>b$ . Легко видеть, что в любую точку диагонального участка первой четверти $n$ -го пояса можно добрать минимальный последовательностью ходов коня так, чтобы на каждом ходе сумма координат увеличиваласьровно на 3 (то есть ходами $(a; b) \rightarrow (a+1; b+2)$ и $(a; b) \rightarrow (a+2; b+1)$ ). Поэтому $a+b=3n$ или $a+b=3(n+1)$ , откуда $d((a; b)) = [(a+b+1)/3]$ или $d((a; b)) = [(a+b+1)/3]+1$ . Какое именно из этих двух чисел можно взять, ясно из сообщений четности (см. (3)).

Подведем итог нашго исследования функции $d((a; b))$ . При условиях $0 \leq a \leq b$ и $a+b \geq 6$ число $d((a; b))$ имеет ту же четность, что $a+b$ , равняется $[(b+1)/2]$ или $[(b+1)/2]+1$ в случае $2a \leq b$ , $[(a+b+1)/3]$ или $[(a+b+1)/3]+1$ в случае $2a>b$ .

На самом деле эти формулы дают верный ответ и при $a+b<6$ всюду, кроме клеток (0; 1) и (2; 2), где они дают 1 и 2 соответственно, вместе правильных 3 и 4 (см. рис. 2).

Метрика коня на прямогольной доске

Ограничим теперь нашу бесконечную шахматную доску: будем рассматривать ходы коня на прямогольной доске $a \times b$ ( $a \leq b$ ). При $a=1$ рассматривать нечего («Товарищ гроссейстер, так конь не ходит!»), при $a=2$ все очень просто. Более содержательные случаи $a=3$ и $a=4$ мы оставим читателю, а сами перейдем к случае $5 \leq a \leq b$ . Оказывается,

При $5 \leq a \leq b$ существует ходов коня длинны $d((a; b))$ внутри прямогольника со стороны $x=0$ , $x=a$ , $y=0$ , $y=b$ , соединяющая точки (0; 0) и $(a; b)$ , и этот путь самый короткий.

Действительно, начинаем с точки в $n$ -м поясе и сделаем один в сторону начала. Тогда мы остаемся внутри прямогольника и попадем в $(n-1)$ -й пояс. Продолжая этот процесс, мы доберемся до четвертого пояса. Далее остается проверить справедливость нашей утверждения для клеток четвертого

Поясса. Этот перебор мы оставляем читателю.

Метрика коня на квадратной доске
Рассмотрим теперь квадратную доску $n \times n$ , скажем, ограниченную прямоугольником $x=0, x=n-1, y=0, y=n-1$ . Изозем диаметром этой доски наиболее расстояние (в смысле метрики коня) между ее клетками. Вновь оставляя случай малых размеров читателю, мы рассмотрим случай $n \geq 5$ . Из предыдущего легко видеть, что диаметром будет расстояние от клетки (0; 0) до одной из клеток $(n-1; n-1)$ или $(n-1; n-2)$ . Пользовать этим замечанием и ранее получить формулой расстояния, показем, что
Диаметр шахматной доски $n \times n$ равен числу $2n/3$ , округленному до ближайшего целого.

Действительно, по формуле расстояния $d((n-1; n-1))$ равняется $[(2n-1)/3]$ или $[(2n-1)/3] + 1$ (именно, тому из этих чисел, которое четно); а $d((n-1; n-2))$ равняется $[(2n-2)/3]$ или $[(2n-2)/3] + 1$ (нечетному). Расмотрим три случая в зависимости от остатка от деления числа $n$ на 3.

Первый случай: $n=3k$ . Тогда
$[(2n-1)/3] = [(2n-2)/3] = 2k-1,$
так что расстояние до $(n-1; n-1)$ равно $2k$ , а до $(n-1; n-2)$ равно $2k-1$ . Диаметр равен $2a$ , что есть $2n/3$ без всякого округления.

Второй случай: $n=3k+1$ . Тогда
$[(2n-1)/3] = [(2n-2)/3] = 2k,$
так что расстояния до $(n-1; n-1)$ и $(n-1; n-2)$ соответственно равны $2k$ и $2k+1$ . Диаметр равен $2k+1$ , то есть округленному числу $2n/3$ .

Третий случай: $n=3k+2$ . Тогда
$[(2n-1)/3] = 2k+1,$
так что интересующие нас расстояния соответственно равны $2k+2$ и $2k+1$ . Значит, диаметр равен $2k+2$ , то есть снова округленному числу $2n/3$ .

Заметьте, что наиболее расстояние реализуется в этом случае клетками, не лежащими на главной диагонали.

Другие формулы
Функция $d((a; b))$ уже исследовалась раньше, и для нее были получены другие (более сложные) аналогичные выражения (при $a+b \geq 8$ , $0 \leq a \leq b$ ). М. Голдберг (США) нашел
$d((a; b)) = \begin{cases} b-a-2[(b-2a)/4] \\ \text{при } 2a \leq b, \\ b-a+[(8a-4b+2)/3] - [(4a-2b)/3] \\ \text{при } 2a > b, \end{cases}$

а Д. Цветкович и С. Симч (Югославия) нашли
$d((a; b)) = \begin{cases} a+b-2\left[\frac{b}{2}\right] - \left[\frac{a-[b/2]}{2}\right] \\ \text{при } 2a \leq b, \\ a+b-2\left[\frac{a+b}{3}\right] \end{cases}$

Можно показать, что эти формулы эквивалентны нашим, но интереснее попытаться угадать, какими рассуждениями пришли к ним их авторы.

В заключение предлагаем читателю такую задачу: найти площадь кругла радиуса $r$ , то есть число клеток $(a; b)$ , для которых $d((a; b)) \leq r$ .

Турнир имен М. В. Ломоносова
По уточненным данным в этом году турир (см. «Квант», 1981, № 8, с. 51) состоит в Москве 25 октября в 10.00 в помещении следующих взвов: МАИ, МАТИ, МГПИ, МИИГАИК, МИНХИГП, МИСИ, МИСИС; приглашают школьники 6—9 классов.