x, y, z

Глава 5. Задача о ходе коня / Математика на шахматной доске

Гик Е. Я.

Комментарии: 0
<<< |1|…|4|5|6|7|8|9|10|11|12|…|19| >>>

Глава 5. Задача о ходе коня

Эта глава посвящена самой интересной задаче о коне и, пожалуй, вообще самой известной шахматно-математической задаче. Она заключается в нахождении маршрута коня на шахматной доске.

Обойти конем все поля шахматной доски, посетив каждое из них по одному разу.

В литературе эту задачу обычно называют просто задачей о ходе коня. Особая популярность задачи объясняется тем, что в XVIII и XIX вв. ею занимались многие крупные математики, в том числе великий Леонард Эйлер, посвятивший ей большой мемуар «Решение одного любопытного вопроса, который, кажется, не подчиняется никакому исследованию»21. Хотя задача была известна и до Эйлера, лишь он впервые обратил внимание на ее математическую сущность, поэтому задачу часто связывают с его именем.

Значительно труднее проблема, состоящая не в отыскании определенного маршрута коня, а в нахождении всех маршрутов и подсчете их числа. Увы, эта задача не решена до сих пор, и шансов на успех немного. Известно, правда, что число решений не превосходит C63168 (это число состоит из ста цифр), но больше 30 миллионов. Математик Ф. Миндинг, подошедший к проблеме с алгебраической точки зрения, предложил метод, позволяющий вывести формулу для числа всех решений, однако вычисления, которые следует при этом произвести, практически неосуществимы, и поэтому метод Миндинга представляет лишь теоретический интерес.

Литература, посвященная задаче о ходе коня, весьма обширна. Те или иные методы нахождения маршрутов можно найти в самых разнообразных источниках. Среди них следует выделить книгу Крайчика «Проблема коня», которая, как видно из названия, целиком посвящена этой теме (эта книга входит в упомянутую во введении фундаментальную работу Крайчика). Об алгебраическом подходе, основанном на исследованиях Янишад рассказывается у Окунева, а у Шуберта22 можно найти подробный исторический обзор задачи о ходе коня. Остановимся на некоторых наиболее интересных методах нахождения маршрутов коня.

Рамочный метод Мунка и Коллини. (Коллини - секретарь знаменитого философа Вольтера). Шахматную доску разделим па две части: внутреннюю, состоящую из 16 полей, и внешнюю, имеющую форму рамы и состоящую из 48 полей (рис. 23,а). На полях внутреннего квадрата запишем заглавные буквы А, В, С, D - так, чтобы каждая из них, повторенная четыре раза, образовала квадрат или ромб, по всем сторонам которого может ходить конь. Те же буквы, только строчные, запишем на рамочных полях так, чтобы ходы коня по каждой из букв образовали замкнутые многоугольники, окаймляющие центральный квадрат.

 
Рис. 23. Задача о ходе коня:
а - рамочный метод Мунка и Коллини; б - метод Полиньяка и Роже - деление на четверти

Конь начинает ходить от какого-нибудь рамочного поля, проходит вокруг рамы по выбранной букве, например а, и в 12 ходов исчерпывает эту букву (при этом последнее поле не должно быть угловым). Затем он переходит во внутренний квадрат, но не на букву Л, а на какую-нибудь другую - В, С или D. Пройдя все поля, обозначенные этой буквой, конь снова переходит на раму - на букву, по которой еще не ходил, и вновь обегает вокруг рамы, исчерпывая до конца эту букву, - и т. д., пока не пройдет по всей доске.

Метод Полиньяка и Роже - деление на четверти. Этот метод проще предыдущего, хотя и похож на него. Разделим доску крестом на четыре квадрата (рис. 23,б). В каждом из них расставим буквы а, b, с, d точно так же, как во внутреннем квадрате на рис. 23,а. Конь начинает движение с любой буквы, проходит в выбранном квадрате по всем четырем полям с этой буквой, затем переходит на ту же букву соседнего квадрата, и т. д. Исчерпав все 16 полей с одной буквой, он меняет ее и снова зигзагом обегает доску. После четырех таких кругов все поля будут пройдены (как и в предыдущем методе, «круговые» маневры не должны заканчиваться на угловом поле).

