“Шахматы и математика” — 2 главная > Е. Гик: “Шахматы и математика”

Конь-хамелеон

Совсем не обязательно быть шахматистом, чтобы знать, какая шахматная фигура самая удивительная. Конечно, это конь! Не случайно выражение “ход конем” стало крылатым и прочно вошло в наш быт. А один из самых остроумных гроссмейстеров, С. Тартаковер, прямо считал, что “вся шахматная партия — это один замаскированный ход конем”. Поэтому, переходя к математическим задачам с участием фигур, мы прежде всего остановимся на задачах о коне.

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

Может ли конь с поля a1 добраться до h8, побывав на каждом поле доски ровно один раз?

Не может. Исходное поле a1 — черное, и, значит, на каждом нечетном ходу конь попадает на белое поле. Однако число 63 (именно на 63-м ходу конь прибывает в противоположный угол доски) нечетно, а поле h8 — черное.

Все оказалось довольно просто, но любопытно, что за доской шахматист иногда сталкивается с подобными вопросами. Рассмотрим, например, позицию, изображенную на рис. 15. Белым здесь удается добиться ничьей единственным путем — 1. Крc1! Теперь их король будет переходить с c1 на c2 и обратно, занимая каждый раз поле того цвета, что и конь, и не выпуская черного короля из заточения. В случае 1. Крc2 конь попадал на d3 при короле на c2, и пешка проходила в ферзи. Аналогия между этим шахматным примером и предыдущей задачей очевидна.

Рис. 15
Рис. 15. Ничья.

Решим один изящный этюд, в котором требуется перехитрить коня-хамелеона (рис. 16). Простой анализ позиции показывает, что фигуры обеих сторон в правом нижнем углу не могут двигаться, т.е., выражаясь шахматным языком, находятся во взаимном цугцванге. Например, если ферзь уйдет с h3, то либо будет потеряна ладья, либо двинется черный слон с угрозой f2-f1Ф. С другой стороны, любой ход слона f1 и коня h1 в начальном положении приводит к немедленной гибели черных, и, значит, они могут ходить только конем h8. Итак, белый король должен подойти к полю h8 и забрать этого коня. Идти он может только по черным полям, так как на белом поле получит шах слоном f1 с превращением пешки “f”.

Рис. 16
Рис. 16. В. Чеховер. Выигрыш.

Прямолинейное движение короля к угловому полю не дает результата: 1. Крb2 Кf7 2. КреЗ Кh8 3. Крd4 Кf7 (прикрывая поле e5) 4. КреЗ Кh8 5. Крf4 (на 5. Фh4 Сd3 6. Л : h1+ черные играют не 6... ghФ? 7. Ф : f2ґ, а 6... ghК!) 5.... Кf7! (охраняя поля e5 и g5) 6. КреЗ Кh8 7. Крd4 Кf7 8. Крc5 Кh8 9. Крd6 Кg6! Мы видим, что конь держит все поля вторжения белого короля. Для того чтобы все-таки прорваться к полю h8 белому королю нужно изменить соответствие цветов между ним и черным конем. Но этого можно достичь, лишь встав один раз королем на белое поле. Искомым является поле a8 — единственное недоступное для черного слона.

После проведенного анализа решение находится почти автоматически: 1-6. Крb2-сЗ-d4-c5-b6-a7 (черный конь в это время переходит с h8 на g6 и обратно) 7. Крa8! Кg6 8. Крb8 Кh8 9. Крc7 Кf7! Неожиданно черный конь опять создал барьер для короля, но это лишь временное препятствие. 10-13. Крb6-c5-d4-e5 Кg6+ 14. Крf6 Кh8 15. Крg7 Кg6 16. h8Ф (после 16. Кр : g6 Сd3+ вся работа белых пошла бы насмарку) 16... К : h8 17. Кр : h8 Кg3 18. Ф : g3 Сd3 19. Ф : g2ґ. Любопытно, что в решении этюда содержится любопытный геометрический мотив: белый король, прежде чем добиться цели, побывал в трех углах шахматной доски!

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

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

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

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

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

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

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

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

Литература, посвященная задаче о ходе коня, весьма обширна. Известно много методов для нахождения маршрутов коня, которые носят имя первооткрывателей — метод Эйлера и Вандермонда, рамочный метод Мунка и Коллини, метод деления на четверти Полиньяка и Роже и др. Вот самое простое правило построения маршрутов коня.

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

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

