Т.Е. Бояринцева, А.А. Мастихина
8
,
.
E a
g f
Отсюда видно, что
r
(
a
) = 1 лишь тогда, когда пересечение
множеств
E
и
T
a
состоит из нечетного множества квадратиков.
Имеем равенство
E
g
( )
0,
a
а
r a f
из которого следует обе-
щанное обоснование алгоритма решения задачи 2.2.
2.3. Конь на шахматной доске.
Приведем еще один пример за-
нимательной задачи. Это один из красивых примеров задачи постро-
ения гамильтонова цикла в графе. Гамильтоновым циклом называет-
ся цикл, проходящий через все вершины графа.
В общем случае построение гамильтонова цикла решается,
например, с помощью алгоритма «поиска в глубину» [1], но в част-
ном случае бывают необычные решения. Пусть имеем граф на 64
вершинах, которые сопоставим клеткам шахматной доски, и две
вершины считаются смежными, если из одной в другую можно по-
пасть одним ходом шахматного коня. Задача состоит в том, чтобы
конем обойти все клетки шахматной доски, побывав на каждой клет-
ке только по одному разу, и вернуться в исходное положение.
Маршрут Яниша. Начинаем с середины доски, позиция 1, далее
посещаем клетки с числами 2, 3, ..., 64 (по ходу коня).
50 11 24 63 14 37 26 35
23 62 51 12 25 34 15 38
10 49 64 21 40 13 36 27
61 22 9 52 33 28 39 16
48 7 60
1 20 41 54 29
59 4 45
8 53 32 17 42
6 47 2
57 44 19 30 55
3 58 5 46 31 56 43 18
Отметим интересное свойство этого маршрута: при повороте
доски на 180° первая половина маршрута (номера с 1 до 32) перехо-
дит во вторую (номера с 33 по 64).
Также приведем другой пример маршрута, примечательный тем,
что для него существует мнемоническое стихотворение, сочиненное
гроссмейстером Василием Пановым (впервые опубликовано в жур-
нале «Наука и жизнь», [8]). Каждая строчка этого стихотворения со-
держит две пары слов. Каждой паре соответствует поле шахматной
доски: первая буква первого слова — столбец (буква в русском про-
изношении), первая буква второго — строка (цифра). Например:
Алеет Осень — A1, Ценными Дарами — C2, Еще Один — E1, Живо-
творящий День — G2 и т. д.