Маршруты и пути коня по доске удобно нумеровать последовательными числами 1, 2, 3 … в соответствии с порядком ходов. В полном маршруте коня начальное поле имеет номер 1, а конечное - 64. Разумеется, изменив направление данного маршрута на противоположное, мы всегда можем начальное поле сделать конечным, и наоборот. Если маршрут замкнут, то поля 1 и 64 связаны ходом коня.

Метод Эйлера и Вандермонда. Этот метод, хотя и не является таким простым и эффектным, как два предыдущих, позволяет, в отличие от них, получать самые разнообразные маршруты коня.

В основе метода лежит возможность замены обратными всех ходов, начиная с поля, связанного ходом коня с конечным.

В качестве примера рассмотрим маршрут на рисунке 24, а. Используя связь поля 31 с конечным полем 64, мы можем получить еще один маршрут. Оставим все числа 1, …, 31 на своих местах, а числа 32, 33, …, 64 заменим соответственно числами 64, 63, …, 32. Иначе говоря, один последовательный путь (от поля 32 до поля 64) мы заменили другим, обратным (от 64 до 32). Теперь поле b4, поменявшее номер 32 на 64, стало конечным. Новый маршрут в старой нумерации полей можно записать так: от 1 до 31, 31 - 64 (один ход - с поля 31 на 64), от 64 до 32.

Указанный прием можно повторять многократно, получая все новые и новые маршруты. В исходном маршруте поле 49 также связано с 64, что дает нам другой производный маршрут: от 1 до 49, 49 - 64, от 64 до 50. В первом из найденных маршрутов поле 32 связано с 43 - и мы можем получить второй производный маршрут: от 1 до 31, 31 - 64, от 64 до 43, 43 - 32, от 32 до 42, и т. д.

 
7
 
24
 
53
 
36
 
5
 
22
 
51
 
34
 
54
 
37
 
6
 
23
 
52
 
35
 
4
 
21
 
25
 
8
 
55
 
58
 
45
 
12
 
33
 
50
 
38
 
59
 
46
 
13
 
48
 
57
 
20
 
3
 
9
 
26
 
15
 
56
 
11
 
44
 
49
 
32
 
60
 
39
 
10
 
47
 
14
 
31
 
2
 
19
 
27
 
16
 
41
 
62
 
29
 
18
 
43
 
64
 
40
 
61
 
28
 
17
 
42
 
63
 
30
 
 
7
 
18
 
47
 
30
 
5
 
16
 
45
 
28
 
48
 
31
 
6
 
17
 
46
 
29
 
4
 
15
 
19
 
8
 
49
 
52
 
39
 
60
 
27
 
44
 
32
 
53
 
40
 
59
 
42
 
51
 
14
 
3
 
9
 
20
 
a
 
50
 
61
 
38
 
43
 
26
 
54
 
33
 
62
 
41
 
58
 
25
 
2
 
13
 
21
 
10
 
35
 
56
 
23
 
12
 
37
 
b
 
34
 
55
 
22
 
11
 
36
 
57
 
24
Рис. 24. Задача о ходе коня. Метод Эйлера и Вандермонда:
а - маршрут, преобразуемый в новые маршруты; б - преобразование «тупикового» маршрута

Если дан некоторый маршрут, то, проявив определенную изобретательность, его можно преобразовать так, чтобы любое наперед заданное поле стало конечным (а эначит, и начальным). Пусть, например, мы хотим сделать конечным поле d4, имеющее номер 56. Свяжем его с полем 64 такими ходами: 64 - 31 - 32 - 57 - 56. Теперь дважды преобразуем исходный маршрут коня (рис. 24,а): 1) от 1 до 31, 31 - 64, от 64 до 32; 2) от 1 до 31, 31 - 64, от 64 до 57, 57 - 32, от 32 до 56. Последний маршрут заканчивается на поле d4, к чему мы и стремились. Описанным методом из незамкнутого маршрута иногда удается получить замкнутый. Так, для превращения маршрута на рис. 24,а в замкнутый достаточно пути: от 11 до 17, от 10 до 1, от 18 до 31, от 64 до 57, от 32 до 45, от 56 до 46 заменить соответственно такими: от 1 до 7, от 8 до 17, от 18 до 31, от 32 до 39, от 40 до 53, от 54 до 64.

