Л. Я. ОКУНЕВ
КОМБИНАТОРНЫЕ ЗАДАЧИ
НА ШАХМАТНОЙ ДОСКЕ

Л. Я. О К У Н Е В
КОМБИНАТОРНЫЕ ЗАДАЧИ
НА ШАХМАТНОЙ ДОСКЕ
Опечатки
Стр.
23
23
24
32
Строка
2 снизу
3 »
9 сверху
11 снизу
Напечатано
2
/
2
аз—<*1=*
/V*+i, h-b + 1
Следует читать
п
п
Т
я* — */=!=
Azt—д-j-l, Ьг-b+l
По чьей
вине
Типограф.
»
Редактора
Типограф.
Окунев. Комбинаторные задачи на шахматной доске.
ОБЪЕДИНЕННОЕ НАУЧНО-ТЕХНИЧЕСКОЕ ИЗДАТЕЛЬСТВО НКТП СССР
ГЛАВНАЯ РЕДАКЦИЯ ОБЩЕТЕХНИЧЕСКОЙ ЛИТЕРАТУРЫ И НОМОГРАФИИ
Москва 1935 Ленинград

Т-23-6-4
ТКК Hi 109
АННОТАЦИЯ
Книжка содержит математическое исследование нескольких
знаменитых комбинаторных задач на шахматной доске, как,
например, задачи о восьми ферзях и задачи Эйлера о ходе
коня. При этом автор пользуется лишь средствами
элементарной математики. Несмотря на это решения многих задач
отличаются большим изяществом, и изучение их доставляет истинное
наслаждение. Книжка имеет большое образовательное значение.
Рассчитана она главным образом на молодежь и может быть
использована в работе математических и шахматных кружков.
Для чтения книги требуется знание алгебры в объеме курса
средней школы и наличие интереса к математике.
При составлении книги использованы как работы старых
авторов, так и новейшие исследования.

ПРЕДИСЛОВИЕ
Задачи, связанные с расположением и движением фигур на
шахматной доске, пользуются широкой популярностью на протяжении
почти двух столетий. Достаточно упомянуть такие задачи: обойти
конем все клетки шахматной доски (причем каждую клетку можно
проходить только один раз); расположить на шахматной доске восемь
ферэей так, чтобы они не угрожали друг другу, и т. д. Решение
подобных задач зачастую приводило к интересным арифметическим
и алгебраическим соотношениям, сами решения бывали обычно
оригинальны и остроумны, неудивительно поэтому, что этими задачами
занимались иногда и такие крупнейшие математики, как Эйлер и Гаусс.
Более простые из таких задач (например задача о восьми ладьях)
могли бы быть использованы для иллюстрации материала,
преподаваемого в курсе алгебры средней школы.
Предлагаемая книжка содержит сводный материал о
математических задачах на шахматной доске. Она рассчитана на читателя,
знакомого с курсом алгебры средней школы и имеющего некоторый
навык в работе с математической книгой.

ВВЕДЕНИЕ
Как известно, шахматная доска или шашечница представляет
собой квадрат, разбитый на 64 белых и черных квадратика,
называемых клетками. Ради общности выводов мы будем рассматривать
также квадратную шахматную доску, состоящую из п1 клеток, и даже
прямоугольную доску из pq клеток (р рядов по q клеток в каждом).
На этих клетках в том или ином порядке располагают шахматные
фигуры, и возникает естественный вопрос, каким образом можно
записать расположение фигур. На практике весьма употребителен
следующий способ записи: восемь колонн шахматной доски обозна-
Фиг. 1. Фиг. 2.
чают первыми буквами я, Ь, с, d9 e, f, g, h латинского алфавита
в порядке следования слева направо, а восемь строк занумеровывают
в порядке следования снизу вверх числами 1, 2, 3, 4, 5, 6, 7, 8
(фиг. 1). Таким образом любой клетке будут соответствовать
определенные буква и число -— именно те, которыми обозначены колонна
и строка, в которых эта клетка находится. Обратно, букве и числу
будет соответствовать определенная клетка. Например, клетка а\
есть клетка, находящаяся в первой колонне и первой строке, т, е.
левая нижняя угловая клетка.
Подобный способ записи годится для любых шашечниц. Однако
для нас такой способ записи не является вполне приемлемым, так

б
ВВЕДЕНИЕ
как нам необходимо добиться наиболее полного применения алгебры
к решению тех или иных комбинаторных задач на шахматной доске.
С этой целью попытаемся определить положение клеток с
помощью чисел. Читатель, наверное, уже догадался, что вместо букв
a, b, с, d, е, /, g, h надо ввести числа 1, 2, 3, 4, 5, 6, 7, 8.
Действительно, тогда каждой клетке будет соответствовать пара
чисел, и обратно. Эту пару чисел мы назовем координатами клетки,
причем число, являющееся номером колонны, назовем абсциссой,
а число, являющееся номером строки, — ординатой клетки.
Например, клетка Ь7 в нашей новой записи будет обозначаться так:
(2,7), причем 2 будет ее абсциссой, а 7 — ординатой (фиг. 2). Вообще
если мы имеем клетку с координатами х, у (х — абсцисса, а у —
ордината), то эту клетку запишем так: (х, у), причем внутри скобок
всегда будем писать сначала абсциссу, а затем ординату. Очевидно,
что эта запись положения клетки пригодна не только для шашечницы
из 64 клеток, но и вообще для любой шахматной доски.
В процессе игры распределение фигур на доске постоянно
меняется, и если мы захотим заняться исследованием законов
распределения данной совокупности фигур, то неизбежно должны будем
воспользоваться методами комбинаторного анализа. Как известно,
комбинаторным анализом называется математическая теория,
занимающаяся определением числа различных способов распределения данных
предметов в известном порядке. Для дальнейшего понадобится уменье
решать простейшие задачи этой теории, а именно определять
числа размещений, перестановок и сочетаний. Мы приводим лишь
определения и окончательные результаты, так как решение этих
задач читатель может найти в любом учебнике элементарной алгебры.
Пусть дано п предметов. Так как природа этих предметов нас
не интересует, мы можем занумеровать их в известном порядке
и вместо п предметов рассматривать п чисел:
1, 2, 3, ..., п (1)
и говорить только о числах.
Определение 1. Размещениями из п чисел (1) по т
называются такие группы чисел, которые можно составить из
чисел (1) так, чтобы каждая группа заключала в себе т чисел
и чтобы каждые две такие группы отличались друг от друга
или числами или порядком их следования.
Например, из трех чисел
1, 2, 3
^ожно составить шесть размещений по два числа в каждом:
1, 2; 2, 1; 1, 3; 3, 1; 2, 3; 3, 2.