Однако на практике правило Варнсдорфа действует весьма эффективно, и даже при вольном использовании его второй части вероятность заблудиться невелика. Иногда завершить маршрут коня удается даже в том случае, если его начальный путь сделан без всякой системы. На рис. 17, а конь, начав путешествие с поля a1, уже прошел 40 ходов. В этой трудной ситуации, пользуясь правилом Варнсдорфа, конь благополучно заканчивает маршрут. С поля 40 он мог бы пойти, кроме поля f2, на поля c5, d6, f3 и g3. Но каждое из этих полей связано с тремя свободными, а поле f2 — с двумя (hi и d3), этим и объясняется выбор, — число 41 ставится на поле f2 (см. рис. 17,б). Дальше у коня выбор между полями h1 и d3. Второе поле связано с четырьмя свободными, а первое — только с одним, и число 42 ставится на h1. С этого поля ход определяется однозначно — на поле g3, которое и получает номер 43. Теперь у коня имеется выбор между полями h5 и f5, причем каждое из них связано с тремя свободными. Согласно правилу, можно выбрать любое из них, в нашем случае конь идет на h5 (номер 44). Продвигаясь далее таким же образом, конь в конце концов обойдет всю доску и последним, 63-м ходом, закончит маршрут на поле c6, которое получит номер 64 (см. рис. 17,б).

Рис. 17
Рис. 17. Правило Варнсдорфа.

Строго говоря, по правилу Варнсдорфа обход доски следует начинать с углового поля, так как в начальный момент именно с него конь может совершить наименьшее число прыжков. В нашем примере первые 13 ходов коня, до поля c1, согласовывались с правилом, однако очередной ход на поле e2 нарушил его (см. рис. 17,а). На поле c1 конь имел выбор из пяти возможностей и, как легко видеть, "точнее" было пойти на a2, а не на e2. На 21-м ходу конь снова сыграл неправильно — пошел на еЗ, а не на f2. Наконец, неточен был и последний, 40-й ход-полю e4 следовало предпочесть поле f3. Впрочем, как мы видели, в конце концов коню удалось выбраться из щекотливого положения.

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

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

Рис. 18
Рис. 18. Полумагический маршрут коня.

Со времен Эйлера известен так называемый "раздельный ход коня"; который заключается в нахождении пути по одной половине доски, его симметричном дублировании и соединении обеих путей вместе (рис. 19). Для половины шахматной доски — доски 8ґ4 — найдено точное число маршрутов коня. Это позволило подсчитать число "раздельных ходов коня" на доске 8×8, которое и дает нижнюю границу для числа всех решений задачи, указанную в начале главы.

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

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

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

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

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

Если одна из сторон доски меньше трех, то, очевидно, маршрута нет (исключение составляет вырожденный случай — доска 1ґ1, для обхода которой достаточно просто поставить коня на доску). Если одна сторона доски равна трем, то другая должна либо равняться четырем, либо быть не меньше семи. Если обе стороны больше трех, то маршрут коня существует на всех досках, исключая доску 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; наконец, m, n і 5.

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

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

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

Доказать, что ни при каком значении m на доске mґ4 нет замкнутого маршрута коня.

Докажем это от противного. Предположим, что при некотором m замкнутый маршрут коня на доске mґ4 существует. Поля, расположенные на верхней и нижней горизонталях доски, назовем крайними, остальные — средними. Так как с крайних полей конь может попасть только на средние, которых имеется 2m, то из 4m ходов, образующих маршрут, 2m сделаны с крайних на средние. Тогда оставшиеся 2m ходов конь совершил со средних на крайние. Поскольку на каждом ходу конь-хамелеон меняет цвет поля, все поля крайних горизонталей должны быть окрашены в один цвет, а средних — в другой. Противоречие.

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

Доказательство существования маршрутов коня (ототкрытых или замкнутых) на указанных досках проводится следующим образом. Для ряда “основных” досок маршруты строятся непосредственно. Далее показывается, как произвольную доску разбить на ряд “основных”, для которых маршруты уже построены. Из этих “микромаршрутов” и составляется маршрут коня на данной доске. В известном нам доказательстве приходится использовать слишком много — 37 (!) “основных” досок, и поэтому, в целях экономии места, полное рассмотрение вопроса о маршрутах коня на прямоугольных досках мы опускаем. Заметим лишь, что ни. одна из сторон “основной” доски не превосходит девяти. Эффектный метод построения маршрута коня на произвольной квадратной доске nґn (n > 4) можно найти в книге “Математика на шахматной доске”.

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

Каждой шахматной фигуре можно поставить в соответствие граф, вершины которого расположены в центрах всех полей доски, и пары вершин соединены ребрами, если между соответствующими полями возможен ход данной фигуры. Каждому пути фигуры по доске соответствует путь в ее графе, а маршруту — маршрут в графе.

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

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

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

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

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

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

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

Обобщение задачи о ходе коня связано не только, с рассмотрением досок различных размеров, но и с изменением самого хода коня. Обычный конь перемещается на одно поле вдоль одной линии (вертикали или горизонтали) и на два поля вдоль другой, и поэтому его можно назвать конем (1, 2). Очевидно, можно ввести в обиход и коня (а, b), совершающего прыжок на a полей в одном направлении и на b в другом. Теперь можно искать маршруты коня (а, b) на доске mґn при различных значениях a, b, m, n.

До сих пор мы рассматривали лишь доски конечных размеров, однако много интересных задач возникает и на бесконечной доске.

При каких a и b конь (a, b) с произвольного поля бесконечной доски может попасть на любое другое поде?