Основное достоинство метода Эйлера и Вандермонда заключается в том, что он помогает нам завершить путь коня в тех случаях, когда мы двигались без всякой системы и попали в тупик - дальше идти некуда, а еще остались непройденные поля. Пусть, например, мы уже побывали на 62 полях доски (путь от 1 до 62 на рис. 24,б, а поля а и b не посетили). Здесь поле а связано с полем 10, а поле 62 с полем 9. Это позволяет нам преобразовать путь от 1 до 62 в следующий: от 1 до 9, 9 - 62, от 62 до 10. После перенумерации поле b2 в этом пути меняет номер 10 на 62 и под номером 63 к пути присоединяется поле а. Теперь нам осталось присоединить к пути поле b. В этом нам помогает то обстоятельство, что из двух последовательных полей 57 и 58 первое связано с полем b, а второе - с полем а (имеющим сейчас номер 63). Теперь наш путь (в исходной нумерации) превращается в такой: от 1 до 9, 9 - 62, от 62 до 58, 58 - а, а - 10, 10 - 57. После очередной перенумерации номер 63 теперь получает бывшее поле 57, и, присоединяя к нему поле b, получаем, наконец, искомый маршрут (рис. 24,а; нумерация здесь последовательная - от 1 до 64).

Рассмотренные нами преобразования - далеко не единственные, позволяющие получать из одних маршрутов другие. Упомянем еще преобразования, связанные с поворотами доски и отражениями ее относительно осей симметрии или центра симметрии. Различные свойства маршрутов, основанные на идеях симметрии, исследованы в указанной ранее литературе. Заметим, кстати, что из одного замкнутого маршрута коня можно получить сразу 127 новых: 63 - сдвигом нумерации ходов, а из полученных 64 - еще столько же изменением направления маршрута.

Правило Варнсдорфа. Это довольно эффективное правило заключается в следующем.

1) при обходе доски коня следует всякий раз ставить на поле, из которого он может сделать наименьшее число ходов на еще не пройденные поля; 2) если таких полей несколько, то разрешается выбирать любое из них.

Правило Варнсдорфа предложено более 150 лет назад. Долгое время считалось, что оно действует безукоризненно. Позднее было установлено, что его вторая часть не совсем точна. Если в распоряжении коня имеется несколько возможностей, упомянутых в первой части правила, то не все они являются равноценными. Полную яспость в этот вопрос удалось внести при помощи ЭВМ. Машинный эксперимент, проведенный в Тульском пединституте под руководством А. Есаяна, показал, что с какого бы поля доски конь ни начал свой маршрут, можно так пользоваться второй частью правила Варнсдорфа, что он попадет в тупик раньше, чем посетит все поля доски.

 
 
21
 
34
 
9
 
 
19
 
32
 
7
 
35
 
10
 
 
20
 
33
 
8
 
 
18
 
22
 
 
 
 
 
 
6
 
31
 
11
 
36
 
 
 
 
 
17
 
 
 
23
 
 
 
40
 
 
30
 
5
 
37
 
12
 
25
 
 
27
 
 
 
16
 
24
 
 
2
 
39
 
14
 
 
4
 
29
 
38
 
13
 
26
 
3
 
28
 
15
 
 
 
54
 
21
 
34
 
9
 
58
 
19
 
32
 
7
 
35
 
10
 
55
 
20
 
33
 
8
 
57
 
18
 
22
 
53
 
64
 
59
 
56
 
45
 
6
 
31
 
11
 
36
 
49
 
46
 
63
 
60
 
17
 
44
 
50
 
23
 
52
 
61
 
40
 
47
 
30
 