ВВЕДЕНИЕ
7
Обозначим знаком А% число всех размещений из я чисел по т.
Можно показать, что
Л? = я(я-1)(я-2)...[я--(/я--1)]. (2)
Определение 2. Перестановками из я чисел называются
размещения из п чисел (1) по п.
Например, из трех чисел
1, 2, 3
можно составить всего шесть перестановок. Это будут:
1, 2, 3; 1, 3, 2; 3, 1, 2; 2, 1, 3; 2, 3. 1; 3, 2, 1.
Обозначим через Рп число всех перестановок из п чисел. По
определению имеем:
Поэтому из (2) следует:
Рп = я(я—1),..[л —(я—1)] = л(я—1)...2-1=хЬ2.3.../г,
т. е. Рп равно произведению всех натуральных чисел от 1 до я.
В математической литературе это произведение называется я-фак-
ториалом и часто обозначается сокращенно знаком я!. Итак,
Р„ = я1 (3)
Например,
Pf = 3l=b2.3 = 6.
И действительно, как мы видели выше, из трех чисел можно
составить всего шесть перестановок.
В заключение дадим определение сочетания.
Определение 3. Сочетаниями из п чисел по т называются
такие размещения из я чисел по т, которые отличаются друг
от друга по крайней мере одним числом.
Например, из четырех чисел 1, 2, 3, 4 можно составить такие
сочетания по 3:
1, 2, 3; 1, 2, 4; 1, 3, 4; 2, 3, 4.
Число С™ сочетаний из я чисел по т выражается следующей
формулой:
гт __ А™ __ п{п — 1)...[Я— (т — 1)] (Д\
Ьп-Р»- 1-2-3...л e W

Глава первая
ЗАДАЧА О ВОСЬМИ ФЕРЗЯХ
1 июня 1850 г, в «Иллюстрированной газете» под рубрикой
«Шахматы» была напечатана следующая задача:
Расставить восемь ферзей на шашечнице так, чтобы ни один
ферзь не угрожал другому.
Несколько позже (29 июля 1850 г.) там же было указано число 60
как число возможных решений задачи, но в действительности
решений оказалось больше, и уже в сентябре того же года было
напечатано истинное число всех решений, 92.
Знаменитый математик Гаусс, читавший «Иллюстрированную
газету», заинтересовался этой задачей и в своей переписке с другим
математиком, Шумахером, неоднократно упоминает о ней. Очень
скоро Гаусс нашел 72 решения задачи. Любопытно отметить, что
Гаусс сомневался в правильности числа 92 как числа всех решений.
В современной постановке задача формулируется в
следующем общем виде:
На квадратной шашечнице из /г2 клеток расставить п ферзей так,
чтобы ни один не угрожал другому. Определить число всех
решений.
Эта задача оказалась настолько трудной, что до сих пор не
найдено общих методов ее решения, несмотря на то, что целый
ряд математиков безуспешно пытался ее решить. О характере
трудностей мы поговорим несколько ниже, а пока заметим, что
задачу этого типа можно сформулировать не только для ферзей,
но и для других фигур, а именно для ладей и слонов, но в этих
случаях решение может быть получено несравненно легче. Поэтому
мы и начнем нашу главу разбором этих простейших случаев.
1. Задача о ладьях
Нам предстоит определить число всех таких расположений п
ладей на шашечнице из /г2 клеток, при которых ни одна ладья не
угрожает другой. Кроме того, мы попутно укажем метод,
позволяющий найти все расположения ладей этого рода. Решение задачи,
как мы сейчас увидим, не представляет особого труда.
Пусть п ладей расположено на шашечнице так, что ни одна
ладья не может бить другую.

§ 1] 8АДАЧА 0 ЛАДЬЯХ 9
Пользуясь способом записи клеток при помощи пар чисел, мы
можем это расположение ладей представить следующим образом:
(аиЬх)9 (#2, &2), ¦.., (an,bj. (1)
Очевидно, что в одной колонне две ладьи стоять не могут, так
как иначе они будут угрожать друг другу. Следовательно, все
числа av..., яп должны быть различны. Например, равенство ах = #2
невозможно, ибо в таком случае ладья (аи bt) окажется в одной
колонне с ладьей (а2, ?2). Итак, должно быть
Но эти п чисел могут принимать только значения целых чисел
от 1 до я, а потому
д1==1; я2 = 2; я3 = 3, ..., ап=п,
т. е. (1) можно переписать так:
(Mi), (Ma), .м (MJ. (2)
Точно так же и в одной строке не могут стоять две ладьи, а потому
числа bv Ь%9..., Ьп все различны. Так как эти п чисел могут
принимать значения от 1 до п, то среди чисел bv #3,..., Ьп должны
встретиться все числа 1, 2, 3, ,.. . ,я. Иными словами, bt, b^..., b9t
есть не что иное, как числа 1, 2, 3,...,пу расположенные в каком-
то порядке, быть может и не в натуральном. Таким образом,
bv Ь%1 • • • > Ьп является перестановкой всех чисел от 1 до п (см,
введение). Обратно, образуя из п чисел перестановку bv b^...ybn и
составив ряд (2), получим такое размещение ладей, при котором
ни одна ладья не может угрожать другой. Действительно, тогда
в каждой колонне и в каждой строке шашечницы будет находиться
только одна фигура. Итак, существует столько решений нашей
задачи, сколько можно составить перестановок из п чисел, и этим
исчерпываются все решения, т. е. мы имеем:
всех решений (см. введение). В частности, для обыкновенной
шашечницы я = 8 и Р8 = 8! = 1.2.3-4«5.6«7-8 = 40320— довольно
значительное число. Все эти решения можно получить, составляя
всевозможные перестановки из восьми чисел:
1, 2, 3, 4, 5, б, 7, 8в (3)

10 ЗАДАЧА О ВОСЬМИ ФЕРЗЯХ [гл. !
Мы не собираемся здесь заниматься утомительней и бесполезной
задачей составления 40 тысяч решений, а ограничимся только тре&:я
решениями. Самой простой перестановкой чисел (3) является,
очевидно, расположение в порядке возрастания, т. е. перестановка
1, 2, 3, 4, 5, б, 7, 8
Она приводит к следующему решению:
(1, 1); (2, 2); (3, 3); (4, 4); (5, 5); (б, 6); (7, 7); (8, 8),
или в обычной шахматной записи:
а\\ 62; сЪ\ dA\ еб; /б; g7; A8,
т. е. все ладьи расположены на главной черной диагонали. Другое
решение получим, взяв перестановку
8, 7, б, 5, 4, 3, 2, 1,
а именно получим:
(1, 8); (2, 7); (3, б); (4, 5); (5, 4); (6, 3); (7, 2); (3, 1),
или
я8; Ь7\ сб; db; eA\ /3; g2\ hi,
т. е. все ладьи находятся на главной белой диагонали,
Наконец, составив, например, перестановку
2, 1, 3, 5, б, 7, 8, 4,
получим:
(1, 2); (2, 1); (3, 3); (4, 5); (5, б); (6, 7); (7, 8); (8, 4),
или
а2; М; сЪ\ db\ еб; /7; g8, А4.
Предлагаем читателю самостоятельно разыскать какие-либо другие
решения.
Усложним несколько задачу о ладьях, а именно потребуем
дополнительно, чтобы ни одна фигура не стояла на главной черной
диагонали. Это добавление уже значительно затрудняет решение
задачи. Один из величайших математиков XVIII века, Эйлер,
пытался определить число Qn всех расположений п ладей на
шашечнице из п% клеток, не стоящих на главной черной диагонали и не
угрожающих друг другу, но он установил только соотношение:
<?» = ("-!)(<?„-!+ Q„-2). (4)
с помощью которого, зная Q^ и Qn_2, можно определить Qn.

§ 1]
ЗАДАЧА 0 ЛАДЬЯХ
11
Правда, пользуясь формулой (4), можно для данного п постепенно
вычислить Qn, но общая формула для Qn этим еще не определяется.
Это общее выражение Qn сравнительно недавно было найдено
с помощью символического исчисления, и только после этого было
дано элементарное решение задачи.
Выведем сперва формулу (4). В каждой колонне должна
находиться одна и только одна фигура. Допустим для определенности,
что в первой колонне ладья стоит на клетке Ь (фиг. 3). Вообще
же ладья может занимать (п— 1)
положений, так как угловая клетка
лежит на главной черной диагонали
и потому исключается. Возможны
только следующие два случая:
a) В первой строке имеется
фигура b', симметричная с b относительно
диагонали аа!. Иными словами,
абсцисса клетки Ь' равна ординате
клетки Ъ (фиг. 3).
Тогда, уничтожая строки и
колонны, проходящие через b и Ь\
получим шашечницу из (я —2)а клеток,
на которой расположены (/г —2)
остальные фигуры, причем эти ладьи
можно разместить на получившейся
шашечнице Qa^ способами. Но b может занимать (п—1)
положений в первой колонне. Поэтому будем иметь всего (я — l)Qrt_2
расположений типа а).
b) В первой строке стоит фигура с, не симметричная с b
относительно диагонали аа'. Переставим между собой колонны,
содержащие b и с. После такой перестановки с займет положение а,
a b окажется на недиагональной клетке. Уничтожая затем строку
и колонну, проходящие через а> получим шашечницу из (л—I)4
клеток и на ней (/г— 1) ладей, не угрожающих друг другу и не
находящихся на главной диагонали. Следовательно, всего
размещений типа Ь) будет (я—-1) Qn_v
Так как этими случаями исчерпываются все возможные случаи, то
или, вынося (п—1) за скобку, получим равенство (4) Эйлера.
Теперь постараемся выразить Qn через п. Как мы выше указали,
существует два решения: элементарное и с помощью методов
символического исчисления. Мы ограничимся здесь только первым,
ь
и.
/
/
Ал
/
/
с
/
/
7\
[
1

12
ЗАДАЧА О ВОСЬМИ ФЕРЗЯХ
[ГЛ. I
а второе решение интересующийся может найти в добавлении *.
Прежде всего непосредственно можно убедиться, что Q%==1 и
Q3 = 2, В самом деле, на шашечнице из четырех клеток можно
расставить ладьи только одним единственным способом (фиг. 4;
ладьи обозначены кружочками), а на шашечнице из девяти клеток —
двумя способами (фиг. 5 и 6).
\о
\/
о
/
.
/\
о 1
Фиг. 4. Фиг. 5. Фиг. б.
Обратим внимание на следующий факт: если к 3Q%
прибавить ( — I)3, то получится как раз Q3. Покажем, что этот факт
имеет место для любого Qn, т. е. что
Q»=>*Q»-t+(-i)n. (5)
Вполне достаточно показать, что если справедливо равенство
<?* = *3м +(-1)* (6)
для всех ?<я — 1, то равенство (5) также имеет место. Для этого
переписываем равенство (4) так:
Согласно (6):
отсюда:
Подставляя это значение (п— l)Qn_2 в выражение Эйлера для Qn,
получим:
т. е. равенство (5) 2.
* См. добавление, § 16.
2 Метод, которым мы доказали равенства (5) или (б), называется методом
математической индукции.
Он основан на следующем принципе: пусть некоторое правило [например
формула (б)] верно для k = l; пусть, каждый раз, когда это правило ока-
Го
z
121
—i
о]
[о
V.
/
О
А
о
1

§ 1] ЗАДАЧА О ЛАДЬЯХ 13
Теперь без труда можно получить выражение Qn через п. Для
этой цели делим обе части (5) на п\
Qn_nQn^ (-1)»
/г!"" п\ ^ п\ '
или, по сокращении:
Qn_ Qn-i . (~l)n
п\ —(л— I)!"1" /г! "
Полагая /г последовательно равным /г, (/г.—1), (л—-2),. • .,3, будем
иметь ряд равенств:
я! (/z—l)!"1" «I >
Q»-i _ 0^2 , (-i)-1.
(л—1)!~(л —2)!"1*" (л—l)! *
Q*-2 _ Qn-г , (~1)^2,
(n — 2)1 — (« — 3)1 "^ (« — 2)1 >
<?3_C?2 . (-D3
3! ~~ 21 r 3!
Складывая все эти равенства, мы после некоторых сокращений
получим искомую формулу:
<?«_(-!)" , (-1)»-* , , (-I)* , Q2
л!"" л! "*"(«—1)! ^ """r 31 ^21»
или, помножив обе части на /г!, заменяя Q2 единицей и
переписывая правую часть в обратном порядке, получим окончательно:
зывалось верным для всех целых положительных чисел &</г, оно
оказывается верным для k = n; тогда наше правило верно для всех целых
положительных значений к
В самом деле. Оно верно для k=l, т. е. для всех целых k, меньших 2,
Но тогда по условию оно верно для k = 2.
Поскольку это правило верно для k = 1 и для k = 2, т. е. для всех
целых чисел к, меньших 3, оно верно и для k = S; но раз оно верно
для k = l, 2, 3, то оно верно для k = 4. Таким же образом мы
последовательно убеждаемся в верности нашего правила для & = 5, б, 7,... Мы
делаем сразу заключение, что наше правило верно для всех целых
положительных чисел /г.

14
ЗАДАЧА О ВОСЬМИ ФЕРЗЙХ
[гл. i
По этой формуле для обыкновенной шашечницы (полагая я*=8)
получим:
решений типа Эйлера
2. Задача о слонах
Определение числа Fn всех расстановок п слонов на шашечнице
из /г2 клеток значительно сложнее предыдущей задачи с ладьями.
До сих пор еще неизвестна общая формула числа этих
расстановок1, хотя некоторые методы здесь имеются* Относительно
обыкновенной доски из 64 клеток задача была решена французским
математиком Перротом, и мы в этом параграфе приведем
изложение его решения, но ради простоты ограничимся доской
из 16 клеток.
Назовем слона черным, если он стоит на черной клетке
шашечницы, и белым, если он стоит на белой клетке. Очевидно, что
требуемым образом можно расставить три белых и одного черного
слона, два белых и два черных слона и т. д. Далее ясно,
что&(&<3) одноцветных слонов можно расставить так, чтобы ни
один слон не угрожал другому. Обозначим через fk число подобных
расстановок. Произведение fJefs(k + s<4) означает, сколькими
способами можно расставить k белых, 5 черных или s черных и к белых
слонов так, чтобы они не угрожали друг другу. Отсюда получаем:
Ъ=/.Л +ЛЛ+fift=2ЛЛ +/|.
Поэтому все сзодится к определению чисел ft} Д, /3. Как же
подсчитать эти числа? Отметим крестиками все одноцветные клетки
шашечницы, например белые клетки. Получим такую схему (фиг. 7).
Повернем затем шахматную доску на 45° по часовой стрелке,
Тогда крестики примут следующее положение (фиг. 8).
Движение белого слона на шашечнице (фиг. 8) уже ничем не
будет отличаться от движения ладьи. Поэтому мы приходим к
такой задаче:
Сколькими способами можно расставить k ладей (&= 1,2,3) на
шашечнице (фиг. 8) из восьми клеток так, чтобы ни одна ладья
не угрожала другой?
* Сравнительно недавно эта задача была полностью решена С. Е. Арнюном.
Его результаты будут опубликованы в сборнике «Математическое
просвещение» № 8

§ 2]
ЗАДАЧА О СЛОНАХ
15
Рассматриваемую шашечницу можно дополнить до прямоугольной
шашечницы, добавив четыре клетки (фиг. 8; дополнительные клетки
отмечены точками). Таким образом шахматная доска (фиг, 8)
состоит из двух частей: клетки первой части отмечены точками,
а клетки второй части — крестиками.
Сначала займемся решением одной вспомогательной задачи.
Пусть шашечница состоит из pq клеток: р клеток в ширину
и q клеток в длину. Обозначим через Ег число возможных
расстановок г ладей на этой доске. Пусть теперь клетки шашечницы
разбиты на две части. Назовем рассматриваемое расположение г
ладей расположением (s+ 1)-го класса, если (r—s) фигур нахо-
] •
1 +
1 +
] •
+
+
+
+.
•
+
+
• 1
W'
+
+
+
¦ III.
+
+
+ 1
+
Фиг. 7. Фиг. 8.
дятся на клетках первой части, а остальные s фигур на клетках второй
части. Обозначим символом Tsr число расстановок (s+l)-ro класса:
?г=7? + 7г1+...+П. (8)
Возьмем решение класса s. Очевидно, что (p — r) (q — г) клеток,
лежащих на пересечении (р — г) колонн и (q— г) строк, будут
свободны от обстрела фигур. На одну из этих клеток можно
поставить новую ладью, и она не будет бита. Следовательно, мы
получаем:
(p-rXq-дГГ1 (9)
расположений г+1 фигур, не угрожающих друг другу.
Не все из числа этих (р — r)(q — г) Т*т~~1 решений действительно
различны. Некоторые из них тождественны. Для установления числа
тождественных решений заметим прежде всего, что среди решений
этого типа одни принадлежат к классу 5, другие к классу s +1,
в зависимости от того, находится ли новая ладья на клетке первой
или на клетке второй части. Легко далее видеть, что среди этих
решений имеется:
(г-8+2)Гг + \ (Ю)
решений класса s. В самом деле, в этом случае (r—s + 2) ладьи
стоят на клетках первой части и среди них наша новая ладья.

16
ЗАДАЧА О ВОСЬМИ ФЕРЗЯХ
[гл. i
Любую из (г—5 + 2) ладей можно принять за эту новую ладью,
откуда и получается формула (10). Подобным образом получаем:
srr+1 rii)
решений класса (5+1). Так как решениями (10) и (11)
исчерпываются все решения (8), то имеем в конечном счете:
(p-r)(q-r)T8r-1 = (r-~s + 2)T:.+ \ + sTar+v (12)
Если известно решение задачи и расстановка ладей для одной
части доски, то с помощью формул (8) и (12) задача решается
для второй части доски и для всей шашечницы. Таким образом
наша цель достигнута.
Возвратимся опять к прямоугольной шашечнице из 12 клеток
(фиг. 8). Здесь точками обозначены клетки первой части, а
крестиками— клетки второй части шашечницы. Для первой части
можно установить эмпирически, что
7Х° = 4; 7? = 2; 7§ = 74° = 0; 7} =8.
Действительно, так как первая часть доски состоит из четырех
угловых клеток, то одну ладью можно разместить на этих клетках
четырьмя способами, откуда 7? = 4. Две ладьи на клетках первой
части можно разместить двумя способами так, чтобы они не
угрожали друг другу. Отсюда Т$ = 2. Три ладьи уже нельзя разместить
требуемым образом: они постоянно будут бить друг друга, и
потому 7з=0. Подобным же образом имеем 72^=0. Наконец,
вторая часть доски состоит из восьми клеток, и потому 71 = 8,
Теперь воспользуемся формулой (12). Имеем:
р = 3 и # = 4,
откуда:
(4-0(3-г) Т8Г1 = (г-8 + 2)^1 + 3^. (13)
Полагая в (13) /-==1 и 5 = 1,2, получим:
3.27? = 27§ + 72г;
3.27} = 71+ 271;
откуда:
72 = 20 и 71=14.
Следовательно, во второй части шашечницы две ладьи можно
расставить 14 способами так, чтобы ни одна не угрожала другой.

§3]
ЗАДАЧА О П ФЕРЗЯХ
17
Для г~2 и 5=1,2,3 получаем:
2720 = ЗГз° + П;
27i = 7* + 37&
откуда:
Г32-16;
П = 4,
т. е. три ладьи можно расставить четырьмя способами на второй
части шашечницы так, чтобы ни одна фигура не угрожала другой.
Возвращаемся теперь к первоначальной задаче о слонах. Мы
выше построили шашечницу, состоящую из двух частей (фиг. 8).
Мы только что получили для нее:
Т{ = 8;
Г* = 14;
Г,' = 4.
Но Т\, 1\у Т\ суть не что иное, как fv /2, /3, откуда:
Z7* = W» +/22 = 2 • 8 • 4 + 142 = 260,
т. е. на шахматной доске из 16 клеток задача с четырьмя слонами
допускает 260 решений. Подобным же образом Перрот установил
22 522 960 решений для обыкновенной шашечницы из 64 клеток.
3. Задача о п ферзях
Как выше уже было указано, задача эта пока еще не решена,
но все же кое-какие результаты получены. Прежде всего вполне
естественно поставить вопрос, допускает ли задача решение для
всякой шашечницы? Оказывается, что для шашечниц с 4 и 9
клетками решений не существует. В этом читатель легко может
убедиться непосредственно. Для 16 клеток (п = 4) существует
следующее решение (фиг. 9).
Здесь крестиками отмечены ферзи. Попробуем определить все
решения при п = 4. Поступим, следуя Гауссу, таким образом.
Прежде всего легко видеть, что в каждой строке должен стоять
один и только один ферзь. Поэтому на одной из клеток первой
строки а\\ Ъ\\ c\\ d\ (фиг. 10) обязательно должен находиться

IS
ЗАДАЧА О ВОСЬМИ ФЕРЗЯХ
[ГЛ. I
ферзь. Допустим, что ферзь находится на а\ и отметим
кружочками все клетки, обстреливаемые этим ферзем (фиг. 10). Второго
ферзя надо поместить на одну из клеток второй строки. Имеется
выбор лишь между клетками с2 и й, Если мы поставим ферзя
на клетку с2, то второй ферзь будет обстреливать клетки ЬЪ
и я(3, и потому для третьего ферзя не найдется на третьей строке
свободного места, так как треть?, строка будет вся заполнена кру-
+'
+
+'
' "*1
+
4
3
2
1
о
о
о
+
о
О
о
±1
¦о]
А
abed
Фиг. 9.
abed
Фиг. 10.
жочками. Если же мы поставим ферзя на d2, то единственной
свободной клеткой на третьей строке будет ЬЗ, но, поставив на
на нее третьего ферзя, мы не найдем свободной клетки на
четвертой строке для четвертого ферзя. Следовательно, решение задачи
с ферзем на а\ невозможно. Предположим теперь, что первый ферзь
стоит на М; тогда мы получим такую картину (фиг. 11). На
второй строке имеется только одна свободная клетка d2; на нее мы
А
3
2.
1
о
о
О
о
О
+
о
о
О
о |
abed
Фиг. 11.
+
1 + 1
+ ' I
+
abed
Фиг. 12.
поставим второго ферзя. Тогда на третьей строке окажется
свободной только клетка #3, и на нее мы поставим третьего ферзя.
Четвертого ферзя остается поставить на с4. Таким образом
получится первое решение, а именно то решение, которое нами было
указано раньше (фиг. 9).
Если поставить первого ферзя на с\ и затем рассуждать, как
выше, то получится второе решение задачи, но, пользуясь первым
решением, можно поступить гораздо проще. А именно, обратим
чередование колонн фиг. 9, т* е. колонну d поставим на место

§3]
ЗАДАЧА О П ФЕРЗЯХ
19
Li.
1
1 1
-™
,+
1
+
+
+
колонны а у колонну с на место колонны Ь, колонну Ъ на место
колонны с й, наконец, колонну а на место колонны d и заново
обозначим переставленные колонны буквами а, #, с> do Получим после,
этого новое, второе решение задачи с ферзем на с\ (фиг. 12).
Назовем такую перестановку колонн зеркальным отражением
колонн. Пользуясь методом зеркального отражения, легко показать,
что не существует решения с ферзем на dl. Действительно, если
бы задача допускала такое решение, то, отражая зеркально колонны,
мы получили бы решение с ферзем на al, что, как мы выше
видели, невозможно. Отсюда вытекает, что для шашечницы из 16
клеток (т. е. при я = 4) существует всего два решения: с ферзем
на М ис ферзем на с\.
Теперь, обращаясь к шахматной доске из 25 клеток (п = 5), мы
можем с уверенностью сказать, что и здесь
задача о ферзях имеет решение.
Для этого заметим, что если на шашечнице
из /г2 клеток возможно такое решение, при
котором хотя бы одна главная диагональ
не занята ферзями, то отсюда сразу
получается решение на шашечнице из (я+1)2
клеток. А именно края шашечницы,
примыкающие к угловой клетке рассматриваемой
диагонали, окаймляются двумя
прямоугольными полосками так, чтобы получилась доска
из (n+lf клеток, и тогда достаточно
поставить на новую угловую клетку нашей диагонали (п+ 1)-й ферзь,
чтобы получилось искомое решение задачи. Так, например, из решения
с ферзем на с\ (фиг. 12) можно получить следующее решение для
шашечницы из 25 клеток (фиг. 13), которое мы запишем сокращенно
так: (5, 2, 4, 1, 3). Первое число 5 означает, что ферзь первой
колонны стоит на пятой клетке, второе число 2 показывает, что
ферзь второй колонны стоит на второй клетке, и т. д. Наконец,
последнее число 3 показывает, что ферзь последней колонны
находится на третьей клетке. Этот способ записи, очевидно, годится
для любой доски и является весьма удобным.
Для 16 клеток мы нашли всего два решения задачи* Значительно
большее число решений получается для доски из 25 клеток,
Так, уже из (5, 2, 4, 1, 3) можно легко получить новые реше*
ния с помощью поворота шахматной доски на 90°, 180°, 270° по
часовой стрелке. Этим способом мы получим последовательно три
решения:
(2, 4, 1, 3, 5);
(3, 5, 2, 4, 1);
(1, 3, 5, 2, 4).
!
2 3 4
Фиг. 13.

20
ЗАДАЧА О ВОСЬМИ ФЕРЗЯХ
[ГЛ. I
Затем применим метод зеркального отражения к (5, 2, 4, 1, 3)
(2, 4, 1,3, 5), (3, 5, 2, 4, 1) и П, 3, 5, 2, 4). Получим
соответственно еще четыре решения:
(3, 1, 4, 2, 5);
(5, 3, 1, 4, 2);
(1, 4, 2, 5, 3);
(4, 2, 5, 3, 1),
причем легко видеть, что зеркальное отражение сводится к
переписыванию чисел в обратном порядке. Например, записывая (5, 2,
4, 1, 3) в обратном порядке, получаем (3, 1, 4, 2, 5).
Невольно напрашивается такой естественный вопрос: сколько
вообще новых решений можно получить, вращая доску и отражая
колонны. Ответом служит следующее предложение.
Теорема. Поворачивая доску (из л2 клеток) и отражая
зеркально колонны, мы всегда получим либо одно, либо три, либо
семь новых решений из одного.
Доказательство сводится к последовательному разбору четырех
возможных случаев:
a) При повороте доски на 90° (по часовой стрелке) получается
первоначальное решение.
b) При повороте доски на 90° получается новое решение, но
при повороте на 180° мы приходим к первоначальному решению.
c) При повороте доски на 90° и 180° получаются новые решения,
но поворот на 270° приводит к первоначальному решению.
d) При повороте доски на 90°, 180°, 270° получаются новые решения.
Легко видеть, что из случаев а), Ь), с) и d) случай с)
невозможен. В самом деле, обозначим через А первоначальное решение,
а через В и С—решения, получающиеся при повороте на 90°
и 180° (по часовой стрелке). Повернем доску на 270°. Получим
решение Л. Повернем затем доску еще на 90°. Тогда получим,
с одной стороны, В, а. с другой стороны, А, так как 270° + 90° = 360°.
Следовательно, решения В и А должны совпадать, что невозможно,
так как В, по условию, отлично от А
Итак, остаются только три случая: а), Ь) и d).
В случае а), с помощью отражения колонн, получим только
одно новое решение.
В случае Ь) получим всего три решения: одно с помощью
вращения и два с цОмощью вращения и отражения колонн.
В случае d) получается всего семь новых решений: три
вращением доски и четыре с помощью вращения и отражения колонн.
Таким образом наше предложение доказано полностью.

§ 3]
ЗАДАЧА 0 П ФЕРЗЯХ
21
Решения типа Ь) называются симметрическими, а типа а) дважды
симметрическими решениями.
Все эти методы, известные еще Гауссу, сильно облегчили
решение задачи для случаев шашечниц из 25, 36, 49 и 64i клеток,
но при дальнейшем увеличении числа клеток определение числа
решений (и самих решений) становится все более и более
громоздким и трудным.
Кроме того, эти методы годятся только для исследования
частных случаев, и потому с их помощью задачу в общем виде решить
невозможно. К сожалению, до сих
пор не удалось найти общих методов,
позволяющих установить формулу
числа решений для шашечницы из п2
клеток.
Известный немецкий математик
Ландау пытался решить такую
задачу:
Сколькими способами можно
расставить k ферзей на шахматной
доске из /г2 клеток так, чтобы ни
один ферзь не угрожал другому.
Очевидно, что при k=n мы
получим обычную общую задачу о
ферзях, сформулированную нами еще Фиг. 14.
в самом начале этой главы. Ландау
удалось решить свою задачу только для случая двух и трех ферзей
(т. е. для k = 2 и 6 = 3), причем получились довольно громоздкие
и неприятные формулы (см. главу II, § 8, стр. 53). Таким образом
и этот путь оказался нерациональным. Но если до сих пор
решение задачи не найдено, то возникает естественный вопрос: можно
ли вообще на шашечнице из /г3 клеток расставить п ферзей так,
чтобы ни один ферзь не угрожал другому?
Ответ на этот вопрос читатель найдет в следующем параграфе,
а сейчас в заключение мы приведем следующее любопытное
свойство дважды симметрического решения.
Теорема. Если для шашечницы из я2 клеток число п может
быть представлено в виде 4k + 2 или 4k + 3, то на такой
шахматной доске не существует дважды симметрических решений.
Доказательство. Допустим противное. Пусть существует
дважды симметрическое решение.
Пусть ферзь первой колонны занимает положение а (фиг. 14).
Повернем доску на 90°. Тогда ферзь займет положение av
* Зсе решения для обычной шахматной доски приведены в добавлении, § 17.
а
а,
°з
а2\

22
ЗАДАЧА 0 ВОСЬМИ ФЕРЗЯХ
[ГЛ. I
Повернем еще раз доску на 90°, ферзь из положения а± перейдет в av
Наконец, поворачивая доску еще раз на 90°, получим ферзя на клегке az.
Так как решение дважды симметрично, то ферзю а обязательно
должны соответствовать три ферзя at, #2, az.
Подобным же образом можно показать, что если ферзь не
стоит на центральной клетке, то ему должны соответствовать три
ферзя, с которыми он последовательно совпадает при повороте
доски на 90°, 180° и 270°. Следовательно, все ферзи, кроме
центрального (если только он существует), можно сгруппировать так,
чтобы в каждой группе находилось четыре ферзя, причем один из
ферз:й группы при повороте на 90°, 180° и 270° совпадает с
остальными тремя. Поэтому, так как всего имеется п фигур, получаем,
что n = 4k, если шахматная доска не содержит центральной клетки,
и n~4k+ 1, если существует центральная клетка. Но, по условию,
я = 4ft+ 2 или /z=4ft + 3, что несовместимо с условиями п — 4k и
/г —4ft+l. Таким образом мы пришли к противоречию.
Из этой теоремы, в частности, следует, что для шашечниц из
36 и 49 клеток не существует дважды симметрических решений.
4. Существование общего решения задачи о п ферзях
Расставим произвольно п ферзей на доске из я2 клеток так,
чтобы в каждой колонне находился только один ферзь. Пусть
расположение фигур окажется следующим:
(а±\ а%, ..., aj.
Мы собираемся доказать такую теорему:
Если ах — ак или аг—<ак = ±(1— ft), то ферзи (/, aL), (ft, аК)
угрожают друг другу] в противном случае они не угрожают
друг другу.
Доказательство. Первое очевидно, тац: как ферзи находятся
на одной горизонтали в том и только в том случае, когда ак = аГ
Что касается второй части теоремы, то можно показать, что наши
ферзи находятся на одной диагонали только в том случае, когда
(#г —#A) = /~ft или (tfj — яА)= — (/ — ft).
В самом деле, пусть для определенности /> k. Клетки
(ft, Oj) и (ft+1, ак+1)
находятся на одной диагонали, так как две клетки смежных колонн
лежат на диагонали, если ордината второй клетки на единицу
больше или меньше ординаты первой клетки. Точно так же
(ft+1, ah+l) и (ft + 2, ah + 2)
находятся на той же диагонали, что и (ft, ак) и (ft+1, ^+l)e

§ 4] СУЩЕСТВОВАНИЕ ОБЩЕГО РЕШЕНИЯ ЗАДАЧИ О П ФЕРЗЯХ 23
Продолжая наши рассуждения до (/, ак + (1 — ft)), получим, что
пес клетки
(А, Л*), (*+li **+!)• -.-, (', ** + ('-*))
лежат на общей диагонали. Аналогичным образом можно получить
вторую диагональ:
(ft, <д, (ft+1, tfA-l), (ft+ 2, 0,-2), ...,(/, д4_(/.-А)),
проходящую через (ft, я7.). Но через (ft, tffc) могут проходить
только две диагонали. Поэтому, если
аг-ак^±(!-к) и (/>ft),
то клетки (ft, яЛ) и (/, аг) заведомо
не лежат на диагонали.
Теперь с помощью доказанной
теоремы задачу о п ферзях можно свести
к такой задаче:
Подобрать п чисел 1
av #2, ..., йп
(где av...,an могут принимать
значения от 1 до я), так, чтобы
Фиг. 15.
л4Ф*, и (^-<> + ±(/-ft) (14)
для всякой пары чисел ак и av и определить число решений задачи.
Первую половину задачи удалось решить сравнительно легко.
Так, Паульс нашел для n = 6k или 6ft+ 4 следующее решение:
2, 4, 6, ..., /г, 1, 3, 5, ..., (л-1). (15)
Читатель легко может проверить, что приведенный ряд чисел
удовлетворяет условиям (14).
Проверки сводятся к последовательному разбору трех
возможных случаев:
a) Индексы ft и / чисел акУ ах ряда (15) не превосходят ^.
b) Индексы ft и / чисел аю аг больше ^.
о
о
о
о
о
о
0
щ
1 Здесь и ниже число п предполагается больше 3.

24 ЗАДАЧА О ВОСЬМИ ФЕРЗЯХ [ГЛ. 1
с) Индекс k числа ак не превосходит -~, а индекс /
числа ах больше тт •
В случае a) ak-=2k\ #г = 2/ и потому (ак-— ах ф =!=(? — /),
так как, предполагая противное, получим нелепое равенство:
2{k — /)=rt=(ft — /)
или по сокращении на & — /
2=±:1.
В случае Ь) #fc = 2s —1 и яг = 2^—1, где s = &— ^,
t = l— —, откуда ak — aL = z*z(k--l). В самом деле,
предполагая противное, получим, как и выше, нелепое равенство
2(5 — 0 = =t(s — 0, или 2==Ь1.
Наконец, в случае с) ak = 2k, аг = 2?—-1, где ? = /— ~,
откуда равенство ak — al=±(k—-l) примет следующий вид:
2(A_9 + l=±[(*--0-J].
Беря знак плюс, получим:
2(* —0+1=(* —0 —f
или
что невозможно при 0 < & < ^; О <Ч < 5 •
Беря знак минус, получим:
2{k-i) + l=-(k-t) + %t
или после очевидных преобразований:
6 (?-0 + 2=^
что опять-таки невозможно при n = 6k и // = 6/г + 4.
Таким образом и в случае с) cik — al ф (Л—-/),

§ 4] СУЩЕСТВОВАНИЕ обЩЕГО РЕШЕНИЯ ЗАДАЧИ О Я ФЕРЗЯХ 25
Для я = 6& + 2 тем же Паульсом было установлено решение:
4, (л-2), (я-4), ...,8, 6, я, 2, (я-1),
1, (я —б), (я —7), ..., 3, (я —3). (16)
Например при я = б + 2 = 8 (здесь k = 1) получаем, согласно (16),
решение:
4, (8-2), 8, 2, (8-1), ;, (8-5), (8-3)
или окончательно:
4, 6, 8, 2, 7, 1, 3, 5.
В решениях (15) и (16) клетки главных диагоналей свободны
от ферзей. Поэтому, согласно замечанию, сделанному в
предыдущем параграфе (стр. 19), мы имеем следующие решения для
нечетных я.
Если я=г6Л+1 или я = 6/г + 5, то решением будет:
я, 2, 4, б, ...,(я-1), 1, 3, 5, ...,(я-2).
Если я = 6А + 3, то решением будет:
я, 4, я —3, ..., 8, 6, (я—1), 2, (я —2),
1, (я-6), (п^8), ...,3, (я-4).
Таким образом для я вида б&, 6&+1, б&-)-2, б/г + 3, 6& + 4,1
6? + 5, где &>1, т. е. для любого я>б нам удалось установить,
что задача имеет решение. Поэтому теперь мы можем с
уверенностью сказать, что задача о я ферзях при я]>3 всегда
допускает решение.
Французский математик Люка предложил другой метод
определения решений, пригодный не для всех я.
Он взял произвольное число а и число d, такое, что числа
d—l, d+l и d не имеют общего делителя с я, и составил
арифметическую прогрессию:
я, a + d, a + 2d} ..., а + (п— \)d.
Затем он составил ряд остатков, полученных при делении
каждого члена прогрессии на я 1. Пусть ai — остаток, полученный при
1 Причем, еслц число делится на пг мы берем в качестве остатка я,

26
ЗАДАЧА О ВОСЬМИ ФЕРЗЯХ
Ггл I
делении а на я, а2 — при делении a-\-d на п и т. д.; наконец, ап
остаток, полученный при делении а + (п— l)d на п. Тогда
ряд чисел
ctv cttv ..., йп
и будет искомым решением задачи, если только п не делится на
2 или на 3.
Например, при п = 5 имеем, положив a = l> d = 2,
арифметическую прогрессию:
1, 3, 5, 7, 9;
откуда получается такое решение:
(1, 3, 5, 2, 4)
для шашечницы из 25 клеток.
Докажем, что метод Люка действительно приводит к цели, когда п
не делится на 2 или на 3. Возьмем />-й и ^-й члены нашей
арифметической прогрессии. Это будут, очевидно,
up = a + (p—l)d и uq = a + (q — l)d.
Вычтем из первого числа второе. Получим:
[a + G*-l)rf]-[a+ (?-1)<*] = (/>-?)<*
Обозначим остатки и частные от деления и и ид на я
соответственно через ар} Ьр и я2, Ьп. Так как делимое равно частному,
умноженному на делитель, плюс остаток, то имеем:
ир = nbp + ap\ uq = nbq + aq.
Мы должны показать, что ap^aq и я^ — aq ф ±(p — q).
Первое вполне очевидно, так как если бы ap=aq, то и^ — uq = (p — q)d
делилось бы на /г, что невозможно, так как d не имеет общего
делителя с /г1, а /7 — #ф0 и меньше я и потому не может
делиться на п.
Следовательно, остается показать, что (ар — ад) ф :±:(р — q).
Допустим противное; пусть ар — aq = ^z{p — q). Тогда
ttp — U9 = n(bp — bq)+(ap — a9) = n(bp'-bu):±(P--9)-
i В этом случае обычно говорят, что числа dan взаимно-просты.
Например, числа 15 и 16 взаимно-просты, так как у них нет общего делителя.

§ 4] СУЩЕСТВОВАНИЕ ОБЩЕГО РЕШЕНИЯ ЗАДАЧИ О П ФЕРЗЯХ 27
С другой стороны, мы имеем:
*p — *t = (p — 9)*i
откуда
(p—g)<t=*(bp—bq)±(p—g)t
я ли
(P-g)d + (p-q)=:n(bp — bQ)}
т. е. окончательно:
(p-g)(d+l) = n(bp-bq).
Иными словами, (p — q)(dz+il) делится на п. Но d— 1 и rf+1
взаимно-просты с п. Поэтому на п должно делиться число р — д.
Но это возможно только в том случае, когда р—# = 0 или р = д,
а между тем у нас р ф д. Следовательно, остается допустить, что
(S-^) + — (р-д).
В заключение заметим, чго когда п делится на 2 или на 3, нельзя
подобрать d так, чтобы dy d—1 и d+1 были взаимно-просты
с п. В самом деле, если п делится на 2, то d, как взаимно-простое
с //, должно быть нечетным; но тогда d±\ будут четными и
потому не будут взаимно-просты с п. Если же п делится на 3, то d,
как взаимно-простое с я, не будет делиться на 3 и потому может
быть представлено в виде 3k+1 или 3k—1.
В случае d = 3k+l число d—1=3& не взаимно-просто с я,
а в случае d=3k—1 число d+l=3k не взаимно-просто с п.
Когда же п не делится на 2 или на 3, число d всегда можно
подобрать требуемым образом.

ГЛАВА ВТОРАЯ
ДВИЖЕНИЕ ФИГУР
Здесь мы займемся решением следующего вопроса: сколькими
способами может какая-либо шахматная фигура с клетки (я, Ь)
перейти на клетку (av &t), двигаясь все время в поступательном
направлении. Мы увидим ниже, что эта задача в некоторых случаях
(движение ладьи) имеет тесную связь с аддитивной теорией чисел, т. е.
с той частью науки о целом числе (называемой теорией чисел),
которая посвящена решению вопроса о разбиении числа * на сумму
слагаемых. Прототипом задач подобного рода является задача
о гирях: как взять п чисел ах, #2,..., ап так, чтобы всякое число
могло быть представлено в виде алгебраической или
арифметической суммы чисел #г, я 2,..., ап, Она была рассмотрена еще
Леонардом Фибоначчи, крупнейшим из европейских математиков
средних веков.
Шахматные фигуры можно разделить на две категории: фигуры
дальнодействующие и фигуры не дальнодействующие. К первой
категории относятся слон, ладья и ферзь, а ко второй — конь
и король. Мы начнем нашу главу с простейшего случая, а именно
с исследования движения короля.
5. Движения короля
Пусть, например, король стоит на клетке е4.
В один ход он может переместиться на одну из восьми клеток еЗ,
е5, d4, /4, d3, /5, /3, db.
Спрашивается — какие из этих перемещений следует считать
поступательными? Условимся в дальнейшем под поступательными
движениями короля подразумевать движения типа:
е4 — е5, е4—/4 и е4—/5,
т. е. вверх, вправо и вправо-вверх, причем мы эти движения
обозначим соответственно стрелками | , —* и /*.
Предположим, что король начинает свое движение от угловой
клетки (1, 1), двигаясь все время поступательно в двух
направлениях | и —>. Поставим задачу:
1 Под числом мы здесь и ниже постоянно будем подразумевать только
целое число.

§5]
ДВИЖЕНИЯ КОРОЛЯ
29
Сколькими способами король может дойти с клетки (1, 1) до
клетки (х, у)?
Обозначим искомое число способов через FXty. Очевидно, что
наша фигура может пройти на клетку (л:, у), либо проходя через
(х, у—1), либо через (х — 1, у). Но клетку (х, у — 1) король
может достичь Fm ± способами, а клетку (х — lyy) Fx_Uy
способами, откуда сразу получается простое соотношение:
р — р \ р
(1)
позволяющее вычислить Fa
х,у>
только известны Fx,y_x и Fx_Uy.
если

Нетрудно сообразить, что FXil='l при
всяком л;, так как клетку (л:, 1) король
может достичь, двигаясь все время
только в направлении —». Точно так же
Z7 =1 при всякому* Поэтому
получим, например, что
^2=^,1 + Л,с,= 1 + 1=2;
^• = ^,i + /7i.t = 2+l=3;
^и = ^и + 'ь1==3 + 1=4
и т. д. Очевидно, что мы, действуя 12345678
подобным образом, вычислим FXi7/
для любой клетки шашечницы. Фиг. 16.
Выпишем в каждую клетку (х, у)
вычисленное для нее число Fx . После такого выписывания
шахматная доска примет следующий вид (фиг. 16), т. е. мы получим
так называемую арифметическую шашечницу.
Попробуем теперь выразить Fx через х и у. Для этого
обозначим цифрой 1 перемещение —>, а цифрой 2 перемещение | .
Король может перейти от клетки (1, 1) к (х,у), совершив л:—1
горизонтальных ходов ~* и у—1 вертикальных ходов ] ,
Например, он может перейти на (х, у) следующим образом:
8
7
В
5
4
3
2
1
1
1
1
1
1
1
1
1
8
7
6
5
Л
3
2
t
3S
28
21
15
10
6
3
1
WW\732
84
56
35
20
10
4
1
210
126
70
35
15
5;
1
462
252
126
56
21
J
f
?71бШ{
324
462
210
84
28
7
1
1716\
"Щ
Щ
ц
з1\
"в"\
ll
причем:
1 1...1...1 1...1
яг2 раз тк раз
тх + щ+ ...+ тк = х—\\
nt + n2 + ...+пк =у—1*
22..Л
пк раз
(А)
Сколько же можно составить подобных комбинаций кз х — 1
цифр 1 и у—1 цифр 2? Сочетания цифр типа (А) принято

30
ДВИЖЕНИЕ ФИГУР
[гл. II
называть перестановками с повторениями. Следовательно, нашей
ближайшей задачей является определение числа всевозможных
перестановок с повторением из х—1 цифр 1 и у— 1 цифр 2. Это
число, очевидно, и будет как раз равно Fx%y. Прежде всего заметим,
что в схеме (А) всего имеется (л;—1) + (у— 1)=х+У — 2 цифр.
Составив всевозможные перемещения этих цифр, получим
(х+у — 2)1 схем, но они не все различны, так как в (А) цифра 1
повторяется х—1 раз, а цифра 2 повторяется (у—1) раз.
Между цифрами 1 можно совершить (х—1)! перестановок, и
эти перестановки не изменят (А). Поэтому число (x-f-y—2)1 схем (А)
можно сократить на (х—1)!.
Точно так же (у—1)1 перестановок между цифрами 2 не
изменят (А), и поэтому число схем можно сократить еще на (у—1)1.
В итоге получим, что число различных схем (А) равно
(х+у-2)1 1
Таким образом мы имеем, что
(х +у_ 2)1
1 х,у {х—1)\ (У — 1)!' К)
Формула (2) позволяет решить без труда более общую задачу:
сколькими способами король может перейти из клетки (я, Ь) на
(av bx) а, двигаясь все время в направлениях ] и —*. В самом
деле, мы всегда можем (а, Ь) принять за (1, 1).
Тогда клетка (#t, b±) относительно (а, Ь) будет иметь
координатами числа at—а+l и bx — 6 + L Отсюда следует, что искомое
число способов равно Fat~a+i, bt-~5+1 или, по формуле (2)
Например, если король стоит на клетке (2, 3), то на клетку (7, 8)
он может переместиться
[(7 + 8) —(2 + 3)11_ 101 _2.2 способами
(7_2)! (8 — 3)! -5Т51^252 способами>
двигаясь в направлениях f и —+
i Вообще пусть kt цифр равно 1, k% цифр равно 2 и т. д. Наконец kn
цифр равно я. Тогда аналогичным образом можно установить, что число
v (Art -I- Л2 + — + /г» V.
всех перестановок с повторениями из этих цифр равно \ t * ' : , •
2 Очевидно, что л<#1 и ?<#i, так как в противном случае король,
двигаясь в направлениях t и -* , не мог бы достичь клетки (at, b^).

§ 5]
ДВИЖЕНИЯ КОРОЛЯ
31
До сих пор мы рассматривали тот случай, когда король
перемещается поступательно в направлениях | и —>. Естественно теперь
перейти к более общему случаю, а именно пусть король
перемещается поступательно в трех направлениях: | , —> и ,/*.
Мы опять начнем свое исследование изучением движения короля
из угловой клетки (1,1) на клетку (х, у). Обозначим через Dx%y
искомое число перемещений. Для того чтобы попасть на (х, у),
король неминуемо должен пройти либо через (х-
через (я—1, у), либо через (х, у — 1). Отсюда
будем иметь такое соотношение:
А
*• у
D
x-U у-
-i+?U.,+ A
я» у-1 >
Л) у—1), либо
[Т
|У
/
1 ' "'
! /
7
5
3
t
25
13
5
1
63
25 \
А
......
причем DXiX=l, DUy=l. С помощью этой
формулы можно определить D№ для любой клетки.
Проделав все вычисления, мы получим еле- 12 3 4
дующую арифметическую шашечницу1 (фиг. 17).
Впрочем, оказывается, что и" D^ можно не- Фиг. 17.
посредственно выразить через х и у с помощью
тех же методов, которые применялись к f . Обозначим
соответственно через 1, 2 и 3 перемещения ] , —* и' у1. В своем движении
от клетки (1, 1) до (х, у) король должен пройти х—1 строк
и у—1 колонн. Приходе 1 он переходит на новую строку, но
колонна остается одна и та же. Наоборот, при ходе 2 король
переходит на новую колонну, оставаясь на одной и той же строке.
Наконец, при ходе 3 наша фигура перемещается на новую колонну и
новую строку. Поэтому ход 3 эквивалентен перемещению 12 или 21.
Представляются только следующие возможности:
1) король переходит от (1, 1) к (#, у) с помощью х— 1 ходов 1
и у — 1 ходов 2;
2) король переходит от (1, 1) к (л:, у) с помощью х — 2 ходов 1,
у — 2 ходов 2 и одного хода 3;
3) король переходит от (1, 1) к (х} у) с помощью х — 3 ходов 1,
у—3 ходов 2 и двух ходов 3;
к) король переходит от (1, 1) к (х, у) с помощью х — k ходов
l,j/ — k ходов 2 и {к—1) хода 3 и т. д.
Очевидно, что число перемещений типа 1) равно числу
перестановок с повторениями из х—1 цифр 1 и у—1 цифр 2.
т. е. равно
(х+у — 2)\
1*—1>»«-У—1)1*
1 Мы здесь ограничились шашечницей из 16 клеток.

32
ДВИЖЕНИЕ ФИГУР
[гл. II
Далее, число перемещений типа 2) равно числу перестановок
с повторением из х— 2 цифр 1,у—2 цифр 2 и одной цифры 3,
т. е. имеем согласно замечанию на стр. 30.
(г+.У-3)1
(лг —2)! Су —2)! 1!'
Вообще, число перемещений короля типа к) равно числу
перестановок с повторением из х — k цифр 1, j/ — k цифр 2 и (k—1)
цифр 3, т. е. мы получаем:
(x+y-k-\)\
(x-k)\ (.у —Л)! (Л—1)! '
Отсюда искомое число Dx определяется как сумма всех этих
выражений; иными словами, мы имеем, что:
*»у (лг—lj! 0> — l)!"1"^* — 2)! СУ —2)! I!"1"
(* + у-4)! С-У+-У — A? —1)1 ,
**"¦(* —3)! (у — 3)! 2!"1" '•• ^(лг-Л)! (.у— А)! (Л—1)! "^ ' * '
причем суммирование продолжается до тех пор, пока не станет
равным нулю х—k или у—k. 0! считается равным единице.
Зная выражение DXiy} нетрудно решить и такую задачу:
сколькими способами король может пройти из клетки (а, Ь) к (at, b±),
двигаясь в трех направлениях 1, 2 и 3. Для этого надо будет
дословно повторить решение аналогичной задачи относительно
движения короля в двух направлениях 1 и 2. Получим, что искомое
число равно
Ач-и* Ьх-Ь + \.
6. Движения ладьи
Ладья, как известно, может в один ход пройти одну, две, три
и более клеток. Условимся называть ходы на одну клетку простыми
ходами ладьи, ходы на две, на три клетки двойными, тройными
ходами ладьи и т. д.; вообще ход на р клеток мы назовем
/7-клеточным ходом.
Обозначим q ходов /7-клеточных через q .
Мы будем изучать только поступательное движение ладьи вперед.
Рассматривая движение ладьи на шахматной доске из я2 клеток,
мы ь*ожем от первой до (/га+1)-й клетки приття самыми

§ 6] ДВИЖЕНИЯ ЛАДЬИ 33
разнообразными способами. Эти способы будут отличаться числом,
порядком и составом ходов.
Например, от первой до пятой клетки мы можем притти
следующими восемью способами:
При этом выражение 2tl2 означает способ передвижения ладьи,
состоящий из двух простых ходов и произведенного вслед за ними
одного двойного хода; выражение 1311 означает способ
передвижения, состоящий из одного тройного хода и произведенного вслед
за ним простого хода и т. д.
Подсчитаем число всех способов передвижения ладьи от первой
до (яг+1)-й клетки. Этот подсчет эквивалентен нахождению числа
решений в целых неотрицательных числах неопределенного
уравнения1:
*, + **+ ...+*« = /» (3)
с т неизвестными, причем значения неизвестных, равные нулю,
принимаются в расчет2. Обозначим искомое число решений
уравнения (3) через Ат.
Легко видеть непосредственно, что
/л* •— 1 — Zi , **2 '—' '— *
В самом деле, при т = 1 имеем уравнение ^ = 1, имеющее
только одно решение, а при т = 2 получаем уравнение:
Х± + ЛГ2 = 2,
которое допускает всего два решения:
0 + 2 = 2 и 1 + 1=2.
Покажем теперь, пользуясь методом математической индукции,
что вообще
Ат = 2»-\ (4)
Для этого предположим, что для всех k<^m формула (4)
уже установлена, и покажем, что тогда формула (4) будет иметь
место и для т.
1 Неопределенным уравнением называется уравнение с числом
неизвестных, большим одного.
2 При этом решения, отличающиеся только расположением нуля,
считаются одинаковыми. Например, решения 0 + 2 и 2 + 0 уравнения х% + х2 = 2
считаются одинаковыми.

34
ДВИЖЕНИЕ ФИГУР
[гл. II
В самом деле, среди решений уравнения (3) существует Ат_х
решений с дгда = 1, Д9г_2 решений с *т = 2, Лш_3 решений с хт = 3
и т. д., АА решений с хт = т—-1 и, наконец, одно решение
с хш = т. Очевидно, что этим исчерпываются все решения нашего
уравнения, а потому имеем:
= 1+(1 + 2 + 22+...+2т-2).
В скобке мы получили геометрическую прогрессию с первым
членом, равным 1, знаменателем 2 и с последним членом, равным
2W~2. Суммируя ее, получим:
Аш = 1 + Y^T^1 + 2m~1-1 =2яг1э
что и требовалось показать.
Рассматривая, например, движение ладьи от первой до пятой
клетки, имеем, согласно формуле (4):
Л4 = 23 = 8.
И действительно, уравнение *1 + л;2 + лг8 + лг1 = 4 допускает
следующие восемь решений:
4 + 0=4; 1 + 1 + 2 =4;
1 + 3 = 4; 2+1 + 1 =4;
3 + 1=4; 1 + 2 + 1 =4;
2 + 2=4; 1 + 1 +-1 + 1=4,
причем 4 + 0 означает способ передвижения ладьи, состоящей из
одного четырехклеточного хода; 1+3 означает способ
передвижения, состоящий из первого простого хода и второго тройного
хода и т. д.
Но среди этих восьми ходов имеются передвижения,
отличающиеся только порядком ходов. Например способы передвижения
2 + 1 + 1 и 1+2 + 1 или, е другой записи, l22t и l^li
отличаются только порядком ходов. Такие способы передвижения мы
будем называть сходными. Все же остальные способы передвиже-.
ния мы назовем несходными, или различными. Если мы будем
считать только различные способы передвижения, то от первой

§ 6] ДВИЖЕНИЯ ЛАДЬИ 35
до пятой клетки мы можем притти всего пятью различными
способами:
4 + 0; 1 + 3; 2 + 2; 1 + 1+2; 1 + 1 + 1 + 1,
или в более сжатой записи:
Представителем группы сходных способов передвижения мы
будем рассматривать тот способ передвижения, в котором ходы
расположены только в возрастающем порядке. Например, из трех
сходных способов передвижения
1 + 2 + 1; 2+1 + 1; 1 + 1 + 2
мы будем способ передвижения 1 + 1 + 2 считать представителем
всей группы сходных способов передвижения.
Поставим себе задачей определение всех несходных способов
передвижения ладьи от первой до (*я+1)-й клетки.
Нетрудно видеть, что число всех таких несходных способов
передвижений равно числу положительных решений неопределенного
уравнения
1-^ + 2«^ + 3*^3+ . • ¦ + тхт=т (5)
с т неизвестными, причем хк означает здесь число & —
клеточных ходов. Например, Здг3 означает, что совершено было хв тройных
хода. Обращаясь к нашему примеру передвижения ладьи от первой
до пятой клетки, будем иметь:
1 *хх + 2-лг2 + 3 <xz + 4 -хк = 4
ч, решая это уравнение, получим все несходные способы
перемещения. Непосредственно можно усмотреть, что это будут
следующие решения:
1.0 + 2.0 + 3.0 + 4-1=4;
1.1 + 2.0 + 3.1 + 4.0=4;
1.0 + 2.2 + 3.0 + 4.0 = 4;
Ь2 + 2*1 + 3.0 + 4-0 = 4;
1.4 + 2.0 + 3-0 + 4.0 = 4,
т. е. мы получим всего пять несходных способов передвижения
14; l±la; 22; 2t la; 4lt указанных выше.

36
ДВИЖЕНИЕ ФИГУР
[ГЛ. II
Обозначим искомое число через N(m).
Существует два способа подсчета N(m). Обоснование второго
способа связано с теорией бесконечных сумм и произведений и
требует знакомства с элементами высшей математики1, а первый
вполне элементарен, но связан с некоторыми предварительными
рассуждениями. Здесь мы ограничимся только первым способом.
Рассмотрим следующее уравнение с k неизвестными:
Oi>0> У*>У±, Л>Л» ¦••> У*>.Ум)'>
обозначим число его решений через Amtk и положим
Легко убедиться, что #t>0, лсА_1 >0, *м>0,..., Art>0. Из
уравнений (7) можно обратно j^,... 7ук выразить через xv х2,..., хк,
а именно так:
-У 2 ==A:* + A:fr-l5
Л = ** + XA-1 + Xk-V>
Уъ-1=Хъ + ^A-i + *t_2 + ... + лг3 + л;2;
После подстановки найденйых значений j;^^,..-,.уЛ в
уравнение (6), раскрытия скобок и приведения подобных членов получим
следующее окончательное уравнение:
1 -хх + 2«лг2+ ... +&«A:fc = /7z
(^>0, дг2>0, ..., лгм>0, л:Л>0),
причем число решений уравнения (8) мы обозначим через Bhm.
Итак, из всякого решения уравнения (6) тотчас следует решение
уравнения (8). Следовательно, мы можем утверждать, что число
1 Читатель, знакомый с элементами анализа, в § 18 добавления найдет
изложение этого способа,
(6)
(8)

§ 6] ДВИЖЕНИЯ ЛАДЬИ 37
решений уравнения (б) не должно превосходить числа решений
уравнения (8), т. е.
Обратно, из уравнения (8) с помощью равенств (7) получается
уравнение (6). Таким образом мы можем точно так же утверждать,
что
Сравнивая эти неравенства, приходим к выводу, что
т. е. мы доказали следующую теорему.
Теорема I. Число решений неопределенного уравнения
Л+Л+•••+)'» = «
(У1>°, У*>Уи •••> Уъ-х>Ум Л>Л-г)
равно числу решений неопределенного уравнения
l-ATj -\-2>х2+ ... + k*xk = m;
(xt>0, х2>0, ..., лг^Х), xft>0).
Заменим далее хк через хк + 1. Получим уравнение:
1 •д:1 + 2-л:2+ ... + k-xk = m-
(хх>0, *2>0, .
эквивалентное уравнению (8). Следовательно:
.. +k'Xk = m — k \
(9)
D Q
где Cftm,— число решений уравнения (9); согласно теореме I:
А, го— С]с,т'
В частности, заменив т на m + k, будем иметь:
Но тогда уравнения (6) и (9) перепишутся следующим образом:
Ot>o, л>Ур л>л> --мЛ>^м);
1-д:1 + 2-д:.2+ ... + к-хк = т
(хг>0, лг.2>0, ..., лг*>0).

38 ДВИЖЕНИЕ ФИГУР [ГЛ. II
Если заменим затем в первом уравнении все yi через zt-\-lf то
получим после сокращений:
*i+**+--• + zh = m,
т, е. мы пришли к такой важной для нас теореме:
Теорема П. Число решений АКчт+к уравнения
zl+zi+...+zk = m \
*-t) /
(z±>0, z%>zt9 •. -, zk'^zi
равно числу решений Cbm+k уравнения:
l-xt + 2»x%+ ... +k'Xk — m
(xt>0, *2>0, ..., xk>0).
(10)
(")
Последнее уравнение при k = m совпадает с (5), т. е. имеем:
?«,!« = #(«)•
Теперь можно произвести подсчет Cm$2m и тем самым
определить N(m). Для этой цели заметим, что все решения уравнения (10)
исчерпываются решениями следующих двух уравнений:
*! + **+••• + ** = /»; z2 + *8+ ... +zh = m\
Но число решений первого уравнения равно Akjtn> так как оно
типа (6), а число решений второго уравнения равно А^ т+м, так
как оно типа (10), но с А—1 неизвестными.
Следовательно:
Теперь, согласно нашим теоремам, имеем:
A:» m-bft
^*,*n
— Г
откуда
С помощью этой формулы уже легко подсчитать N (т) для данного т»

§ 6) ДВИЖЕНИЯ ЛАДЬИ 39
В качестве иллюстрации применим формулу (12) к подсчету N(4),
т. е. к подсчету всех несходных способов передвижения ладьи от
первой до пятой клетки. Мы должны для этого определить
С4|8 = Л/(4). По формуле (12) имеем:
^з,7 == ^з»4 + Ца?б» Ч*»з == ^2»i + ^i»a»
^2,6:=^'2.4+ W»3» 4ja==:4si2 + ^ЬЗ*
Но Cft,m при &>/тг равно нулю, так как т — k в этом случае
отрицательно, и потому уравнение
1»л:1 + 2«*а+ ... +&.*A. = /7z —A
нельзя решить в целых неотрицательных числах. Затем, Chyh> CUm
равны единице, так как уравнение
Ьлг1 + 2-л:2+ ... + k-xk — k — k = Q
(*t>0, *2>0, ¦ ,., л;А>0)
и уравнение
xi = /ю — 1
имеют лишь по одному решению в неотрицательных числах, а именно,
первое уравнение допускает только решение xx=x% = .9. =л;А = 0,
а второе xt=fn — 1. Следовательно:
Cbm = ° ПРИ К>Щ
откуда в данном случае имеем:
и потому;
Q,4 = l + 1=2; С2,6 = 2 + 1=3;
См = 0 + 1 = 1; С3,7 = 1 + 3 = 4;
См = 0 + 1 = 1; С4;8 = 1 + 4=5,
т. е. N(4)=5»,
1 Какой же конкретный смысл имеют числа Сь т+1с7 Оли означают число
несходных способов передвижения ладьи поступательно от первой до (т + 1)-й
клетки не более чем в k ходов. Например См определяет четыре способа
перемещения от первой до пятой клетки в один, два или три хода.

40
ДВИЖЕНИЕ ФИГУР
[ГЛ. II
Второй способ подсчета основан на гораздо более удобной
формуле (см. добавление, стр. 80), но, к сожалению, вывод ее
неэлементарен. Все попытки выразить N(m) и Ск,т через k и т до сих
пор не увенчались успехом, за исключением весьма частных
случаев; например, это можно сделать для C2lW(w>2). А именно,
легко показать, что при четном т
а при нечетном т
г — т~1
7. Движения коня
Конь, несомненно, является наиболее интересной и сложной
шахматной фигурой, причем с его движением связан целый ряд задач,
до сих пор не решенных еще в общем виде (например, знаменитая
задача Эйлера, о которой речь будет ниже, в гл. III).
Как и в предыдущих случаях, исследование движения коня
сводится к анализу неопределенных уравнений со многими неизвестными.
Если конь стоит на клетке (/га, га), то в один ход он может
переместиться следующими восемью способами;
(/и_1эЛ-2); (гаг-1,га + 2); (/га+1,га-2); (/га+1,га + 2);
(/га — 2, га — 1); (/га —2, л+1); (/га+ 2, га — 1); (/га + 2, га + 1).
Легко видеть, что эти восемь клеток можно получить, решая
в целых числах неопределенное уравнение:
(х — mf + (y — га)2=5 (13)
относительно неизвестных х и у, так как
х — /ra = dzl; у — п = ±2
и
х — т = ±2\ у — /z = dt 1
удовлетворяют уравнению (13).
Известный русский шахматист XIX века Яниш, написавший
большое сочинение, посвященное приложению математического
анализа к шахматам*, базируясь на уравнении (13), свел изучение
1 С. F. Jaenisch, Traite des applications de P analyse mathematique au
jeu des echecs. Saint-Petersbourg 1862.

§7]
ДВИЖЕНИЯ КОНЯ
41
движения коня к исследованию системы четырех уравнений с восемью
неизвестными:
О — хх) + 2(х% — хг) = а\
2Су—л)+ Су»—л) =*;
х + xt=y +ух;
** + *з=Л+Л>
где х, х{, х^, xvy,yvy.j. и _у3 положительны или равны нулю,
а конь перемещается из клетки (т, п) на клетку (т + а, п + Ь).
При этом сумма х + х±+х^ + х3 оказывается равной числу
прыжков фигуры.
Эта система допускает бесчисленное множество решений, что
вполне понятно, так как конь, вообще говоря, может перемещаться
бесчисленным числом способов с клетки (т, п) на клетку (т + а,п + Ь).
Другое дело, если мы наложим некоторые ограничения, например
потребуем, чтобы движение было поступательным или состояло из
определенного числа прыжков.
Начнем с простейшего случая, а именно с поступательного
перемещения. Мы назовем прыжок коня из клетки (/я, п) на клетку (х9у)
поступательным, если разности х — т, у — п положительны; но,
согласно уравнению (13), это может быть лишь в том случае,
когда х — т=2,у — п = 1 или х—/га = 1, д/ — п = 2. Пусть конь
начинает свое движение с клетки (т, п) и заканчивает его на клетке
(т + а, п + ?), передвигаясь все время поступательно. Движение
фигуры можно представить следующей схемой:
(*о> Л), (xv у,), (*2, j/,),..., (х„ yt), (xi+v ум)9..., (хк, ук).
Здесь k обозначает число прыжков. При этом
х* = Щ У*=п\ xh = m + a\ ук = п + Ь
и
*м—**=2; л+1—л=1»
или
*i+i--*<=i; л+i—л=2-
Составим суммы:
(xi—x0) + (xr-xl)+... +(xk—xk_l)=xh — x0=a, (14)
(Ух-Уо) + (Уъ-Уд + • • - + (V, -ум)=Л -ye =ft (15)
и объединим отдельно все скобки, равные 2, и скобки, равные 1.

42 ДВИЖЕНИЕ ФИГУР [ГЛ. JI
Пусть в первой сумме число двоек равно s, а число единиц
равно /. Тогда:
2s+t=a.
Легко видеть, что во второй сумме будет 5 единиц и / двоек,
так как если xi+i—xi = 2y то уи1— Уг~1, а когда xi+i — #|=1,
то yiJrX—yi = 2. Поэтому получаем для второй суммы:
2t + s = b.
Очевидно, что число k слагаемых первой и второй сумм
равно s-\-t. Таким образом мы имеем следующую систему двух
уравнений с двумя неизвестными s и t:
2s + t=a;
s + 2t = b;
откуда, имея в виду, что
после некоторых преобразований получим:
s = a — ky
t=b — k.
Мы пришли к следующему предложению:
Если а-\-Ь делится на 3 и разности а — /?, b — k
положительны или равны нулю, то конь с клетки (т,п) может притти
с помощью а~Х прыжков на клетку (т + а, п + Ь\ двигаясь по-
о
ступателъно* Если же одно из этих условий не выполняется,
то клетка (т + а, п + b) с помощью поступательных прыжков
для коня недостижима.
Например, с клетки (1, 1) на клетку (7, 4) конь может притти,
совершив-^— = 3 поступательных прыжка, так как 6 + 3 делится
на 3 и б —3>0, 3 — 3 = 0.
Остается подсчитать число всевозможных способов
поступательного перемещения фигуры. Для этого заметим, что а можно
представить Cfl+f = \.} способами в виде суммы s двоек и t
единиц. Отсюда сразу вытекает, что существует всего Си способов

§7]
ДВИЖЕНИЯ КОНЯ
43
поступательного перемещения из клетки {туп) на клетку (т + а,
n + b). Для приведенного выше примера имеем всего С| = 1
способ передвижения *.
Мы только что рассмотрели поступательное перемещение коня,
но можно частично решить более общую задачу. Назовем прыжок
из (т, п) на (х,у) поступательным в горизонтальном направлении,
если х — т положительно; что касается разности у—я, то она
может иметь любой знак.
Мы будем говорить, что перемещение коня совершается
поступательно в горизонтальном направлении, если оно состоит только
из поступательных горизонтальных прыжков.
Дезире Андре как раз для этого случая удалось частично
решить задачу, причем любопытно отметить, что его решение
совершенно не связано с анализом системы
уравнений Яниша. Он указал
способ подсчета числа поступательных
горизонтальных перемещений коня на
прямоугольной шашечнице, имеющей
в ширину четыре клетки, а в длину п
клеток. В частности, при п =8 мы
получим половину обыкновенной
шахматной доски. Фиг. 18.
Рассмотрим п-ю колонну этой
шашечницы и обозначим через Sn, #n, QnH Pn соответственно число
способов поступательных горизонтальных перемещений коня из данной
клетки на первую, вторую, третью и четвертую клетки я-й колонны
(фиг. 18). Тогда, по Дезире Андре, мы будем иметь:
Ограничимся выводом только первого соотношения.
Легко видеть, что на клетку Рп конь может пройти только из
клеток а и Ъ. Но число способов передвижения фигуры на а и Ъ
соответственно равно Qw_2 и /?л_2, откуда
т. е. мы пришли к первому соотношению. Остальные равенства (16)
устанавливаются точно таким же образом.
* Легко видеть на основании известных свойств числа С™, что Сгн = Csk.
•а
•Ь
Рп
Qn
/?„
sn

44
ДВИЖЕНИЕ ФИГУР
[ГЛ. II
Покажем теперь, как можно пользоваться системой (16) в
конкретных случаях. Подсчитаем, например, число способов
поступательного горизонтального передвижения коня с клетки (1,1) на
клетку (5,4), т. е., иными словами, определим Р5. Легко видеть,
что, переходя из (1,1) во вторую колонну, конь может
переместиться только на клетку (2,3) (фиг. 19).
Поэтому:
S± = l*; Rt=0; Q1==0; Pl==0;
S2 = 0; Яа = 0; Q, = l; Pe = 0,
и мы можем остальные S, /?, Р, Q с помощью формул (16)
вычислить следующим образом:
/?, = PSi + Q1 + 51 = 0 + 0+l = l;
Qt = Pt +^ + 5^ = 0 + 0 +0=0;
/V^Qi + Я, =0 + 0=0;
затем имеем:
S4=Q3 + #2 = 0 + 0 = 0;
P4 = P3 + Q2+S2 = 0+1 + 0=1;
Qi=P2 + /?2 + 53 = 0 + 0+1 = 1;
P4=Q2 + /?3 = 1 + 1=2,
откуда:
Ps = Q3 + /?4 = o + i=i,
т. е. существует лишь один способ передвижения с клетки (1,1)
на клетку (5,4). Он отмечен на чертеже крестиками (фиг. 19).
Обратимся в заключение к рассмотрению того случая, когда
перемещение коня (быть может, и не поступательное) с клетки (#z, n)
на клетку (т + а>п-\-Ь) состоит из k прыжков. Эта задача
гораздо труднее двух предыдущих. Математик Миндинг вместо
исследования системы неопределенных уравнений предложил другой способ.
Он предложил обозначать клетку (т, п) через хтуп- Тогда все
J Si принимается равным единице. Если бы конь вместо (1,1) стоял, напри
мер, на (1,3), то мы положили бы Q1 = l.

§ 7]
ДВИЖЕНИЯ КОНЯ
45
возможные доступные клетки определятся с помощью членов
выражения Uxmyn, где
и~(*+т) (?+$)+(*+v)(y+j)> (17)
причем члены Uxmyny обладающие отрицательными показателями
и показателями, равными нулю, не принимаются в расчет.
С помощью формулы (17) можно решить,
например, такую задачу: определить число
способов перемещения коня с клетки (1,1) 4
на клетку (3, 4), если известно, что движение з
состоит из 11 прыжков и происходит на -
прямоугольной шашечнице, имеющей в
ширину четыре клетки, а в длину три клетки. 1
Напишем прежде всего U в раскрытом
виде:
Фиг. 19.
?/=*y + J^ + ? +J,+ 4 + ^ + JL+Jl
-* ' ^ x ' xy2 у2 у ху 1 х*
и определим и± = [иху], т. е. выражение Uxy без отрицательных
и исчезающих показателей. Имеем:
Ut = x*y*+xy.
Далее имеем:
[Ux У]=хУ + хУ + ху* + ху + х'у + хУ\
[Uxy] = хУ + хУ + хУ + х*у + ху + ху9.
Но все ходы, выходящие за пределы шашечницы, и ходы на
клетки (1,1) и (3,4)* должны быть отброшены. Поэтому остаются
лишь напечатанные жирно члены, и мы получим:
U% =х3у + xys + ху.
Аналогичным образом находим далее:
?/8 =х*у + 2ху* + 2хУ + хУ;
Ug = Sx9y + bxf + ЪхУ + 4хУ;
Un = 6х*у + 10ху* + 7хУ + ЪхУ + Ъху1\
UQ = 13х*у + ЗхУ + 1дху* + 1 ОгУ + ПхУ.
1 Ход на (3,4), если он встретится, надо отбросить, потому что мы хотим
клетку (3,4) достичь в одиннадцать, а не в меньшее число прыжков.
1
Г 1
У
Л
/
^
н»
/'
•-*
1<ч
' 1

46
ДВИЖЕНИЕ ФИГУР
[гл. П
Можно было бы далее составить ?/7, ?/8, ?/9, ?/10, UUi но гораздо
проще поступить следующим образом. Будем исходить из (3,4)
в обратном направлении. Составим для этой клетки [Шг*.у4];
получим:
[UxY] = хУ + хУ + хУ + хУ + хУ + хУ + ху* + ху\
Отбрасывая все члены, соответствующие клеткам за пределами
шашечницы, мы придем к выражению:
Vtz=xy + хуг,
Нетрудно заметить, что если в Ux заменить хт через х*~т и уп
через У*~Л, то как раз получится Vt. Поэтому, произведя
подобную замену в ?/2, получим К2 и т. д.; наконец из ?73 получится
такое К5:
V. = бл:У + ЮхУ + 7ху* + ЗхУ + Зх*у,
или, несколько переставив члены:
У8 = Зх3у + дхУ + 7хуг + ЮхУ + бху.
Сравнивая U6 и V3, мы видим, что существует 13 способов
передвижения в шесть ходов с клетки (1, 1) на клетку (3, 1) и три
способа перемещения в пять ходов с клетки (3,1) на клетку (3, 4).
Таким образом конь может в 11 ходов притти 13-3=39
способами на клетку (3, 4), проходя на шестом ходу клетку (3, 1).
Точно так. же выводим, что существует 3-3 = 9 способов
передвижения в 11 ходов на клетку (3,4), при которых проходится
на шестом ходу клетка (2, 2) и т. д. В итоге получаем
13.3 + 3.3 + 13.74-19-10 + 17.6 = 431 способ
перемещения в 11 ходов на (3,4).
8. Сравнительная сила шахматных фигур
Известно, что при игре в шахматы две ладьи, вообще говоря,
сильнее ферзя, а два слона — сильнее ладьи. Поэтому возникает
естественный вопрос, что называть силой фигуры и как эту силу
можно определить. Так как шахматные фигуры отличаются одна
от другой характером движения, то можно попытаться определить
силу фигуры, основываясь на особенностях ее передвижения.

§ 8] СРАВНИТЕЛЬНАЯ СИЛА ШАХМАТНЫХ ФИГУР 47
Рассмотрим, например, движение короля. Король, находясь на
одной из угловых клеток, может двигаться в трех направлениях.
Далее, если король стоит на краевой, не угловой клетке шашечницы,
то он может перемещаться уже в пяти направлениях. Наконец, со
всех остальных клеток король в состоянии перемещаться в восьми
направлениях. Но обыкновенная шашечница состоит из четырех
угловых и 24 краевых клеток. Поэтому для нее мы можем
составить такую таблицу:
для 4 клеток король может перемещаться в трех направлениях;
для 24 клеток король может перемещаться в пяти направлениях;
для 36 клеток король может перемещаться в восьми направлениях.
Всего получается 4*3 + 24«5 + 36«8=420 перемещений короля
на всей шашечнице. Если мы разделим 420 на 64, то получим
среднее число возможных ходов короля, приходящихся на клетку,
т. е. мы получим — = 6,5625, —около шести ходов.
Вполне естественно считать, что фигуры тем сильнее, чем большее
число ходов должно приходиться в среднем на одну клетку. Таким
образом мы можем силой фигуры назвать среднее число ходов,
приходящихся на клетку той части шашечницы, которая доступна
фигуре. Из этого определения следует, что сила фигуры зависит
от числа клеток шахматной доски. Каким же образом определяется
эта сила для шашечницы из п* клеток? Чтобы ответить на этот
вопрос, разберем прежде всего движение коня.
Прыжки коня можно разбить на две категории.
Мы отнесем прыжок к первой категории, если при этом
проходится одна колонна и две строки, и отнесем прыжок ко второй
категории, если проходятся две колонны и одна строка. Из клеток
любой колонны, не находящейся на краю шашечницы, конь может
совершить п — 2 прыжка сверху вниз первой категории по одну
сторону и столько же прыжков по другую сторону колонны. В самом
деле, с каждой клетки этой колонны, за исключением лишь двух
нижних клеток, можно совершить один прыжок рассматриваемого рода
по одну сторону и один прыжок по другую сторону; что касается
двух нижних клеток, то для них не существует ходов сверху вниз.
Всего, таким образом, мы имеем 2 (п — 2) прыжков первой
категории сверху вниз. Очевидно, что число прыжков первой категории
снизу вверх также равно 2 (/г —2). Следовательно, из колонны, не
находящейся на краю доски, можно совершить в общей сложности
4(л —2)
прыжка первой категории. Обращаясь к крайним колоннам, видим,
что для них существуют прыжки только по одну сторону. Поэтому

48 ДВИЖЕНИЕ ФИГУР [ГЛ. II
из краевой колонны можно совершить всего 2(п— 2) прыжка
первой категории, а из двух крайних колонн 4 (п — 2) прыжка. Таким
образом на всей доске существ} ег 4 (/г — 2) (л — 2)+ 4 (/г — 2) =
= 4 (п — 2) (п — 1) ходов первой категории.
Точно таким же образом можно установить, что число прыжков
второй категории равно
4(«-2)(«-1),
откуда получается число
4 (л — 2)(я—1) + 4(л —2)(л—1) = 8(я —2)(л—1)
всех прыжков коня. Теперь можно уже без труда вывести силу
коня. А именно имеем:
8(я —2)(я--1)
В частности, при п = 8 (т. е. для обычной доски) сила коня
8-6-7 42 - ос ^
равна —^— = — =5,25, т. е. конь слабее короля.
Чтобы определить силу других фигур, рассмотрим некоторую
«общую» фигуру, которая способна перемещаться из клетки (/л, п)
только на (w±r, ndzs) или (mdzs, n±r).
В частности, при г=1, 5 = 2 мы получаем ход коня. Число ходов
этой общей фигуры можно определить с помощью тех же
рассуждений, что и для коня. Мы здесь ограничимся лишь готовым
результатом. Оказывается, что наша фигура по всей доске может
совершить
2 [(2/г — г— sf — (r— sf\ (18)
ходов, если гф^ и г и s не равны нулю.
Легко видеть, что при г ф 5 и r,s и 0 рассматриваемая фигура
способна совершить восемь различных ходов из клетки (т, /г), так
как мы имеем в данном случае восемь различных клеток, на
которые она может попасть:
(т + г, п + s); (//г — г,/г + s); (m-\-r,n — s)\ (w—-г,/г —s);
(m + s,n + r); (m — s,n + r)\ (m+s, n — r)\ (m — s,n — r).
Если же г или 5 = 0 или г =5, то число различных клеток
сокращается до четырех. Таким образом здесь получается всего

§ 8] СРАВНИТЕЛЬНАЯ СИЛА ШАХМАТНЫХ ФИГУР 49
четыре различных хода фигуры, и потому при г или 5 = 0, или
г=s для определения искомого числа ходов следует брать
половину выражения (18). Теперь мы можем вернуться к основной
задаче.
Для определения силы короля рассмотрим следующие две фигуры:
одну г = 5=1, а другую г=1, 5 = 0. Число ходов первой фигуры
ргвн.) половине выражения:
2 [(2/г — 1 — If — (1 — If] = 2-4(п — I)2,
т. е. равно 4 (я—1)*, так как здесь г=5=1.
Для второй фигуры следует также взять половину выражения:
2 [(2п — 1 —Of — (1 —О)2] = 2 [(2/г— I)2 — 1],
так как для нее 5 = 0. Поэтому число ходов этой фигуры равно:
(2п — If— 1.
Нетрз'дно видеть, что король как раз и является сочетанием
рассматриваемых фигур. Следовательно, имеем:
4(n—lf + (2n—lf—l=4(n—l)(2n—l)
ходов короля; откуда без труда определяем его силу:
4 (л — 1)(2п — 1)
&
Для шашечницы из 64 клеток мы снова получаем 6,5625.
Обращаясь к оценке силы ладьи, заметим, что здесь искомое
число ходов гораздо проще найти непосредственно. А именно, из
любой клетки ладья способна совершить 2/х — 2 различных ходов:
п—1 ходов горизонтальных и столько же вертикальных. Поэтому
для всей шашечницы получаем:
п*(2п — 2) = 2п*(п—1) (19)
ходов ладьи; откуда сила нашей фигуры равна:
2п*гп-\)
- = 2(д—1).
В частности, при п = 8 получаем число 14.
Гораздо сложнее определяется сила слона и ферзя.

50 ДВИЖЕНИЕ ФИГУР [ГЛ. II
Два слона * вместе эквивалентны совокупности фи^ур, для
которых r=s и г пробегает значения от 1 до п—1. Заметив это, мы
можем, пользуясь формулой (18), определить число ходов двух
слонов на квадратной шашечнице из /г2 клеток. Так как r=s, то,
согласно приведенному выше замечанию, следует взять половину (18).
Имеем поэтому
(2/г — 2г?
ходов фигуры с r=s\ откуда, полагая последовательно г= 1,2,, .. 5
п — 1, видим, что число ходов наших слонов равно сумме:
(2/г — 2)2 + (2/г — 4)2 + (2/2 — 6)*+ ... + 22 =
= 4[(п-1)* + (п-2)* + (п — 3)*+...+1«],
или, переписывая слагаемые в квадратной скобке в обратном
порядке, получим:
4[1* + 22 + За+...+(/х-1)2].
Нам необходимо для окончательного решения задачи выразить
сумму квадратов
12_1_22 + 32+...+(/г-1)*
через п. Для этой цели составим следующий ряд равенств:
1^= 1;
23 = (i + i)8=i3 + 3.i2 + 3.i+ 1;
33 = (2+1)3 = 23 + 3«22 + 3.2+ 1;
43 = (3+1)3 = 33 + 3-32 + 3-3 + 1;
(я — 1)3 = [(/г — 2)+1]3 = (/г —2)3 + ЗГ/г—2)2 + 3(/г —2)+1;
л»=[Сл—1)+1]8 = (я —1)8 + 3(л—1)а + 3(л —l)+lf
и сложим их. Тогда получится:
13 + 23 + 38+...+/г3=[13 + 23 + 33+... +(п—1)3] +
+ 3[12 + 22+...+(л-1)2] + 3[1 +2 +3+...+(/*-!)] +
+ (1 + 1 + ... + 1),
* Один слон черный, а другой белый.

§ 8] СРАВНИТЕЛЬНАЯ СИЛА ШАХМАТНЫХ ФИГУР 51
причем в последней скобке стоит п единиц; после некоторых
сокращений будем иметь:
лЗ = 3[12 + 22 + 32+...+(я-1)2] +
+ 3[1 + 2 + 3+...+(*-1)] + л.
Но 1 + 2 + 3+... + (я — 1), как сумма членов арифметической
п (п — 1)
лрогрессии, равна —^—-; откуда:
^3[1Ч2ЧЗЧ...+(^1)2] + 3^^ + л,
или
|l2 + 22+32+...+(/Z— 1)*] =
_ л» л (л— 1) ? _я(д — 1)(2/1—1)
т. е. мы выразили нашу сумму квадратов через п.
Теперь для двух разноцветных слонов мы сразу получаем:
4я(л--1)(2л —1) _ 2/х (/г — 1) (2/г — 1)
6 *~~ 3
(20)
ходов. В случае четного п число ходов черного слона равно числу
ходов белого слона, так как в этом случае белых и черных клеток
одинаковое количество. Поэтому для четного п сила слона не
зависит от цвета и равна:
/г(/г — 1) (2/г — 1) __2(я —1)(2я—1)
Q7Z2 ~ ЗЯ '
ибо только половина доски доступна слону. При я = 8
получим 8,75.
Когда я нечетно, сила слона уже зависит от цвета, но мы этот
случай разбирать не будем, так как нас интересует главным образом
обыкновенная шашечница из 64 клеток.
Остается оценить силу ферзя, но теперь эта задача решается
чрезвычайно просто. В самом деле, ферзь является, собственно
говоря, сочетанием двух слонов и ладьи. Следовательно, число его
ходов равно сумме выражений (19) и (20), т. е.
2п*(п 1) | 2"(я—*)(2* —*) =2/г(/г —1)(5л2 —1),
о о
откуда сила ферзя будет равна:
2я(я—1)(5я-~1) _2(я~1)(5я — 1)
3/1* ~~ 3/г
(21)

52
ДВИЖЕНИЕ ФИГУР
[ГЛ. II
Применяя эту формулу к обычной шашечнице, получим число
~ = 22,75.
4
Итак, можно составить следующую табличку для доски из 64
клеток:
Наименование Сила
фигур фигур
конь 5,25
король 6,5625
слон 8,75
ладья ¦ 14
ферзь 22,75
Однако не следует забывать, что действительная сила фигуры
зависит еще от распределения других фигур на доске и не является
неизменной. Поэтому число ходов фигуры, приходящихся в среднем
на клетку шашечницы, правильнее было бы назвать потенциальной
силой фигуры.
В заключение покажем, что, зная силу ферзя, можно решить
частично задачу Ландау, а именно в случае k = 2. Мы здесь имеем
в виду следующую задачу:
Сколькими способами можно расставить на шашечнице из /г2
клеток двух ферзей так, чтобы ни один не бил другого?
Прежде всего ясно, что если из числа всех расстановок наших
фигур вычесть число таких расстановок, в которых один ферзь
угрожает другому, то мы как раз получим искомое число. Чему же
равно число всех расстановок?
Очевидно, что два ферзя занимают только две клетки доски
и эти клетки можно выбрать С\г способами из всего числа п%
клеток шашечницы. Таким образом мы видим, что два ферзя можно
расставить всего С\г способами. Но среди этих С^а распределений
фигур находятся такие размещения, у которых одна фигура бьет
другую. Подсчитаем число таких размещений. Пусть первый ферзь
стоит на (лг, у). Если второго ферзя поставить га одну из клеток
линии обстрела первого ферзя, то фигуры будут угрожать друг
другу. Легко видеть, что второго ферзя можно разместить
рассматриваемым образом столькими способами, сколько разлучных
поступательных ходов может совершить первый ферзь из клетки (х,у).
Попятные ходы надо откинуть, так как они войдут при счете
поступательных ходов из клеток, находящихся до (х,у). Поэтому,
в конечном счете, на шахматной доске из пА клеток два ферзя
можно расставить так, чтобы они били друг друга р способами
где р — число всех поступательных ходов ферзя по всей доске
2?
Но сила / ферзя равна -~ , так как число поступательных ходов

§ 8} СРАВНИТЕЛЬНАЯ СИЛА ШАХМАТНЫХ ФИГУР 53
равно числу попятных ходов. Отсюда получаем, что
пЧ
и потому искомое число М будет равно:
или, подставляя значения С\% и / из (21), после некоторых
преобразований получим окончательно:
л*п(п-1)(п-2)(Зп-1)
м- б
В частности, при л = 8 эта формула дает:
м== 8-7-6-23 =1288>
б
Решая далее задачу для трех ферзей, Ландау получил для четного п
выражение:
~ п(п — 2)* (2л3 — 12л* + 23/г — 10),
а для нечетного п:
-^(л — 1)0 — 3)(2/г4 — 12л3 + 25л2 — 14л-г х).
Эту же задачу для четырех ферзей решить до сих пор не удалось

ГЛАВА ТРЕТЬЯ
ЗАДАЧА ЭЙЛЕРА О ХОДЕ КОНЯ
9. Предварительные замечания
Среди комбинаторных задач на шахматной доске, несомненно,
самой трудной * и интересной является знаменитая задача Эйлера,
относящаяся к движению коня на шашечнице.
Она состоит в следующем: требуется обойти конем все клетки
шашечницы, проходя каждую клетку не более одного раза. При
этом шашечница может быть как прямоугольной, так и квадратной,
но мы будем рассматривать главным образом обыкновенную доску
из 64 клеток.
Сам Эйлер довольно много занимался этой задачей и указал
некоторые частные методы решения, но до сих пор не удалось
найти общего метода и определить число всех решений задачи.
Даже для обыкновенной шахматной доски известно лишь, что
число решений во всяком случае не меньше чем 31054144 и не
больше CiqS (числа, состоящего из ста цифр).
Любопытно отметить, что еще в самом начале XVI века известна
была следующая задача, принадлежащая Гуарини:
На четырех угловых клетках шашечницы из девяти клеток стоят
два белых и два черных коня (фиг. 20); белые кони должны
очутиться на клетках черных, а черные — на местах белых коней.
Решение ее довольно просто. Очевидно, что возможно только
такие два случая:
a) одноцветные кони находятся в одной колонне или горизонтали;
b) одноцветные кони стоят на противоположных угловых клетках.
Таким образом все сводится к разбору случаев а) и Ь).
Разберем прежде всего случай а). Пусть для определенности
белые кони стоят на клетках 1 и 3, а черные — на клетках 7 и 9
(фиг. 19). Тогда делаем следующие ходы конями:
1—8, 3—4, 9—2, 7—6, 4—9, 6—1, 2—7, 8—3.
Теперь белые кони заняли положение 3 и 9, а черные 1 и 7,
т. е. получился такой эффект, как будто бы мы повернули
шашечницу на 90° по часовой стрелке. Нам нужно добиться того,
1 Она считается даже более трудной, чем задача о восьми ферзях.

§10] ДВИЖЕНИЕ КОНЯ НА ДОСКЕ ИЗ 64 КЛЕТОК 55
чтобы белые кони очутились на клетках 7 и 9, а черные — на
клетках 1 и 3, но если мы повернем доску на 180° по часовой
стрелке, то наши фигуры как раз расположатся требуемым
образом. Шашечница была как бы повернута нами на 90°; поэтому
остается ее еще раз повернуть на 90°, т. е.
употребить ту же серию ходов, какую мы
только что проделали, а именно:
1—8, 3—4, 9—2, 7—6, 4—9,
6—1, 2—7, 8—3. (А)
Теперь обращаемся к случаю б). Пусть,
например, белые кони находятся на 1 и 9,
а черные — на 3 и 7. Поворачивая
шахматную доску на 90° (по часовой или против Фиг. 20.
часовой стрелки — безразлично), мы получим
искомое расположение фигур. Поэтому вместо такого
поворота достаточно провести один раз систему ходов (А), и задача
будет решена.
Возвращаемся к нашей основной теме. Среди решений эйлеров-
ской задачи имеется целый ряд решений, замечательных т м, что
конь, пройдя все клетки шашечницы, возвращается к исходной
клетке. Такое движение коня мы будем называть замкнутым. Но
возможны и такие решения, когда конь, пройдя все клетки, не
возвращается на свое старое место, т. е. имеем незамкнутое
перемещение коня. Мы ниже дадим примеры как замкнутых, так и
незамкнутых перемещений.
!()• Движение коня на доске из 64 клеток
Пусть конь, двигаясь на обыкновенной шашечнице с поля
(mv nx)y проходит последовательно 16 клеток:
(/я„ пх)} (т„ ла), ..., (тш /zls) (1)
без повторений. Такую совокупность полей мы будем называть
дорожкой. Покажем, что если дорожка (1) удовлетворяет условиям:
при т% = mk, \ e при т~9 — тк, 1 при т? = 9 — тю \
к, кроме того, конь в состоянии прыгнуть с клетки (*га1в, п16) на
клетку (9 — mv 9 — /г,), то можно с помощью дорожки (1)
получить решение задачи Эйлера для нашей шахматной доски.
\
4
7
2
5
! 8
1
3
6
! э

56 ЗАДАЧА ЭЙЛЕРА О ХОДЕ КОНЯ [ГЛ. III
Легко видеть, что
(9 — mv пх\ (9 — *и2, яД ,.., (9 — rnHi л1в), (3)
(Я11Э 9 — лД (/га2, 9 — /г2), ..., (да1в, 9 — /?1б), (4)
(9-/^,9-/0, (9 —/?г2, 9 — л2), ..., (9 — mw 9 — я1с) (5)
являются также дорожками, удовлетворяющими тем же условиям,
что и (1). Дорожки (1), (3), (4), (5) вместе взятые исчерпывают
все 64 клетки шашечницы, и нашей ближайшей целью является
решение следующей задачи:
Объединить дорожки (1), (3), (4) и (5) в одну дорожку из
64 клеток.
Мы для наглядности обратимся к конкретному примеру и
рассмотрим следующую дорожку, удовлетворяющую требованиям (2):
(5, 5), (4, 3), (2, 4), (1, 2), (3, 1), (2, 3), (1, 1), (3, 2),
(1, 3), (2, 1), (4, 2), (3, 4), (1, 5), (2, 7), (4, 8), (3, 6).
Французский математик XVIII века Вандермонде, известный
своими исследованиями по высшей алгебре, решая задачу Эйлера
именно в том направлении, в каком мы ее сейчас хотим решить,,
как раз и нашел эту совокупность клеток, причем вместо (л:, у)
он пользовался более компактным обозначением. А именно: он
предложил писать абсциссу сверху, а ординату снизу, т. е. х
вместо (х, у). В этих обозначениях наш пример тогда запишется так:
5421321312431243
5342131231245786
и из (а) по правилам (3), (4) и (5) можно получить еще три
новых дорожки:
4
5
5
4
4
4
5
3
4
6
5
6
7
4
2
5
7
5
8
2
1
7
8
7
6
1
3
8
6
8
7
3
2
6
7
6
8
1
1
8
8
8
6
2
3
7
6
7
8
3
1
6
8
6
7
1
2
8
7
8
5
2
4
7
5
7
6
4
3
5
6
5
8
5
1
4
8
4
7
7
2
2
7
2
5
8
4
1
5
1
б
6;
3
3;
6
3.
(Ь)
(с)
/ j\
(<*)

§ 10] ДВИЖЕНИЕ КОНЯ НА ДОСКЕ ИЗ 64 КЛЕТОК 57
Легко обнаружить, что последовательность (а) удовлетворяет
условиям (2), причем с клетки ти = л можно прыгнуть на клетку
л16 о
9 — Ш!_4
9—я, ""4е
Покажем, как из дорожек (а), (Ь), (с) и (d) получается дорожка
из 64 клеток, т. е. решение задачи Эйлера.
г 3 4 *
С клетки б конь может прыгнуть на , или, как мы будем в
дальнейшем постоянно говорить, соединяется с ..
Но тогда мы можем следующим образом получить из (а) и (d)
новую дорожку из 32 клеток:
5421321312431243
5342131231245786
4578678687568756
4657868768754213'^
т. е. мы просто конец дорожки (а) соединяем с началом дорожки (d)
— т
Далее, в силу принятых условий клетка 1%==к соединяется
с л /"1 = . • В самом деле
9—пх 4
[(9 - ти) - т, Г + [я,, - (9 - njf =
= [(9 - тх) - ти? + [(9 - nt) - nuf. (6)
Мы знаем *, что если конь в состоянии прыгнуть из (а, Ь) на
(ху у), то должно иметь место следующее соотношение:
(* — af + (y — Ь)* = 5.
Но, по условию, клетка (mlv пи) соединяется с (9 — tnv 9 — п%).
Поэтому
[(9 - тх) - тп? + [(9 - пх) - пи? = 5,
откуда, согласно (6),
[(9-я1,)-Я11]« + [я1,-(9-я1)Р = б,
т. е. (9 — #г16, /г16) также соединяется с (mv 9 — nt), что и
требовалось показать.
1 См. гл. II, § 7 , стр. 40.

58
ЗАДАЧА ЭЙЛЕРА О ХОДЕ КОНЯ
[ГЛ. III
4
5
5
4
5
3
4
6
7
4
2
5
8
2
1
7
6
1
3
8
7
3
2
6
8
1
1
8
6
2
3
7
8
3
1
6
7
1
2
8
5
2
4
7
6
4
3
5
8
5
1
4
7
7
2
2
5
8
4
1
6
6
3
3
Таким образом получается вторая дорожка из 32 клеток,
составленная из дорожек (Ь) и (с) так, как было составлено (е):
ю
Остается, следовательно, две дорожки (е) и (f) соединить в одну
дорожку. Как это сделать?
Дорожка (е) заканчивается клеткой л ~~OTl6 = 0 - Кроме того до-
9 — л1б 6
рожка (е) замкнута, т. е. ее конец n~~ i6 = Q соединен с нача-
у — /?1г, о
mi 5
лом 1 = с
о
п\
. Заметим, что такая замкнутость всегда выполняется,
когда (w16, пи) соединяется с (9 — ти 9 — #t), так как
[(9-т1)-«1,]« + [(9-я1)-я1|]« = 5 =
= [(9-«te)-'"i]2 + [(9-«16)-"1]2.
По той же причине замкнутой будет и дорожка (f). Отыщем
з дорожке (f) клетку, соединяющуюся с концом 3 дорожки (е).
о о
Это будет клетка 2. В силу замкнутости (f) мы можем 2 сделать
началом, а соседнюю с ней клетку . — концом, т. е.
преобразовать (f) следующим образом:
8 6 7 ... 3 4 5 7
2 1 3 ... 3 5 3 4
и приписать полученную дорожку к (е). Это даст нам такое
решение задачи Эйлера:
о
5
4
4
4
3
5
6
2
4
7
5
1
2
8
7
3
1
6
8
2
3
7
6
1
1
8
8
3
2
6
7
1
3
8
6
2
1
7
8
4
2
5
7
3
4
6
5
1
5
8
4
2
7
7
2
4
8
5
1
3
6
6
3
8678687568756542
2131231245786465
1321312431243457
7 8 6 8
6 8 7 5
13 5 3 4
• (г)

§ 10] ДВИЖЕНИЕ КОНЯ НА ДОСКЕ ИЗ 64 КЛЕТОК 59
к
Мы получили замкнутое перемещение коня, так как начало ^
7
соединяется с концом .; отсюда вытекает следующая важная
теорема.
Теорема I. Для всякой клетки обыкновенной шашечницы
существует замкнутое решение задачи Эйлера,
Доказать это весьма легко. Пусть, например, клетку (1, 1) мы
приняли за исходную клетку. В силу замкнутости можно дорожку
(g) преобразовать так, чтобы (1, 1) была началом, а
предшествующая клетка (2, 3) —концом перемещения коня, т. е. написать сна-
13 1 7 7 5
чала - , затем ~ , о и т- Д« Д° 4 > затем к приписать начало
2
и все следующие клетки до 3. Тогда получится:
1
1
3
2
1
3 .,
7
.. 4
5
5
4
3
2
4 ..
2
. 3*
а это и есть искомое решение задачи.
Нам удалось решить задачу Эйлера, соединив две дорожки из
32 клеток в одну, и в этом нам помогла счастливая случайность:
для конца ^ первой дорожки нашлась клетка 9 во второй дорожке,
соединяющаяся с «• Но оказывается, что если это обстоятельство
не имеет место, все же можно редшть нашу задачу, как это
утверждает следующая теорема.
Теорема II. Если дорожка из 16 клеток:
(алр я,), (/Hj, л,), ..., (mw nu) (1)
удовлетворяет условиям (2) и (яг,б, пи) соединяется с (9—mt,
9 — /zt), то из дорожки (I) и дорожек
(9 — mt, nt), (9 — т%, я.2), ..., (9 — тш л16), (3)
(mv 9 — ^), (/я„ 9 — л2), ..., (тш 9 — л16), (4)
(9 — /я,, 9 — ^), (9 — /яа, 9 — я2), ..., (9 —/w16, 9 —я16) (5)
можно построить дорожку из 64 клеток.
Доказательство. По условию (/я18, я1в) соединяется
с (9 — mv 9 — nt); но тогда, как это нами было показано выше,

60 ЗАДАЧА ЭЙЛЕРА О ХОДЕ КОНЯ [ГЛ. III
клетка (9 — лг{6, л,в) должна соединяться с (лг1} 9—^), откуда
получаем две замкнутых дорожки из 32 клеток:
(«1, «i)> (лг2, л2), ..., (лг1С, л16),
(7)
(9 —/и„ 9 —л,), (9 — лг.2, 9 —л2), ..., (9 — лг1в, 9 — л10)
и
(9 —«J, л,), (9 — лг2, л2), ..., (9-~лг10, л16),
(о)
(«л, 9 —лг), (лг2, 9 —л2), ..., (/л16, 9-л16).
Теперь все наши усилия должны быть направлены к тому, чтобы
дорожки (7) и (8) соединить в одну дорожку. Если бы в дорожке
(7) нашлась клетка (/л, л), соединяющаяся с клеткой (\х, v) из
дорожки (8), то это соединение можно было бы сделать весьма
просто, поступая следующим образом. Сделаем в (7) (лг, л)
началом, а предшествующую клетку (лг', л') — концом. Для этого
выписываем из (7) все клетки, начиная с (лг, л) и кончая (9 — /л16, 9 — л1С),
и затем приписываем (ти п{), (лг2, л2), . ..,(лг', л'), что
позволительно, так как конец (9—-лг1е, 9 — л1б) соединяется с (mv nt)?
В результате получим замкнутую дорожку:
(лг, л), . .., (9 —лг16, 9 — л,6), (tnv nt), (лг2> л2), ..., (лг', л'). (9)
Аналогичным образом преобразуем (8):
(|х, v), ..., (лг16, 9 — л16), (9 — mv лД (9 — /л2, л2), ..., (pt'f v'), (10)
где (jji', у') — клетка, предшествующая (ja, v).
Теперь сразу видно, как можно построить искомое перемещение
коня: надо (10) переписать в обратном порядке и потом приписать
(9). Получится:
0*\v'), . ..,(9 —лг2, л2), (9 — mv nt), (лг1б, 9 — л1С), ..., (ja, у),
(лг, л), ..., (9 —/и1в, 9 —л1б), (лга, пх\ . ..,(лг\ л').
Следовательно, остается еще установить, что такие две клетки
(лг, л) и (jjl, v) действительно существуют.
Чтобы это показать, вообразим, что конь перемещается из
(9 — лг16, 9 — л16) на (9 — лг13 пх) следующим образом:
(9— лг1б, 9 —л16), (а1? bt), . ,.,(av ft4), (ew, 0A+1), ..., (9 —лг, л^.
Пусть (яА, 0ft)—последняя клетка, принадлежащая дорожке (7).
Тогда (ам, bh+i) не может быть вне (8), она непременно должна

§ II] ПОСТРОЕНИЕ ДОРОЖКИ ИЗ 16 КЛЕТОК 61
входить в число клеток дорожки (8), так как (7) и (8) вместе
взятые содержат все клетки шашечницы.
Таким образом мы действительно можем принять (afc, bh) за
(т, п) и (ak+v bM) за (jx, v), и тем самым теорема полностью
доказана.
Итак мы видим, что решение задачи Уйлера сводится к
построению 16-клеточной замкнутой дорожки, удовлетворяющей условиям
теоремы П. Однако следует заметить, что найденное согласно
теореме II перемещение коня по всей доске не всегда будет замкнутым.
Как же практически можно найти дорожку (1)?
Очевидно, что с помощью проб ее получить можно, не часто
не совсем легко и удобно. В следующем параграфе мы как раз
и приводим один из методов разыскания такой дорожки, дающий
целый класс решений задачи Эйлера.
11. Построение дорожки из 16 клеток и решение задачи
Эйлера
Сущность этого метода состоит в том, что шахматную доску
делят на четыре равных части, по 16 клеток в каждой (фиг. 20),
и в каждой части конем проходится замкнутая дорожка, состоящая
из четырех клеток. В общей сложности у нас получатся в каждой
части четыре дорожки, содержащие вместе 16 клеток шашечницы.
Выберем из каждой части доски по одной четырехклеточной
дорожке ^ так, чтобы на их 16 клеток были наложены ограничения
(2), т. е. потребуем, чтобы имели место условия
при mi=mky 1 при т? = 9 — ткУ ^ при mi — 9 — ml
Если затем эти 16 клеток удастся соединить в одну дорожку
v^i» У\)> (-^2» Уъ/> •••> 0*16» -Ую)»
в которой конечная клетка соединяется с (9 — xv 9—yt), то
решение задачи Эйлера будет обеспечено.
Рассмотрим прежде всего замкнутое перемещение коня в одной
из четвертей шашечницы, например в первой четверти. Обозначим
через а0, а1У #2 и аъ его последовательные положения и соединим
эти клетки а01 аи аа, а3 прямыми. Легко видеть, что после такого
соединения получится либо ромб, либо квадрат (фиг. 21).
Обозначим далее соответственно через bQ} biy &2, bz, с0, с1% с2, cz
и dQ, dt1 d2, dB замкнутые дорожки во второй, третьей и
четвертой четвертях. Оказывается, что в силу ограничений (2) возможны
только следующие случаи:
|-(2)

62
ЗАДАЧА ЭЙЛЕРА О ХОДЕ КОНЯ
[ГЛ. III
a) Два ромба одинаково направлены и находятся в одной
половине шашечницы, а в другой лежат квадраты с параллельно
направленными сторонами. Одно из возможных расположений ромбов
и квадратов указано на фиг. 21.
b) Второе расположение получается из предыдущего, если
четверти шашечницы, содержащие ромбы, повернуть каждую на 90°
(фиг. 21а).
c) Два ромба находятся в диаметрально противоположных
четвертях и неодинаково направлены, а именно: один направлен вдоль
\hJ
\Ч»
I
\к
У
1
X*"
Т
***
^
s
A
ж*>
S
A
1b,
1
Фд
/
Од
°\
d!\
•uq-V
1
м*
x ¦
V
cy
^
s>
V.
^
>
<s
s
<
\
*s
s
\
\\
3
\
V
[iT
k
\
-v
^
"s^
V
V
[1
N
\
\b
ф
4i
Л
JS.
<1A
\
^
X
\
л<*
s
\
4
s
s
\
jy
Лс
v
s
s
ц
Л0? 1
\
„*>
S*
\
*"**2 i
Фиг. 21. фиг. 21а.
правой диагонали, а другой вдоль левой диагонали. На остальных
же четвертях лежат квадраты, но уже не с параллельно
направленными сторонами (фиг. 22).
d) Последнее расположение получим, если четверти шашечницы,
содержащие ромбы, повернуть каждую на 90° (фиг. 22а).
Но расположения с) и d) необходимо отбросить, так как здесь
нельзя связать четыре дорожки в одну. Остаются случаи а) и Ь),
и мы сейчас покажем, что действительно, располагая в каждой
четверти ромбы и квадраты так, как это указано в пунктах а) и
Ь), можно получить решения задачи Эйлера и среди них
замкнутые. Мы ограничимся рассмотрением расположения а).
Легко видеть, что существует всего лишь восемь расположений
ромбов и квадратов типа а), но все они получаются из одного
с помощью вращения доски и зеркального отражения колонн.
Поэтому вполне достаточно рассмотреть расположение ромбов и
квадратов фиг. 21. Здесь
<*о> «1» «а, я3> *о, К К *з> с» cv cv cv d*> dv rf2, d3 (11)
как раз образует 16-клеточную дорожку, причем ее конец d%
соединяется с клеткой, диаметрально противоположной нача-

§11] ПОСТРОЕНИЕ ДОРОЖКИ ИЗ 16 КЛЕТОК 63
лу а0 *. Необходимо отметить, что существует еще ряд дорожек,,
дающих новые решения задачи Эйлера, например:
d0, dv rf2, d8, <?a, cv cQy c8, tf0, av я2, я3, ?0, 63, ?2, ^;
*з» co» cv cai <*з» <*a> rfi» <*o> *n *2i аз> <*0, Ьг> h> bv *>&
и т. д.
Проведем все же наши операции до конца, чтобы показать, что
из (11) получается замкнутое решение. Заменив а0, а1э а2, я3, ^о>
Фиг. 22. Фиг. 22а.
*i> *2> ^з> со> <Ч> **> ^з» rfo> d» dv dv их координатами, получим:
4312124357865687
421357867865312 4'
откуда, согласно предыдущему параграфу, будем иметь еще три
16-клеточные дорожки:
5687875642134312
421357867865312 4»
4312124357865687
5786421321346875*
5687875642134312
57864213213 46875'
1 Если мы имеем клетку (т, л), то клетка (9 — т, 9 — п) называется
диаметрально противоположной относительно {т} п). Вообще для
шашечницы из л» клеток клетка (л + 1 —* а> n + 1 — b) будет диаметрально
противоположна клетке (а, Ь).

^4 ЗАДАЧА ЭЙЛЕРА О ХОДЕ КОНЯ [ГЛ. II
Из этих дорожек получаются две замкнутые дорожки:
4312124357865687
4213578678653124
5687875642134312
5786421321346875;
5687875642134312
4213578678653124
43121243578^5687
5786421321346875
(12)
(13)
.но 32 клетки каждая. Постараемся теперь соединить их в одну
2
дорожку. Легко видеть, что конец первой дорожки соединяется
с клеткой з второй. Поэтому (13) переписываем так:
3 4 ... 5 7 8 5
3 1,... 4 5 7,... 2
и приписываем к (12). В результате получится решение задачи
Эйлера:
4312124357865687
4, 2, 1, 3, 5, 7, 8, 6, 7, 8, 6, 5, 3, 1, 2, 4
5687875642134312
21321346875
13421343124
87542135687
86578656875
12457864312,
5 4
причем оно оказалось даже замкнутым, так как 2 соединяется с 4.
Если клетки в порядке следования отметим числами 1, 2, 3,
4,..., 64, то получим следующую наглядную картину
перемещений коня (фиг. 23).
5
3
3
6
6
7
4
1
5
8
8
2
2
7
7
6
1
4
8
5
4
2
6
7
3

§ 12]
МЕТОД ЭЙЛЕРА
65
12. Метод Эйлера
В двух предыдущих параграфах было дано изложение метода
Вандермонде. Метод Эйлера базируется на несколько ином
принципе, и чтобы нагляднее представить себе, в чем он заключается,
разберем следующий конкретный пример.
Поставим коня на произвольную клетку, например на (1, 1), и
впишем в нее число 1, а в диаметрально противоположную клетку
впишем число 33. Передвинем затем фигуру наугад на пустую
клетку, например на клетку (3, 2), в которую впишем число 2,
По
\43
\37
\iz
\51
lL
36
11
50
39
14
48
9
38
13
2
35
15
40
8
47
3
34
45
6
41
16
46
7
18
43
4
~зз\
т
44\
5
17 \
42}
[38
\з1
\48
Г
\36
\Z7
Ш
[з
47
6
37
32
41
4
35
26
30
39
8
45
28
33
г
43
7
48
29
40
1
44
25
34
50
9
60
17
56
13
64
23
59
18
49
12
61
24
55
14
10
51
20
57
16
53
22
63
19\
58
11
52
21
62\
15Ч
54\
Фиг. 23. Фиг. 2з.
а в (б, 7), как диаметрально противоположную, впишем 34. Далее
с клетки (3, 2) или 2 совершенно произвольно передвигаемся на
новую пустую клетку, например на клетку (5, 1). Вписываем в (5, 1)
число 3, а в диаметрально противоположную клетку (4, 8) —число 35
и т. д. Перемещаясь подобным образом, мы дошли без
повторения до клетки (8, 6) или 19. После 19 перемещение без
повторения клеток оказалось уже невозможным. Таким образом у нас
получились дорожка
1, Z) О, 4, ••., 1а
и дорожка
33, 34, 35, 36, ..., 51,
состоящая из клеток, диаметрально противоположных клеткам
дорожки 1, 2, 3,..., 19.
Из фиг. 24 видно, что довольно много клеток осталось пустыми,
но часть из них можно все же заполнить числами. Для этого
заметим, что из угловой клетки 1 конь может прыгнуть на пустую

ее
ЗАДАЧА ЭЙЛЕРА О ХОДЕ КОНЯ
[ГЛ. Ш
клетку (2, 3); в нее мы впишем 64, а в диаметрально
противоположную — 32 и затем совершим произвольный ход на одну из
оставшихся пустых клеток, например на (3, 1) или 63. Ей будет
соответствовать диаметрально противоположная клетка с числом 31 и т. д.
до тех пор, пока не начнутся повторения.
Таким образом у нас получились еще две новых дорожки:
\10
\49
Ш
\37
/>'
\т
\гв
\jl
2В
36
11
5D
27
$4
39
14
48
9
А
В
38
18
2
83
35
30
С
0
Е
F
15
40
8
47
f
е
й
с
62
3
31
34
45
6
Ь
а
41
16
46
7
32
59
18
43
4
61
jJl
58\
19
44\
5
60\
"т
Щ
1, 64,
33, 32,
63,
31,
58
26
(фиг. 25), которые в соединении со
старыми дают две дорожки:
58, 59, 60, ...,
..., 64, 1, 2,.
19
(I)
26, 27, 28,
32, 33, 34,.
51. (II)
Фиг. 25.
После этого у нас осталось еще
12 пустых клеток; в них мы впишем
буквы A, a, By b9 С, с, D, d, Ey e, Fy /, причем большими буквами
отмечены клетки, диаметрально противоположные клеткам с
такими же, но малыми буквами. Например А диаметрально
противоположна а. Постараемся теперь все эти клетки присоединить к
дорожкам I и II.
Для этого необходимо будет воспользоваться так называемым
преобразованием Бертрана, которое заключается в следующем.
Пусть мы имеем какую-нибудь дорожку из i клеток:
(ти njy (/rc2, я2), ..., {тЬу nt)
и пусть (тку пк) (кф1~\) соединяются с (т^ nt). Тогда можно
преобразовать нашу дорожку так:
{mv п^у (яг2, л2) ,..., (ткуПк)у
{т^п^у (m^v п^) ,-.., (ткПу пкЧ).
Теперь возвратимся к нашей задаче.
Постараемся к дорожке (I) присоединить две клетки с
различными буквами.
Легко видеть, что клетка 6 соединяется с концом 19, а следу.
ющая клетка 7 соединяется с клеткой. /, В свою очередь / сое.

§ 12] МЕТОД ЭЙЛЕРА 67
диняется с клеткой, обозначенной большой буквой В. Применяя
преобразование Бертрана к дорожке (I) и присоединяя /, В,
получим
58, 59, ..., 64, 1, 2, ,.., 6, 19, 18, ..., 7/ B.Q0
Для (II) достаточно выписать в соответствующем порядке
диаметрально противоположные клетки. Получим:
26, 27, ..., 32, 33, 34, ..., 38, 51, 52, ..., 39, F, b. (IIt)
Снова преобразуем (It), заметив, что клетка 12 соединяется с
концом Б, а клетка 11, следующая за 12 в (1Д — с клеткой D и
наконец D с клеткой с (Ь нельзя брать, так как оно уже вошло
в (ПА)). Получим:
58, 59,..., 64, 1, 2,..., 6, 19,..., 12, Я,/, 7,...,ll,D,c 0a)
и соответственно:
26, 27,..., 32, 33, 34,.,., 38, 51,..., 44, bt F} 39,..., 43, d, С. (И2)
Опять преобразуем (1а)* Конец с соединяется с 16, а 15,
которое следует в (12) за 16, соединяется с а (можно было вместо 16
и 15 взять 2 и 3). В свою очередь а соединяется с Е.
Отсюда имеем:
58, 59, ..., 64, 1, 2, ..., 6, 19, ...,
... 16, с, D, И, ..., 7,/, В, 12, ..., 15, а, Е (13)
и
... 26, 27, ..., 32, 33, 34, ..., 38, 51, ...
... 48, С, rf, 43, ..., 39, F, Ь% 44, ..., 47, Л, е. (П3)
Итак все буквы уже присоединены. Остается только (13) и (П3)
связать в одну дорожку. Для этого найдем в (13) такую клетку,
которая соединяется с 26, являющемся началом дорожки (П3), а
предшествующая клетка — с концом Е дорожки (13). Легко видеть,
что этому условию удовлетворяет клетка 63. В самом деле, клетка 63
соединяется с клеткой 26, а клетка 62, предшествующая клетке 63,—
с концом Е дорожки (13). Поэтому к дорожке (18) применяем
преобразование Бертрана так, чтобы 63 оказалось в конце. Это
даст нам:
58, 59, ..., 62, Е, о, 15, .,., 12, Б,/, 7, ...
..., И, А С, 16, ..., 19, 6, ..., 1, 64, 63.

68 ЗАДАЧА ЭЙЛЕРА О ХОДЕ КОНЯ [ГЛ. III
Переписываем (П3):
26, 27, ..., 30, *, Л, 47, ..., 44, Ь, F, 39, ...
... 43, d, С, 48, ..., 51, 38,..., 33, 32, 31.
Теперь мы можем связать полученные дорожки в одну, а именно в
58, ..., 62, Еу а, 15, ...
12, Я,/, 7, ..., 11, D, с,
16, ..., 19, 6, ..., 1, 64,
63, ... 26 ..., 30, е, А,
47, ..., 44, Ь, F7 39, ...,
43, d, С, 48, ..., 51,
38, ..., 31,
причем получилось даже замкнутое
решение задачи с конем.
Фиг. 26. Принимая клетку 58 за исходную,
получим следующую картину
перемещения коня (фиг. 26).
К сожалению, метод Эйлера обладает одним существенным
недостатком: он громоздок и часто бывает утомителен. В
дальнейшем были найдены другие способы решения, гораздо более
простые и изящные, как, например, метод Коллини.
13. Метод Коллини
Коллини, секретарь знаменитого философа XVIII века Вольтера,
предложил очень изящный способ решения задачи Эйлера.
Выделим в обыкновенной шашечнице средний квадрат из 16
клеток. Он будет окружен рамкой из 48 клеток. Затем разместим
четыре коня на маленьком четырехклеточном квадратике,
примыкающем к краю доски, и обозначим их положение буквами ах% bv
cv dt (фиг. 27.) Если мы станем перемещаться конем at вдоль
края доски, то, пройдя последовательность клеток #2, я3,..., я12,
он сможет вернуться на место av так как ап соединяется с av
Прыгнем затем из я12 на центральный квадрат и опишем конем
такой квадрат или ромб, чтобы можно было вернуться на исходное
положение av В данном случае это будет ромб а13, aw an, аи.
\17
\S4
\35
\58
Г
ш
\зз
[30
35
53
18
55
34
31
46
9
53'
16
39
1Z
57
10
29
i?j
60
37
52
19.
6
45
8
dL
15
40
13
38
51
20
5
28
64
61
42
25
44
7
48
21
41
14
63
2
23
50
27
4
S2\
1
24 \
43\
26 \
' з\
22\
Щ

§ 13] МЕТОД КОЛЛИНИ 69
В конечном счете у нас получится такая замкнутая дорожка:
Н "з
13 а11 а1Ь а1в»
(14)
состоящая из двух замкнутых частей:
а< а*
ап и axz аХ1 a1Vt a1B.
Точно так же для остальных коней получатся замкнутые
перемещения:
btb%
dx d%
Ьъ bis Кг 6ib hv (15)
^12 ^13 Ci4 C1S ^16» (*")
dn di* du di* dn> (17)
каждое из которых распадается на
две замкнутых части.
Дорожки (14), (15), (16) и (17)
легко связать в одну, причем можно
их соединить так, чтобы получалось
как замкнутое, так и незамкнутое
перемещения. Легко видеть, что за
некоторыми исключениями
(которыми» являются клетки av a7, bv.
рй?
и„
и?
Mfc
К
Li
4
h
CIZ
щг
4
ь,
ог
OjO
ь9
dx
h
%
%
4
ъ
4
<b
%
%
4s
^
%
*г
fc
&
**
dw
%
%
%
4
"в
d3
%
%
•4?
4
fc
%
%
fc
d7
aB
c6
bs
ds
«4
H\
a,\
c7\
bs\
ds\
°s\
%|
M
Фиг. 27.
bXQi d^ и d8) любая клетка одной
дорожки может быть соединена
с клетками некоторой другой дорожки. Например ахв соединяется
с br Воспользовавшись этим обстоятельством, получим:
212 а13
аы Ь%
Къ ьп
*ie К
Но Ьх соединяется с с1б, откуда имеем:
а1 • • • ^12 ^13 • • • ^16 ^2 • • • ^12 *13 • • * ^16 *1 *Ч6
В свою очередь ct соединяется с rf8> a потому мы можем
построить дорожку
aiB h
'16 "1 ^16
cxdz ... rf18 dx rfa,
т. е. получилось незамкнутое решение задачи Эйлера.
Но иногда могут получиться замкнутые перемещения, как
показывает нижеследующий пример. Преобразуем (17) так:
dg ... d16 dx d% dz.
dz соединяется с аПУ откуда получаем:
di • • • dia d% d* dz ai* • • • ai ax* a*

70 ЗАДАЧА ЭЙЛЕРА О ХОДЕ КОНЯ [ГЛ. Ill
В свою очередь ап соединяется с с13, а потому
dg ... du dl d2 dz
Наконец си соединяется с bv и это приводит к окончательному
решению
dh ... di6 dx rf2 ds a^ ... at я1в ... д13 cn ... cx cl0 bt... biGi
которое оказывается замкнутым.
Можно указать также несколько более систематический путь
использования метода Коллини. Выберем из каждой
последовательности (14), (15), (16) и (17) по паре соседних клеток так, чтобы
они в совокупности составили восьмиклеточную дорожку; после
этого задача Эйлера будет тотчас же решена. Например легко
усмотреть, что
al az du dn cz ci &3 b6
дорожка указанного типа. Поэтому (14), (15), (16) и (17)
преобразуем соответственно так:
аг а{ я1С ... я3,
diB dx d>2 ... с/, j.,
С3 C% C\ CIB * * * ^V
h bi Ьг b2 bi bn ••• &16 ••• ^e»
после чего связываем их без труда в одну дорожку
#2 ... Яд а1в .. • «15 сг ... Cg u§ ... #в,
состоящую из 64 клеток.
14. Правило Варнсдорфа
В небольшой брошюре, опубликованной в 1823 г. *, Варнсдорф
предложил следующее правило:
a) коня следует ставить каждый раз на клетку, из которой
можно совершить наименьшее число прыжков на непройденные
клетки;
b) если таких клеток с наименьшим числом прыжков не одна,
а несколько, то совершенно безразлично, на какую из них следует
ставить коня.
^Warnsdorf, Des Rflsselsprunges einfachste und allgcmeinste LOsung.

§ И]
ПРАВИЛО ВАРНСДОРФА
71
К сожалению, до сих пор не найдено строгого математического
обоснования этого правила, но в первой своей части оно
неоднократно подтверждается эмпирически
не только на обыкновенной
шахматной доске, но и на всякой
прямоугольной или квадратной
шашечнице, допускающей решение задачи
Эйлера.
Поставим коня на угловую клетку
(1, 1); тогда, следуя правилу
Варнсдорфа, мы обойдем все 64 клетки
доски без повторений так, как это
показано на прилагаемой схеме
(фиг. 28); на основании следующей
таблицы можно полечить и другие
решения задачи Эйлера: Фиг. 28.
Номер клетки,
на которой
стоит конь
1
2
8
23
25
29
32
Номер клетки
с наименьшим
числом
прыжков
2 ИЛИ 12
3 или 35
9 или 23
24 или 58
26 или 56
30 или 52
33 или 45

Наименьшее число
прыжков
1
5
3
3
5
3
3
3
Номер клетки,
на которой
стоит конь
33
36
46
49
55
56
61
Номер клетка
с наименьшим
числом
прыжков
34 ИЛИ 40
37 или 53
47 или 49
50 или 54
56 или 60
57 или 63
62 или 64

Наименьшее число
прыжков
4
4
3
3
2
2
1
Мы видим, что когда конь стоял на 1, был выбор между
клетками 2 или 12. Если бы вместо 2 было взято 12, то получилось
бы другое решение. Далее, находясь на 2, конь, по правилу
Варнсдорфа, может прыгнуть на 3 или 35; мы взяли наугад клетку 3,
но если бы вместо 3 была бы выбрана клетка 35, то опять-таки
получилось новое решение задачи Эйлера, и т. д.
Необходимо отметить, что вторая часть Ь) правила не всегда
справедлива *, т. е. часто бывает, что выбор клетки с
минимальным числом прыжков имеет решающее значение. В качестве при-
1 Впрочем, в том случае, когда конь начинает двигаться из угловой
клетки, вторая часть Ь) правила, повидимому, справедлива. Строгэ
придерживаясь правила Варнсдорфа, именно с угловой клетки и следует начинать
обход, так как в начале с угловой клетки можно совершать наименьшее число
прыжков на другие клетки, из которых еще ни одна не пройдена.
\б4
113
\16
77
\so
\35
\14
[1
17
10
61
34
15
12
51
36
20
63
18
49
60
53
2
13
9
48.
55
62
33
46
37
52
56
21
44
47
54
59
32
3
43
8
57
24
45
40
29
38
22
25
6
41
58
27
4
31
7\
42 \
23\
2б\
5
зо\
39\
28\
. —J

72
ЗАДАЧА ЭЙЛЕРА О ХОДЕ КОНЯ
[ГЛ. III
мера рассмотрим для большей простоты квадратную шашечницу
из 36 клеток. Пусть конь начинает свое перемещение из клетки
(3, 3), обозначенной цифрой L Придерживаясь строго правила Варнс-
дорфа так, как это указано на фиг. 29, мы не получим решения
р" ¦ '
\15
\zo
\з
\28
\13
19
4
Z7
14
21
Z
16
31
18
1
12
Z9
5
Z6
33
30
9
Z2
3Z
17
Z4
7
34
11
Is]
6 \
31
10'
23\
8]
\26
\15
\18
\з
\36
[13
17
4
25
14
19
Z
3Z
27
16
1
12
35
5
24
31
34
9
Z0
28
33
ZZ
7
30
11
1з\
6
Z9\
ю\
21
8
Фиг. 29.
Фиг. 30.
задачи Эйлера, так как клетка (1, 6) остается пустой. Но можно
по правилу Варнсдорфа еще перемещаться так, как показано на
фиг. 30; мы видим, что здесь все клетки оказались заполненными.
15. Шашечницы из 16, 25, 38 и 49 клеток
В предыдущих параграфах рассматривалась главным образом
шашечница из 64 клеток.
Все разобранные методы решения могут быть так или иначе
распространены на шахматную доску из я2 клеток, но мы здесь
ограничимся лишь весьма частными случаями.
Относительно шашечницы из 16 клеток известно, что для нее
задача Эйлера невозможна, т. е. можно обойти без повторения
только 15 ее клеток; угловая клетка остается пустой.
Переходя к доске из 25 клеток, мы должны прежде всего
отметить, что вообще на всякой шашечнице, состоящей из нечетного
числа клеток, замкнутое перемещение коня невозможно.
Докажем это предложение. Пусть наша доска состоит из ц
клеток и пусть мы имеем следующую замкнутую дорожку:
На основании уравнения (13) § 8 главы II получаем такие
равенства:
(^-*1), + (y»-j't)ts=6»
(*,-*«),+0',-\у,),=б,
(jCi—K^ + Ctt-JV)»^,

§ 15] шашечницы из 16, 25, 36, 49 клеток 73
откуда, складывая, будем иметь:
[ (*» — *i)' + (¦*»—х%У' + • • • + (*!—*н-)2] +
+ [(У. -Л)' + СУ.-Л)8 + • • • + CVi ~^Л = 5ц
или после раскрытия круглых скобок и некоторых
преобразований:
2[(лг? + — + *? — *t*a — ...— х±Хр) +
+ (у\+. • • н-у^-лу*- ¦ • • -л^)]=5^
Мы видим, что 5)л делится на 2, что возможно только в том
случае, когда }Л четно. Итак мы показали, что если на шашечнице
из pi клеток существует замкнутое решение задачи Эйлера, то \х
может быть только четным; если же jx нечетно, то замкнутые
перемещения невозможны.
Таким образом, обращаясь к шашечницам из 25 и 49 клеток,
мы видим, что они допускают только незамкнутые решения, и
нашей целью будет разыскание этих решений.
Доска из 25 клеток состоит из одной центральной клетки,
окруженной рамкой из 24 клеток. Поставим в центр коня bQ1 а на
угловую клетку второго коня at (фиг. 31). Затем, следуя методу
Коллини, совершим обход фигурами at и bQ вдоль рамки,
окружающей центр. В результате у нас получатся две дорожки:
а± аъ • • • av
и
bQ Ьг ... Ь1&.
Если мы их свяжем, то тем самым задача будет решена. Но
это сделать весьма нетрудно, так как Ьи соединяется сяаив силу
замкнутости аха^... as имеем:
откуда получается сразу решение задачи Эйлера:
Ь0 ... Ьи я2 ... а8 а±.
Для шашечницы из 49 клеток можно получить решение с
помощью правила Варнсдорфа. Мы предлагаем читателю
самостоятельно найти решение, поставив коня на одну из угловых клеток.
Перейдем к доске из 36 клеток и воспользуемся методом Эйлера.
Прежде всего заметим, что здесь клетке (а, Ь) диаметрально
противоположной клеткой будет клетка (7 — а, б — Ь). Поставим коня,
например, на клетку (1, 1), которую мы обозначим через № 1.
Клетка, диаметрально противоположная № 1, будет иметь № 19

74
ЗАДАЧА ЭЙЛЕРА С ХОДЕ КОНЯ
[гл. III
(в случае шашечницы из (2ft)2 клеток подобная клетка получит
номер 2^+1). После этого, следуя методу Эйлера, мы будем иметь
следующую схему (фиг. 32), причем клетки, диаметрально
противоположные 1, 2, 3, 4,... и 36, 35, 34,... занумерованы числами
19, 20, 21, 22,... и 18, 17, 16,... (для доски из (2ft)2 полей
поля диаметрально противоположные полям 1, 2, 3, 4,... и
(2ft)2, (2ft)2 — 1, (2ft)2 — 2,... получат соответственно номера
ТВ
4
\27
\12
\зз
[б_
26
13
34
5
28
19
¦Wnn
3
38
11
20
7
32
и
25
2
29
18
21
1
10
23
1В
31
в
"F\
1S\
зо\
3\
22\
17 \
Г-
\35
\2В
7
\22
LL
29
6
21
36
27
14
34
В
8
15
2
23
5
20
33
28
Ь
16
32
3
18
3
24
11
1э\
4
25\
ю\
17 \
а\
р>
Г
lbs
\.ь».
к
bfs
bio
а8
be
bi
b4
%
bo
a2
biz
bs
bu
a4
bz
by
°s\
b3\
bS\
bi3\
2h
Фиг. 31. Фиг. 32. Фиг. 33.
2ft»+1, 2ft2 + 2,2ft2 + 3, 2ft2 + 4,... и 2ft2, 2ft2-1,2ft2 —2,...).
У нас, таким образом, получились две дорожки:
32, ..., 36, 1, ..., 11
и
14, ..., 18, 19, ..., 29.
Присоединим к ним А, В, а и Ь. Воспользуемся для этой цели
преобразованием Бертрана. Тогда в конечном счете мы придем
к таким двум дорожкам:
32, ..., 36, 1, 2, 11, 10, ..., 3, а, Ъ,
14, ..., 18, 19, 20, 29, 28, ..., 21, А, В.
Но легко видеть, что b соединяется с 14, откуда сразу
получается замкнутое решение:
32, ..., 36, 1, 2, 11, 10, ..., 3, я, Ь9
14, ..., 18, 19, 20, 29, 28, ..., 21, Л, В.
Примем клетку 32 за исходную и перенумеруем клетки в
порядке прохождения числами 1, 2, 3,...,36, тогда будем иметь
следующую наглядную диаграмму (фиг. 33).

ДОБАВЛЕНИЯ
16. Решение задачи Эйлера о ладьях с помощью методов
символического исчисления
В § 1 было указано, что задача Эйлера о ладьях впервые была
решена методами символического исчисления. Здесь мы как раз и
собираемся дать изложение этого решения.
Мы знаем, что на шашечнице из я2 клеток п ладей можно
расставить Рп = п\ способами так, чтобы ни одна фигура не
угрожала другой. Эти Рп расстановок состоят из размещений
следующих типов:
a) Размещений типа Эйлера, т. е. такие размещения, у которых
главная диагональ аа! не занята ладьями. Число Qn этого типа
расстановок фигур нам как раз и надо определить.
b) Размещений с одной ладьей d на диагонали аа!.
Для того чтобы определить число размещений этого типа,
уничтожим колонну и строку, проходящие через клетку, на которой
стоит ладья d.
Тогда получим шашечницу из (л— I)2 клеток, и на лей
остальные наши фигуры образуют размещения эйлеровского типа. Что
касается ладьи d, то она может занимать п различных
положений * на диагонали аа1. Поэтому получаем, что существует всего
nQn-\ размещений рассматриваемого типа.
c) Размещений с двумя ладьями dt и d„2 на главной диагонали
аа1. Уничтожая колонны и строки, проходящие через dx и d%,
получим шашечницу с (п — 2)2 клетками и на ней размещение ладей
типа Эйлера. Но фигуры dx и d% могут занимать на аа' только
Сп=—^-g—- различных положений, а потому существует всего
ClQn-г Размещений типа с и т. д.
d) Вообще среди Рп размещений имеются размещения с р
ладьями на диагонали аа'. Уничтожая линии, проходящие через эти
ладьи, мы получим шашечницу из (/г— pf клеток и на этой доске
размещения Эйлера. Кроме того на диагонали аа' р фигур можно
разместить всего Срп способами, откуда мы имеем CnQn-p
расстановок типа d.
1 Так как главная диагональ йа! состоит из п клеток.

76 ДОБАВЛЕНИЯ [§ 16
е) Наконец имеется лишь одно размещение с п ладьями на аа!.
Из а), Ь), с), d) и е) сразу вытекает, что
Pn = Qn+dQn~x + ClQn.,+ ... + CpnQa_p+... + 1. (1)
Легко видеть, что если (Q + l)n раскрыть по биному Ньютона
и затем вместо Qw, Q71'1,..., Qn~p,..., 1 подставить соответственно
Qn> Qn-w'9 Qn-p>- - -А* т* е- показатели степени сделать
индексами, то получится как раз правая часть равенства (I)1. Поэтому
равенство (1) можно символически записать в виде
Яп = (<Э+1)*. (2)
Но при этом необходимо все время помнить, что Pn, <Qn,
Q*"1,..., Qn~p,.•. означают здесь не что иное, как Pn, Qn,
Q„_,,..., Qn-P- Существует целая теория, посвященная
символическим равенствам, а именно так называемое символическое
исчисление. Пользуясь методами символического исчисления, можно
показать, что если имеет место равенство (2), то должно
удовлетворяться символическое равенство
(р+*)»-«г+*+1д
причем хп, х"'1,... являются здесь не чем иным, как самыми
настоящими степенями числа л:2. Полагая л:= —1, получим:
(Р — 1)« = Q»
или, переписывая в обратном порядке и возвышая в степень би
ном (Р — 1)п:
q» = р» — CIP"-1 -f С*Р«-2 - С*Рп-3 + ... + ( -1)*.
Расшифровывая это символическое равенство, имеем:
Q„=^-^P„_1 + ciP„.a-c)3,p„_3+... +(-i)«, (3)
т. е. мы уже решили задачу Эйлера. Однако (3) можно несколько
упростить. Легко видеть, что
Рп — ClPn-l = nl — П • (П — 1)' = П{ — nl = °»
Зр _п(/г—1)(/г — 2) ( -QM—jg1-
п-з— з v J 3!
i Ср. книжку: Кудрявцев В., Суммирование степеней и числа
Берну л ли.
2 Доказательство этого соотношения мы вынуждены опустить.

§ 17] РЕШЕНИЕ ЗАДАЧИ О ФЕРЗЯХ 77
и вообще
откуда
л ч„_„,4___
о —*L_-*Lj_J!L_ , (-i)n*
ч«~~ 2! 3! "*" 4! ••• "•" л!
или
«.=»'(i-i+i—.+«=?).
т. е. получилась хорошо нам известная формула (7) § L
17. Решение задачи о ферзях на обыкновенной
шахматной доске
В первой главе мы упомянули, что для шашечницы из 64
клеток было найдено 92 решения задачи о восьми ферзях.
Оказывается, что из двенадцати решений могут быть получены все
остальные с помощью зеркального отражения колонн и поворота доски
на 90°, 180° и 270° по часовой стрелке. Вот эти решения:
I. (1, 5, 8, 6, 3, 7, 2, 4). VII. (2, 6, 8, 3, 1, 4, 7, 5).
П. (1, 6, 8, 3, 7, 4, 2, 5). VIIL (2, 7, 3, 6, 8, 5, 1, 4).
III. (2, 4, б, 8, 3, 1, 7, 5). IX. (2, 7, 5, 8, 1, 4, 6, 3).
IV. (2, 5, 7, 1, 3, 8, б, 4). X. (3, 5, 2, 8, 1, 7, 4, 6).
V. (2, 5, 7, 4, 1, 8, б, 3). XI. (3, 5, 8, 4, 1, 7, 2, б).
VI. (2, 6, 1, 7, 4, 8, 3, 5). XII. (3, б, 8, 1, 5, 7, 2, 4).
Читатель уже знает, что зеркальное отражение колонн сводится
к простому выписыванию цифр в обратном порядке. Легко также
показать, что поворот доски на 90°, 180° и 270° сводится к
простым арифметическим операциям над координатами клеток.
Пусть наши восемь ферзей занимают следующие восемь клеток
(1, а,), (2, я2), (3, я3)> •••> (8, а%). (4)
Повернем шахматную доску на 90° по часовой стрелке. Тогда
клетка (&, ah) примет положение клетки (ак, 9 — к), и потому
после такого поворота последовательность клеток (4) перейдет в
К, 8), (а„ 7), (я3, 6), ,.., (а8, 1). (5)

78 ДОБАВЛЕНИЯ [§17
Повернем еще раз доску на 90° в том же направлении; это
даст нам:
f8, 9-aJ, (7, 9-flfj, (6, 9-а,), ..., (1, 9-а8)
или, переписывая в порядке возрастания абсцисс:
(1, 9-*8), (2, 9-я,), (3, 9-я6), ..., (8,9-^). (б)
Наконец повернем шашечницу снова на 90° по часовой стрелке.
Получим из (6):
(9-^,8), (9-*„ 7), (9-я8, 6), ..., (9-^,1). (7)
Таким образом мы показали, что повороты доски на 90°, 180° и
270° сводятся соответственно к арифметическим операциям (5), (6)
и (7) над координатами клеток, занимаемых ферзями. Особенно
просто дело обстоит с поворотом на 180°, а именно, в этом
случае можно высказать следующее правило:
Если шашечницу повернуть на 180° по часовой стрелке, то
восемь ферзей
(at> я2, а3> я4, я3, а6, я7, я8) (8)
примут положение
(9 — я8, 9 —а7, 9 — я6, 9 — яй, 9 —а4, 9 — а3» 9 — #2, 9 —aj. (9)
Из этого правила легко вытекает одно любопытное свойство
симметрического решения; оказывается, что решение (8) является
тогда и только тогда симметрическим, когда сумма цифр ряда (8),
равноотстоящих от начала и конца, постоянно равна девяти.
Докажем это свойство. Если (8) симметрично, то это значит, что
(8) и (9) должны совпадать, т. е.
д1==9 — я8, откуда ^ + #3 = 9;
а% = 9 — av откуда аа + а7 = 9;
я8 = 9 — я0, откуда a3 + ^s = 9;
я4 = 9 —яй, откуда я4 + да = 9.
Обратно, если сумма цифр, равноотстоящих от концов (8),
постоянно равна девяти, то (8) и (9) совпадают и потому решение (8)
при повороте на 180° не меняется, т, е. симметрично.

§ 17] РЕШЕНИЕ ЗАДАЧИ О ФЕРЗЯХ 79
На основании этого свойства легко обнаружить, что среди
двенадцати приведенных решений только одно X является
симметрическим. Дальнейшие исследования показывают, что на шашечнице из
64 клеток совершенно отсутствуют дважды-симметрические решения.
Таким образом получается всего 11 простых и одно симметрическое
решение, откуда имеем действительно 11 • 8 + 1 • 4 = 88 + 4 = 92
решения.
Покажем, как с помощью операций (5), (9) и (7) и зеркального
отражения колонн можно получить из одного остальные решения.
В качестве примера возьмем расположение I, т. е.
(1, 5, 8, 6, 3, 7, 2, 4).
Это решение удобнее переписать в координатной форме:
(1, 1), (2, 5), (3, 8), (4, 6), (5, 3), (б, 7), (7, 2), (8, 4).
Поворачивая доску на 90°, получим согласно (5):
(1, 8), (5, 7), (8, 6), (б, 5), (3, 4), (7, 3), (2, 2), (4, 1)
или, располагая в порядке возрастания абсцисс:
(1, 8), (2, 2), (3, 4), (4, 1), (5, 7), (б, 5), (7, 3), (8, б),
т. е. после поворота на 90° мы получили:
(8, 2, 4, 1, 7, 5, 3, б).
Поворачивая доску на 180°, сразу получаем на основании
правила (9):
(9-4, 9-2, 9-7, 9-3, 9-6, 9-8, 9-5, 9-1)
или окончательно
(5, 7, 2, 6, 3, 1, 4, 8).
Наконец поворот на 270° дает согласно (7):
(9-4, 8), (9-2, 7), (9-7, 6), (9-3, 5),
(9-6, 4), (9-8, 3), (9-5, 2), (9-1, 1)
или после вычитания:
(5, 8), (7, 7), (2, 6), (6, 5), (3, 4), (1, 3), (4, 2), (8, 1).

80 ДОБАВЛЕНИЯ [§ IS
Располагая этот ряд в порядке возрастания абсцисс, мы получим:
(1, 3), (2, 6), (3, 4), (4, 2), (5, 8), (б, 5), (7, 7), (8, 1),
т. е. в другой записи:
(3, 6, 4, 2, 8, 5, 7, I).1
Таким образом при повороте на 90°, 180° и 270 ° мы из решения I
получим соответственно три новых решения:
1а (8, 2, 4, 1, 7, 5, 3, б),
1Ь (5, 7, 2, б, 3, 1, 4, 8),
1с (3, б, 4, 2, 8, 5, 7, 1).
Остальные решения определяются с помощью зеркального
отражения колонн; для этого, как мы знаем, надо цифры в решениях
I, Ie, 16, 1с переписать в обратном порядке. После такой операции
легко получится:
Id (4, 2, 7, 3, б, 8, 5, 1),
1е (б, 3, 5, 7, 1, 4, 2, 8),
U (8, 4, 1, 3, 6, 2, 7, 5),
Ig (1, 7, 5, 8, 2, 4, б, 3).
18. Исследование движения ладьи с помощью бесконечных
сумм и произведений
Формула (12) § б, с помощью которой можно определить число
несходных способов поступательных перемещений ладьи от первой
до /гс + 1-ой клетки, является громоздкой и неудобной. Поэтому
мы здесь приведем исследование2 русского математика XIX века
Бугаева.
Он нашел следующую формулу:
N(m) = N(m—l) + N(m — 2) — N(m — S) —
— N(m — 7)+...—A(s)N(m — s)+..., (10)
* Это решение можно получить также из (8, 2, 4, I, 7, 5, 3, 6) с по*
мощью правила (9).
2 Мы здесь имеем ввиду его работу «Об одном шахматном вопросе*.

§18] ИССЛЕДОВАНИЕ ДВИЖЕНИЯ ЛАДЬИ 81
где A(s) обращается в (•—1)* для всех целых чисел,
удовлетворяющих уравнению
и в нуль для всех остальных чисел.
Великий математик Эйлер первый показал, какую большую роль играют
в теории чисел соотношения между бесконечными суммами и
произведениями.
Вопрос о решении неопределенного уравнения
aixl + a2^2+ ••• +я«<,» = >я
и, в частности, уравнения (5) § б гл. II в целых числах он свел к
исследованию произведения
1
(1 — t*i) (1 — ta%)... (1 — &п)
путем его разложения в бесконечный ряд по степеням ?
Эйлерову теорию разбиения числа на т слагаемых до сих пор нельзя
считать вполне законченной, несмотря на то, что в XIX веке ею
весьма усиленно занимались такие математики, как Кэли, Сильвестр, Мак-
магон и др.
Вернемся к выводу формулы (10). Для нас особенно важное значение
имеет соотношение:
оо со
Д(1-х*) = 1 + 24(р)^ (11)
найденное Эйлером в 1741 г., в котором коэфициенты Л(р) имеют
значения, указанные выше. Из равенства (11) мы получаем:
1 = 1
оо оо
k=zl p=zO
Рассматривая левую часть этого равенства, заметим, что
откуда:
оо
-5—*—=IL!+**+**+¦•¦*
Па-4) ы
*=1

82 добавления [§18
Последнее произведение равно бесконечной сумме
1+2^№>**'
Ьс1
где N(k) выражает число решений неопределенного уравнения:
l-x± + 2-r2 + 3-xs+ ...+k-xk = k (12)
в целых неотрицательных числах. Поэтому, полагая N(0)=1, имеем:
СО
р=0
р=0
ИЛИ
СО СО
l=(%A(P)*)-(%NU>)**y
р~0 р=0
После перемножения этих двух бесконечных сумм у нас получится:
со
1 = 2*»«" (13)
причем
т
Д>=1; Bm = 2iA(s)N(m-syt (тфО).
s=0
Но равенство (13) возможно только в том случае, когда все коэфициенты
Вт) за исключением В$} равны нулю.
Поэтому мы будем иметь:
^A(s)N(m — s) = 0
5=0
или, в развернутой форме
N (т) = N (т — 1) + N (т — 2) — N (т — 5) —
— N(m — 7) + ... — A(s)N(m — s) f ... (10)
Члены правой части равенства (10) надо продолжать до тех пор,
пока т — 5 не станет меньше нуля.

§ 18] ИССЛЕДОВАНИЕ ДВИЖЕНИЯ ЛАДЬИ 83
С помощью формулы (10) N (т) очень легко вычислить.
Например для N (5) получается
N(5) = N(4) + N(3) — N(0)=:NW + N(3)—1
и, чтобы определить N(5), необходимо найти значения N(4) и N(3)
Согласно (10) имеем:
W(4)=W(3) + W(2),
N(3)=N(2) + N(0) = N(2)+l,
N(2) = N(l) + N(0) = N(l)+l,
A/(1)=/V(0)=l,
откуда:
N(2) = 2, Л7(3) = 3, Л/(4)=5,
и
iV(5) = 5 + 3~l=7.
Таким образом уравнение
xi + 2х2 + Злг3 + 4лг4 + 5лгй = 5
допускает всего семь целых и неотрицательных решений, а это
значит, что существует только семь несходных способов
передвижения ладьи от первой до шестой клетки.
И действительно, решая наше уравнение, получим такие семь
несходных способов передвижения:
l.pi> *1 *4> *2 *3> *1 *3> *1^2> ^1 *2> *1С
Кроме формулы (10) можно вывести еще одну замечательную
формулу, выражающую N(m) через предыдущие N. А именно
оказывается, что имеет место следующее любопытное соотношение:
mN(m) = N(m—l)b(l) + N(m — 2).8(2)+..,
...+N(l)b(m — l) + b(m), (13)
где b(k) означает сумму всех делителей числа k, причем в число
делителей включаются 1 и само k. Если известно разложение k на
первоначальных множителей, то b{k) определяется очень просто.
В арифметике, как известно, все числа разделяются на два рода:
на первоначальные и составные. Первоначальным называется такое
число, которое делится только на 1 и на самого себя. Если же
число делится на другое число, большее 1, то оно называется со-

84
ДОБАВЛЕНИЯ
[§ 18
ставным. Так 2, 5, 7, 11 и т. д. являются первоначальными
числами, а, например, 15 — составное, так как оно кроме 1 и 15
делится еще на 3 и 5.
Относительно составных чисел известно, что они могут быть
разложены на произведение первоначальных множителей и притом
каждое только одном способом. Так, если к число составное, то
* = Р?Р? ••• />«*,
где ри /?2,..., рп первоначальные, а а^..., ап целые
положительные числа. Все делители k поэтому имеют вид
Р\ Р\ ••• />&»>
где
0<Pi<*i> 0<P2<<*2> ... 0<prt<cv
Следовательно, если мы составим произведение
<Р? +Р\ +р\ + • • • +Р?)0§ +р\+р\ +... +р®...
то оно как раз будет равно сумме делителей 8(&) числа k.
Но в каждой из скобок стоит сумма членов геометрической
прогрессии, откуда по формуле суммы членов прогрессии получаем:
рщ + 1 — 1 pa-i+l — 1 pvn-bl — 1
»«--S=T-Srr--i5=r-- <">
Теперь, зная выражение 8(&), уже нетрудно определить N(jn),
коль скоро известны N(k)(k<^m). В качестве примера возьмем
N(6) и вычислим его по формуле (13):
67V(6)=:N(5)8(l) + ^(4)5(2) + N(3)S(3)-f
+ N(2) 8 (4) + N(1) 8 (5) + 8 (6).
Но 8(1)^=1 и по формуле (14).
5(2)Ц^- = 3; §(3) = |^1=4;
am —2п1 7- */к\ 58-1 «. */йч 22-1 За—1 10

§ 18] ИССЛЕДОВАНИЕ ДВИЖЕНИЯ ЛАДЬИ 85
Теперь, пользуясь формулой (13), вычисляем N:
УУ(1)=1, Л/(2) = 2, N(S) = S, Л^(4) = 5, N(5) = 7.
Поэтому
6ЛЧ6) = 7.1+Б-3 + 3.4+2-7 + 1-6+12==бв;
откуда:
yv(e)=f=ii.
Перейдем к выводу формулы (13). Возьмем производную от обеих частей
равенства:
00
i
1л
- ==1п2лГ(р)л*
П (1~**) р"о
*=1
Получим:
*% pN(p)x*-i
1—л: t1-x«t1-a«t,,,t1-jc»
или, умножив обе части на х:
^N(p)xP
г" • • • "Т*
Но
1— х ' 1— лг2^ 1— лгЗ^'" М— А*^ "'• оо
: л: + л;2 + л* + лг« +- лг» + je« + ...
1 — л:
Y=#= W +2Л-* + 2*+...
З*3 * * , о ^ .
откуда:
х , 2дг2 , 3*з
1— X М — Л*"Г(1 — АГЗ)"1" "'
= *+ (1 + 2)*в+(1+3)*«+...

86 ДОБАВЛЕНИЯ [§ 18
где kb k%}. •., к8 все возможные делители к Поэтому
оо
? pN(p)xP
l(l)x+b(2)x2 + h(3)x*+...+b(k)x*+...==p-g .
lN(p)xP
V—
Если теперь мы помножим обе части последнего равенства на
оо
и затем сравним коэфициенты при одинаковых степенях х} то получим как
раз формулу (13).

СОДЕРЖАНИЕ
Стр.
Предисловие • 3
Введение 5
ГЛАВА ПЕРВАЯ
ЗАДАЧА О ВОСЬМИ ФЕРЗЯХ
1. Задача о ладьях 8
2. Задача о слонах 14
3. Задача о л ферзях 17
4. Существование общего решения задачи о п ферзях 22
ГЛАВА ВТОРАЯ
ДВИЖЕНИЕ ФИГУР
5. Движения короля . • 28
6. Движения ладьи 32
7. Движения коня 40
8. Сравнительная сила шахматных фигур 46
ГЛАВА ТРЕТЬЯ
ЗАДАЧА ЭЙЛЕРА О ХОДЕ КОНЯ
9. Предварительные замечания , 54
10. Движение коня на доске из 64 клеток 55
11. Построение дорожки из 16 клеток и решение задачи Эйлера ... 61
12. Метод Эйлера ¦ 65
13. Метод Коллини 68
14. Правило Варнсдорфа 70
15. Шашечницы из 16, 25, 36 и 49 клеток - 72
ДОБАВЛЕНИЕ
16. Решение задачи Эйлера о ладьях с помощью методов
символического исчисления 75
17. Решение задачи о ферзях на обыкновенной шахматной доске . . 77
18. Исследование движения ладьи с помощью бесконечных сумм и
произведений 80

Редакция Я. Я. Бончкооского. Оформление Я. Я. Костиной, Корректура О. Я. Барашковой*
Сдано в производство 4/VII-1935 г. Подписано к печати ИДИ 1935 г.
Печ. лист. 5% Тираж 10.000. Формат 82Х1Ю!/л- Печат. знак, в печ. л. 46 000. Заказ Л 82.
Гл ред. общетехн. литерат. и номограф. № 82. Уполномоченный Глазлита № В-29614.
Ф-'са книги «Красный пролетарий» Партиздата ЦК ВКП(б). Москва, Краснопролетарская, К.
Отпечатано с матриц в 1-й Журнальной ттп. ОНТИ. Москва, Денисовский 30 Зак. 68.