Достаточно выяснить, при каких a и b конь может с данного поля доски перейти на соседнее по вертикали или горизонтали. Решение задачи требует использования аппарата “теории чисел”. Приведем сразу ответ: числа a и b должны иметь разную четность и быть взаимно простыми. Очевидно, для обычного коня (1, 2) эти условия выполняются, а, скажем, конь (1, 3) в состоянии посетить лишь поля одного цвета (числа 1 и 3 нечетны).

На скольких полях бесконечной доски может оказаться конь за p ходов, начиная свой маршрут с данного поля?

Обозначим искомое число полей через N(p). Легко проверить, что N(0)=1, N(1)=8, N(2)=33. За три хода (p=3) конь с данного черного поля может попасть на все белые поля восьмиугольника, имеющего центр в исходном поле. Методом математической индукции доказывается, что при любом p і 3 конь может оказаться на всех одноцветных полях соответствующего восьмиугольника (при четных p — того же цвета, что и начальное поле; при нечетных p — противоположного). Подсчитав число полей в таком восьмиугольнике, получим N(p)=17p2+4p+1 (p і 3).

Для остальных шахматных фигур последняя задача не представляет интереса. Король за p ходов может попасть на любое поле квадрата (2p+1)ґ(2p+1) с центром в данном поле. Дальнобойные фигуры уже за один ход могут оказаться на бесконечном числе полей за два хода слон попадает на все одноцветные поля бесконечной доски, а ферзь и ладья — на любое ее поле.

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

Рис. 21
Рис. 21. Пешки мешают коню.

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

Группу коней, размещенных на бесконечной доске назовем эскадроном, если они могут сделать любо число ходов, не оставляя ни одного коня без защиты. Эскадрон — активный, если при таком “дружном” перемещении он может занять одним из своих коней любое поле доски. Интересна следующая задача.

Из какого наименьшего числа коней можно создать активный эскадрон?

Ясно, что один или два коня вообще не образую эскадрон, а эскадрон из трех или четырех коней перемещается лишь на конечной территории, т.е. не является активным. Минимальный активный эскадрон состоит из пяти коней. На рис. 22 показано, как перевести пятерку коней из положения 1 в положения 5 и 11. Положения 1 и 11 отличаются друг от друга сдвигом по вертикали на одно поле. Отсюда следует, что в вертикальном направлении можно последовательно осуществить бесконечное число переходов всей пятерки коней. Положения 1 и 5 отличаются тем, что одно из них сдвинуто относительно другого на одно поле по вертикали на одно по горизонтали (а также перевернуто на 180°). Таким образом, эскадрон, занимающий положение 1, может попасть на любое поле доски, и, значит, является активным. Заметим, что для остальных фигур задача об активном эскадроне решается намного проще.

Рис. 22
Рис. 22. Активный эскадрон коней.

В заключение главы рассмотрим еще две задачи о путешествии коня по доске.

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

"Трава не растет там, где ступил мой конь!" — похвалялся вождь гуннов Аттила, намекая, что предводительствуемые им полчища уничтожают все живое на своем пути.

На рис. 23, а конь Аттилы стоит на поле g4, неприятельский король — на b3, а горящие поля заштрихованы. На рис. 23,б изображен граф коня для рассматриваемой задачи. Его вершины расположены в центрах полей, доступных коню, а пара вершин соединена ребром в том случае, если между соответствующими полями возможен ход коня. В результате задача свелась к нахождению такого пути в графе, который не содержит ни одной вершины более одного раза и, кроме того, проходит через обе заданные (на рис. 23,б они обведены кружками).

Рис. 23
Рис. 23. Задача о коне Аттилы.

Методы решения подобных задач, называемых лабиринтными, приводятся в различных книгах по теории графов. Для коня Аттилы искомый путь на данной доске нетрудно найти и непосредственно, он состоит из следующих восемнадцати ходов: Kg4-f6-e8-g7-e6-f8-g6-e7-c6-a5 : b3-d2-b1-a3-b5-d6-f7-h6-g4 (можно воспользоваться и обратным путем). Для достижения цели коню Аттилы пришлое побывать на 18 полях из 35, не “сожженных” в начал сражения.

Несамопересекающимся путем (маршрутом) фигура мы называем такой путь, график которого не имеет самопересечений (и касаний).

На шахматной доске найти самый длинный (по числу ходов) несамопересекающийся путь коня.

Искомый путь коня на доске 8ґ8 состоит из 35 ходов (рис. 24,а). Любопытно, что этот несамопересекающийся путь почти одновременно и независимо друг от друга нашли сразу две ЭВМ — американская и западногерманская.

Рис. 24
Рис. 24. Несамопересекающиеся пути коня.

Задача была исследована для всех досок mґn при m, n Ј 9. Ни один человек из решавших задачу не сумел найти на доске 6×6 путь, содержащий более 16 ходов. Рекорд установила машина! Предложенный ею 17-ходовый путь без самопересечений изображен на рис. 24,б.

| Оглавление |