5
 
37
 
12
 
25
 
48
 
27
 
62
 
43
 
16
 
24
 
51
 
2
 
39
 
14
 
41
 
4
 
29
1
 
38
 
13
 
26
 
3
 
28
 
15
 
42
Рис. 25. Задача о ходе коня. Метод Варнсдорфа

Все же на практике это простое правило дает неплохие результаты. Более того, иногда оно позволяет завершить путь коня даже в том случае, если несколько начальных ходов сделано произвольно. Например, на рис. 25,а конь с a1 уже сделал 40 ходов. В этой доьолыю трудной ситуации, пользуясь сформулированным правилом, кошо удается благополучно закончить маршрут. С поля 40 он мог бы пойти, кроме поля f2 с номером 41, на поля c5, d6, f6 и g3, каждое из которых связано с тремя свободными. Что же касается поля f2, то с пего имеется только два свободных выхода (на h1 и d3), этим и объясняется выбор - число 41 ставится на поле f2 (рис. 25,б).

При следующем ходе возникает вопрос относительно полей h1 и d3. Второе поле связано с четырьмя свободными, а первое - только с одним g3, поэтому число 42 ставится на h1 (рис. 25,б). С поля h1 ход коня определяется однозначно - на поле g3, которое и получает помер 43. С этого поля у коня выбор между полями h5 и f.5, причем каждое И8 них связано с тремя свободными. Сюгласно правилу, можно выбрать любое из них, в нашем случае конь идет на h5 (номер 44). Продвигаясь далее тгем же образом, конь в конце концов попадает на поле 64t.

Строго говоря, по правилу Варнсдорфа обход доски следует начинать с углового поля, так каж в начальный момент именно с него конь может совершись наименьшее число прыжков. Путь коня на рис. 25,а до поля 13 согласуется с указанным правилом, однако уже очередной ход на поле 14 (e2) противоречит ему. С поля 13 у коня имелся выбор И8 пяти возможностей и, как легко вшдеть, «точнее» было пойти им на a2, а не на e2.

Правило Варнсдорфа, как показывает опыт, является достаточно эффективным не только для обычной шахматной доски, но и для других досок, на которых вообще имеется решение эадачи.

 
50
 
11
 
24
 
63
 
14
 
37
 
26
 
35
 
23
 
62
 
51
 
12
 
25
 
34
 
15
 
38
 
10
 
49
 
64
 
21
 
40
 
13
 
36
 
27
 
61
 
22
 
9
 
52
 
33
 
28
 
39
 
16
 
48
 
7
 
60
1
 
20
 
41
 
54
 
29
 
59
 
4
 
45
 
8
 
53
 
32
 
17
 
42
 
6
 
47
 
2
 
57
 
44
 
19
 
30
 
56
 
3
 
58
 
5
 
46
 
31
 
56
 
43
 
18
Рис. 26. Магический маршрут коня

Рис. 27. Раздельный маршрут коня

Многие составители «хода коня» стремились внести в свое занятие, насколько это возможно, эстетический элемент и достигли довольно любопытных результатов. Маршрут на рис. 26, принадлежащий Янишу, примечателен в нескольких отношениях. Он замкнут, образует «полумагический квадрат» (суммы чисел вертикалей и горизонталей равны магическому числу 260, а суммы чисел главных диагоналей отличны от него) и, кроме того, обладает необычной симметрией - при повороте доски на 180° первая половина маршрута (от 1 до 32) превращается во вторую (от 33 до 64).

Еще со времен Эйлера известен так называемый «раздельный ход коня», который заключается в нахождении пути по одной половине доски, его симметричном дублировании и соединении обоих путей вместе (рис. 27). Для половины шахматной доски - доски 8×4 - Крайчик нашел точное число решений. Это позволило ему подсчитать число «раздельных ходов коня» на доске 8×8, которое и дает нижнюю границу для числа всех решений задачи, указанную в начале этой главы.

Если говорить о графиках маршрутов коня, то здесь придумано множество необычных решений, изображающих различные предметы, буквы или знаки (изпестен даже график, посвященный Наполеону!). Два достопримечательных примера такого рода приведены на рис. 28. График первого маршрута (он является замкнутым) напоминает вазу, а график второго представляет собой цветок, части которого расположены в высшей степени симметрично.

 
Рис. 28. Ваза и цветок

Наиболее интересное обобщение эадачи о коне возникает при рассмотрении произвольной доски m×n.

При каких значениях тип существует маршрут коня по всем полям доски m×n?

Если одна из сторон доски меньше 3, то, очевидно, маршрута нет (исключение составляет вырожденный случай - доска 1×1, для «обхода» которой достаточно просто поставить коня на доску). Если одна сторона доски равна 3, то другая должна быть либо 4, либо не меньше 7. Если обе стороны больше 3, то обходной маршрут коня существует на всех досках, кроме 4×4. Итак, конь может обойти все поля доски m×n при следующих уелогиях: m, n ≠ 1, 2; если m = 3, то n = 4 или n > 6; соответственно, если n = 3, то m = 4 или m > 6; m = 4, n ≥ 5; n = 4, m ≥ 5.

Для существования замкнутого маршрута прежде всего необходимо, чтобы доска была четной. Как показано в предыдущей главе, если одна сторона равна 4, то замкнутого маршрута нет. Если обе стороны четной доски больше 4, то замкнутый маршрут всегда существует. Наконец, если одна сторона равна 3, то для существования замкнутого маршрута другая должна быть не меньше 10. Как мы видим, наименьшая (по площади) прямоугольная доска, которую может обойти конь, имеет размеры 3×4, а наименьшие прямоугольные доски с замкнутыми маршрутами имеют размеры 5×6 и 3×10.

Для обычной доски 8×8, а также для всех досок с меньшими сторонами, приведенные выше результаты устанавливаются непосредственно. Если же хотя бы одна сторона доски больше 8 (а другая больше 2), то ее легко разбить на доски со сторонами, меньшими 8, которые допускают маршруты коня. Из этих маршрутов и удается «собрать» маршрут на исходной доске. Аналогичная идея используется и для доказательства существования замкнутых маршрутов на соответствующих четных досках.

Остановимся несколько подробнее на квадратных досках n×n. На досках 2×2 и 3×3 маршрута нет - в первом случае вообще никакие два поля не связаны друг с другом, а во втором - центральное поле не связано с крайними.

Покажем, что нет маршрута и на доске 4×4. Подсчитаем, сколько ходов имеется в нашем распоряжении. Центральных полей здесь всего четыре, и они нам дают максимум восемь ходов (включая движение через углы доски). Остальные ходы образуют стороны квадратов a2 - b4 - d3 - c1 и a3 - c4 - d2 - b1. Поскольку квадраты замкнуты, то из четырех ходов каждого в маршруте может быть использовано не более трех. Итак, всего имеем 8 + 3 + 3 = 14 ходов. Однако для того, чтобы обойти все поля доски 4×4, требуется 15 ходов - противоречие!

на досках (4k + 1)×(4k + 1);

на досках 4k×4k;

на досках (4k + 2)×(4k + 2);

на доске 7×7;

общий метод нахождения маршрутов коня на доске n×n при n > 14.
Рис. 29. Маршруты коня на квадратных досках

На рис. 29,а предложен общий метод обхода досок n×n, где n = 4k + 1 (n = 1, 5, 9 и т. д.). На рис. 29,б дан метод обхода досок для n = 4k + 2 (n = 6, 10, 14 и т. д.). Аналогичным образом (рис. 29,в) обходятся доски при n = 4k (n = 8, 12, 16 и т. д.). На рисунках 29, г и 29, д (внутренний квадрат) указаны маршруты - на досках 7×7 и 11×11. Итак, мы имеем, в частности, маршруты коня на всех досках n×n при n < 15 (n ≠ 2, 3, 4).

Заметим, что маршруты на рис. 29,б и 29,в придумал недавно ленинградский школьник Н. Нецветаев. Он же предложил интересный метод нахождения маршрутов на всех досках n×n при n ≥ 15. Этот метод опирается на то, что при любом n ≥ 14 существует замкнутый обход полосы ширины 3, окаймляющей доску (n - 6)×(n - 6). На рис. 29,д изображен обход такой полосы для доски 17×17. Чтобы получить замкнутый обход полосы для любой доски n×n при n ≥ 14, надо взять такой же обход полосы, но увеличить число «треугольников» между парами полей, аналогичными парам c6 и с9, f15 и i15, о12 и о9, l13 и i3 (см. рис. 29,д); крайний случай получается при совпадении таких пар, внутренний квадрат при этом имеет размеры 8×8. Если мы имеем маршрут коня по внутренней доске, то для получения маршрута по всей доске n×n нужно выкинуть ходы, помеченные на рис. 29,д сплошной линиемг, и добавить «пунктирные» ходы. При полном обходе, как мы видим, конь сначала идет по внутреннему квадрату, «отвлекается» на нашу полосу и, возвращаясь в квадрат, заканчивает путешествие.

Теперь очевидно, что нахождение маршрута на произвольной доске n×n (n ≥ 15) сводится к нахождению маршрута на доске (n - 6)×(n - 6). В конце концов мы придем к доске n×n, где 9 ≤ n ≤ 14. Поскольку для всех таких досок маршруты уже найдены, то наша задача решена полностью.

Нетрудно видеть, что прием Нецветаева дает возможность получить и замкнутые маршруты на всех четных квадратных досках (n ≥ 6). Заметим также, что обходы на рис. 29,а - 29,в не дают общего решения, так как упущен случай n = 4k + 3 (кстати, все получающиеся на рисунках маршруты для n ≠ 4k + 3 не замкнуты).

Еще один интересный вопрос: а нельзя ли для нахождения маршрутов в общем случае использовать полосы шириной не в три, а в два поля (как на рис. 29,а)? Увы, ответ здесь отрицательный. Доказано, что всю полосу шириной в два поля можно обойти конем лишь в том случае, если она окаймляет доску (4k + 1)×(4k + 1).

С точки зрения теории графов задача о ходе коня является частным случаем важной проблемы - нахождения гамильтонова пути в графе, т. е. пути, проходящего через все его вершины по одному разу. Этим и объясняется популярность задачи о ходе коня в литературе по теории графов (при этом рассматривается «граф коня»).

Задача нахождения гамильтонова пути в графе является, в свою очередь, частным случаем так называемой задачи коммивояжера, к которой сводятся самые разнообразные задачи одного из важнейших разделов прикладной математики - исследования операций. Требуется найти кратчайший путь коммивояжера, по которому он должен объехать ряд городов (связанных между собой некоторым числом дорог), посетив каждый из них по одвому разу. Конечно, прежде всего здесь возникает вопрос, может ли коммивояжер вообще объехать все города с однократным посещением каждого из них. Таким образом, можно считать, что настоящая глава посвящена путешествиям по шахматной доске «коня-коммивояжера».

В следующей задаче, не совсем похожей на предыдущие, мы не различаем двух ходов коня, связывающих одну и ту же пару полей, например, Кg1-f3 и Кf3-g1.

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

Убедимся, что эта задача не имеет решения. Поскольку ходы в маршруте копя не должны повторяться, то, попадая на некоторое поле одним ходом, мы должны покинуть его другим. Таким образом, каждое поле доски (кроме, быть может, начального и конечного полей в искомом маршруте) должно быть связано с другими полями четным числом ходов. Однако на доске имеется восемь полей (a2, b1 и симметричные им), с которых у коня имеется по три хода на другие поля доски, - и, значит, указанное условие не выполняется!

Выше мы уже говорили о гамильтоновом пути в графе, проходящем по одному разу через все его вершины. Путь, который проходит через все ребра графа, называется эйлеровым. Таким образом, мы фактически показали, что в графе коня гамильтонов путь существует, а эйлеров - нет.

Ниже будут приведены маршруты по всем полям доски и для других фигур, причем эти маршруты отыскать значительно проще, чем для коня. Существование этих маршрутов означает, что в графах всех фигур имеются гамильтоновы пути. Что же касается эйлерова пути, то им обладает только граф ладьи.

Касаясь обобщений задачи о коне, заметим, что множество интересных проблем возникает при рассмотрении «обобщенного коня» (а, b). Важно отметить, что если числа а и b имеют одинаковую четность, то коль может попасть только на поля одного цвета. Те или иные маршруты коня (а, b) на досках m×n при различных значениях а, b, m, n можно найти у Крайчика.

В следующих двух задачах речь идет о маршрутах коня на объемной (пространственной) доске. Эта доска представляет собой параллелепипед m×n×k (в частности, куб n×n×n), единичные кубики которого образуют «поля», лежащие в одном слое параллелепипеда и отстоящие в этом слое соответственно на одно и два «поля».

Обойти конем все поля объемной шахматной доски 4×4×4, посетив каждое по одному разу.

Указанная доска, как и обычная, содержит 64 поля, но только объемных. Обход этой доски шахматным конем фактически состоит в том, чтобы занумеровать ее поля-кубики последовательными числами от 1 до 64 так, чтобы каждые два «поля» с соседними номерами были связаны ходом коня. Для решения задачи объемную доску удобно представить в виде четырех горизонтальных слоев 4×4×1, лежащих один над другим. На рис. 30 поверхности этих слоев занумерованы числами 1, 2, 3, 4. Нетрудно проверить, что, двигаясь в указанной последовательности, мы обойдем все поля доски 4×4×4.

 
57
 
30
 
47
 
36
 
48
 
33
 
58
 
31
 
29
 
60
 
35
 
46
 
34
 
45
 
32
 
59
 
 
42
 
37
 
56
 
51
 
55
 
52
 
43
 
40
 
38
 
41
 
50
 
53
 
49
 
54
 
39
 
44
 
 
27
 
62
 
15
 
2
 
14
 
26
 
63
 
61
 
28
 
3
 
16
 
4
 
13
 
64
 
25
 
 
10
 
7
 
22
 
17
 
21
 
18
 
9
 
6
 
8
 
11
 
20
 
23
 
19
 
24
 
5
 
12
Рис. 30. Обход конем объемной доски 4×4×4

Обойти конем поверхность объемной доски 8×8×8, посетив каждое ее поле по одному разу (поля плоские).

В данной задаче хотя и фигурирует объемная доска, конь перемещается по шести обычным двумерным доскам 8×8, образующим грани куба. Трудность задачи состоит лишь в «сопряжении» всех шести маршрутов коня. Удобно воспользоваться разверткой куба на рис. 31, где решение изображено графически. Как мы видим, маршрут является замкнутым, т. е. конь может начать и кончить свое путешествие на любом из 64×6 = 384 полей поверхности нашей доски.

В заключение рассказа о ходе коня рассмотрим задачу на плоской, но бесконечной шахматной доске.

На бесконечной шахматной доске расставлены пешки через три поля на четвертом, (например, b1, f1, b5, f5 и т. д.). Может ли конь обойти все свободные поля такой доски, побывав на каждом из них по одному разу?

Рис. 31. Обход конем поверхности объемной доски 8×8×8

Требуемого маршрута не существует. Для таго чтобы это показать, рассмотрим два квадрата: 196×196 и концептрично окаймляющий его 200×200. Ясно, что при указанной расстановке пешек-все они стоят на полях одного цвета, в нашем примере - белого. При этом с каждого из 196²/2 = 19208 черных полей внутреннего квадрата при обходе доски конь попадает на одно из 200²/2 - 2500 = 17500 свободных белых полей окаймляющего квадрата. Так как 17500 < 19208, то на некоторые белые поля конь попадает более одного раза - противоречие.



21. В «Commentationes arihm. coli.», S, -Pb., t. I, 1849,

22. Г. Шуберт. Математические развлечения и игры. Одесса. 1923.

<<< |1|…|4|5|6|7|8|9|10|11|12|…|19| >>>
Комментарии: 0