Шахматы и математика

DjVu

      ПРЕДИСЛОВИЕ
      У математики и шахмат много родственного. Выдающийся математик Г. Харди, проводя параллель между этими двумя видами человеческой деятельности, в своей статье «Исповедь математика» заметил, что решение проблем шахматной игры есть не что иное, как математическое упражнение, а игра в шахматы это как бы насвистывание математических мелодий.
      Конечно, не все студенты мехмата поглощены серьезным изучением дебютных вариантов (совмещать занятия математикой и шахматами вообще очень сложно), но, пожалуй, именно на этом факультете труднее всего встретить студента, не умеющего играть в шахматы!
      Среди крупных ученых, специалистов в области точных наук, известно немало сильных шахматистов, например, математик академик А. А. Марков, механик академик А. Ю. Ишлинский, физик академик, лауреат Нобелевской премии П. Л. Капица.
      В то же время многие гроссмейстеры имеют математическое или близкое к нему образование. Склонность к занятиям математикой проявлялась даже у чемпионов мира по шахматам. Интересовался ею первый шахматный король В. Стейниц. Профессиональным математиком был его преемник доктор Эм. Ласкер. Доктор М. Эйве, пятый чемпион мира, возглавлял один, из вычислительных центров в Голландии. Первый советский чемпион мира М. Ботвинник, доктор технических наук и специалист в области электротехники, в последние годы все силы отдает разработке алгоритма игры в шахматы и, по существу, переквалифицировался в математика-прикладника. Яркими математическими спо-собностями в юные годы обладал М. Таль. Нынешний чемпион мира А. Карпов с золотой медалью закончил математическую школу, был победителем ряда математических олимпиад. После окончания школы он поступил на механико-математический факультет МГУ, но затем ради шахмат «пожертвовал» математикой...
      Сопоставление математики и шахмат, как сфер человеческой деятельности, очень интересно и заслуживает специального изучения. Однако эта тема лежит несколько в стороне от содержания данной книги.
      Шахматная доска, фигуры и сама игра часто используются для иллюстрации разнообразных математических понятий и задач. Шахматные примеры и термины можно встретить в литературе по кибернетике, теории игр, вычислительной математике, исследованию операций, теории графов, теории чисел и комбинаторике. Важное место занимают шахматы в развитии современных методов программирования на электронных вычислительных машинах (ЭВМ).
      Еще одна точка соприкосновения математики и шахмат — это один из популярных жанров занимательной математики, к которому относятся математические игры, задачи и развлечения на шахматной доске. Мы называем этот жанр шахматной математикой. Почти в каждом сборнике олимпиадных математических задач или книге головоломок и математических досугов можно найти красивые и остроумные задачи с участием шахматной доски и фигур. Многие из них имеют интересную историю, привлекали к себе внимание известных ученых. Например, задачей о ходе коня занимался великий математик Леонард Эйлер, а задачей о восьми ферзях — другой великий математик Карл Гаусс (обе задачи обсуждаются в книге).
      Интересно, что «шахматные» увлечения Эйлера относятся к 18-му столетию, а Гаусса — к середине 19-го. С тех пор в течение целого века крупные математики не занимались шахматами (речь идет о научном подходе к игре). Ситуация резко изменилась в середине нынешнего столетия в связи с бурным развитием кибернетики и вычислительной техники. Шахматы — одна из наиболее удобных моделей, используемых математиками при разработке современных методов программирования на ЭВМ. К шахматам постоянно обращались
      в своих работах такие выдающиеся ученые, как Винер, Тьюринг и Шеннон.
      Наибольшее внимание в данной книге уделено шахматной математике (первые десять глав). Рассматриваются многие типы математических задач и головоломок на шахматной доске: о силе фигур, об их маршрутах, расстановках и перестановках, о разрезании и покрытии доски. Устанавливаются различные шахматноматематические рекорды, описываются необычные свой* ст.а геометрии шахматной доски.
      Следующие* две главы посвящены занимательным, математическим и «сказочным» играм на шахматной доске. Описываются игры на необычных досках, с необычными правилами и с необычными фигурами. В главах 13, 14 дано математическое освещение двух шахматных вопросов: составление турнирных расписаний и вычисление рейтингов шахматистов (коэффициентов, характеризующих их силу). Наконец, в заключительной главе рассказывается о шахматных достижениях ЭВМ — в практической игре и в анализе окончаний.
      По существу, над этой книгой автор работал более десяти лет, — начиная с 1971 года, когда в журнале «Квант» были впервые опубликованы его «Шахматноматематические заметки». У издания «Шахматы и математика» было два «промежуточных» этапа — в 1976 году вышла моя книга «Математика иа шахматной доске», а в 1981 году «Шахматный калейдоскоп» (в соавторстве с А. Карповым). После их появления пришло много писем, в которых читатели уточняли и улучшали предложенные решения задач, предлагали свои собственные шахматно-математические игры, задачи, головоломки. Некоторые из этих предложений нашли отражение в данной книге. Вот один пример. Известно было, что перестановку коней в третьем зигзаге Шинкмана (см. стр. 89) можно осуществить в 107 ходов. Читатели прислали более короткие решения, и в результате рекорд был доведен до 45 ходов. Конечно, при работе над книгой были учтены также материалы на шахматно-математическую тему, появившиеся в печати в последние годы, в частности, в журнале «Квант».
      Охватить весь жанр шахматной математики в одной небольшой книжке невозможно. Если бы мы привели исчерпывающие решения только тех задач, которые содержатся в книге, то ее объем увеличился бы в несколько раз. Вот почему для многих задач даны лишь краткие решения, указания или ответы. Полные решения приводятся в тех случаях, когда они не требуют громоздких выкладок и, кроме того, не лишены, на вкус автора, некоторого изящества.
      Литература по шахматной математике совершенно необозрима. В список можно было бы включить многие шахматные издания, монографии пб перечисленным выше разделам математической науки, книги по занимательной математике, научно-популярные статьи и работы в серьезных математических журналах. Однако поскольку это не диссертация, решено было не злоупотреблять ссылками на литературу. В конце книги приведен список из десяти названий.
     
      ГЛАВА 1
      МАТЕМАТИКА ШАХМАТНОЙ ДОСКИ
      В математических задачах и головоломках на шахматной доске дело, как правило, не обходится без участия фигур. Однако доска сама по себе также представляет достаточно интересный математический объект. Поэтому рассказ о шахматной математике мы начнем с задач о шахматной доске, не расставляя пока на ней фигур.
      Прежде всего напомним одну старинную легенду о происхождении шахмат, связанную с арифметическим расчетом на доске.
      Когда индийский царь впервые познакомился с шахматами, ?н был восхищен их своеобразием и обилием красивых комбинаций. Узнав, что мудрец, который изобрел игру, является его подданным, царь позвал его, чтобы лично наградить за гениальную выдумку. Властелин пообещал выполнить любую просьбу мудреца и был удивлен его скромностью, когда тот пожелал получить в награду пшеничные зерна. На первое поле шахматной доски — одно зерно, на второе — два, и так далее, на каждое последующее вдвое больше зерен, чем на предыдущее. Царь приказал побыстрее выдать изобретателю шахмат его ничтожную награду. Однако на следующий день придворные математики сообщили своему повелителю, что не в состоянии исполнить желание хитроумного мудреца. Оказалось, что для этого не хватит пшеницы, хранящейся не только в амбарах всего царства, но и во всех амбарах мира. Мудрец скромно потребовал ... зёрен. Это число записывается двадцатью цифрами и является фантастически большим. Подсчет показывает, что амбар для хранения необходимого зерна с площадью основания 80 м должен простираться от Земли до Солнца. Конечно, связь с математикой здесь несколько условна, однако неожиданная развязка истории наглядно иллюстрирует грандиозные математические возможности, скрывающиеся в шахматной игре.
      Раз уж речь зашла о происхождении шахйат, то уместно привести одну гипотезу, использующую некоторые математические свойства доски. Согласно этой гипотезе шахматы произошли из так -называемых магических квадратов.
      Магический квадрат порядка п представляет собой квадратную таблицу пХп, заполненную целыми числами от 1 до ns и обладающую следующим свойством: сумма чисел каждой строки, каждого столбца, а также двух главных диагоналей одна и та же. Для магических квадратов порядка 8 она равна 260 (рис. 1). Закономерность расположения чисел в магических квадратах придает им волшебную силу искусства. Недаром выдающийся немецкий художник А. Дюрер был настолько очарован этими математическими объектами, что воспроизвел магический квадрат в своей знаменитой гравюре «Меланхолия».
      Рассмотрим одну из старинных дебютных табий (начальных расположений фигур) под названием альмуджаннах. Она получается из современной расстановки при помощи следующих симметричных ходов белых и черных: ...
      Подсчитав сумму чисел, стоящих на восьми полях — ..., участвующих в первых двух ходах, мы неожиданно получим магическое число 260. Тот же результат даст и каждая последующая пара приведенных ходов. Подобные примеры (число их можно увеличить) и позволяют высказать гипотезу о связи магических квадратов с шахматами. А исчезновение всех следов этой связи можно объяснить тем, что в далекую эпоху суеверий и мистики древние индусы и арабы приписывали числовым сочетаниям магических квадратов таинственные свойства, и эти квадраты тщательно скрывались. Может быть, поэтому и была выдумана легенда о мудреце, который изобрел шахматы.
      Среди математических задач и головоломок о шахматной доске наиболее популярны задачи на разрезание доски. Первая из них также связана с легендой.
      Один восточный властелин был таким искусным игр жом, что за всю жизнь потерпел всего четыре поражения. В честь своих победителей, четырех мудрецов, он приказал вставить в его шахматную доску четыре алмаза — на те поля, на которых был заматован его король (см. рис. 2, где вместо алмазов изображены кони).
      После смерти властелина его сын, слабый игрок и жестокий деспот, решил отомстить мудрецам, обыгравшим его отца. Он велел разделить им шахматную доску с алмазами на четыре одинаковые по форме части так, чтобы каждая заключала в себе по одному алмазу. Хотя мудрецы выполнили требование нового властелина, он все равно лишил их жизни, причем, как гласит легенда, для казни каждого мудреца использовал его часть доски с алмазом.
      Эта задача о разрезании доски часто встречается в занимательной литературе.
      Разрезать доску на четыре одинаковые части (совпадающие при наложении) так, чтобы на каждой из них оказалось по одному коню. Предполагается, что разрезы проходят только по границам между вертикалями и горизонталями доски.
      Одно из решений задачи представлено на рис. 2. Располагая четырех коней на различных полях доски, мы получаем множество задач о разрезании. Интерес в них представляет не только нахождение одного необходимого разреза, но и подсчет числа всех способов разрезать доску на четыре одинаковые части, содержащие по одному коню. Установлено, что наибольшее число решений — 800 — задача имеет при расположении коней в углах доски.
      Следующую задачу на разрезание обычно связывают с именем выдающегося шахматного композитора и мастера головоломок С. Лойда.
      На какое максимальное число частей можно разрезать шахматную доску, если считать разными части, отличающиеся своей формой или цветом полей при совмещении. Переворачивать части не разрешается (а поворачивать можно).
      Максимальное число частей равно 18. На рис. 3 представлены два разреза. Решение на рис. 3,а принадлежит Лойду; особенность его состоит в том, что одна из частей содержит восемь полей (максимум). В решении на рис. 3,6, отличающемся внешней симметрией, ни одна часть не содержит более пяти полей. На рис. 3,а части 17 и 18, или 8 и 9, хотя и имеют одинаковую форму отличаются цветом полей при совмещении. Другие части, например, 3 и 6, вообще не могут быть совмещены (переворачивать их нельзя).
      Рассмотрим рис. 4,а. Здесь требуется выполнить сразу три задания, одно математическое (на разрезание доски) и два чисто шахматных:
      а) разрезать доску на четыре одинаковые части (совпадающие при наложении); б) заматовать черного короля кратчайшим путем при ходе белых; в) заматовать черного короля кратчайшим путем при ходе черных (кооперативная игра).
      (...)
      В двух следующих задачах требуется разрезать шахматную доску на самые мелкие части, т. е. на отдельные поля.
      Пусть разрезанные части доски разрешается прикладывать друг к другу так, чтобы следующий разрез мог рассечь не одну, а несколько частей. Сколько разрезов надо произвести, чтобы получить 64 отдельных поля доски?
      Сначала разрежем доску пополам. Затем положим обе половины рядом и проведем второй разрез, получая четыре одинаковые части и т. д. Так как каждый разрез увеличивает число частей вдвое, то после шестого разреза доска распадается на 64 поля (64=2®).
      Пусть теперь каждую часть доски разрешается разрезать только в отдельности. Сколько разрезов понадобится в этом случае, чтобы получить 64 отдельных поля?
      Обычно эта задача, особенно если она предлагается сразу после предыдущей, вызывает определенные трудности. Вероятно, у решающих задачу в какой-то мере проявляется инерционность мышления. Ведь сразу видно, что придется произвести 63 разреза. Действительно, каждый разрез увеличивает число частей на единицу, но перед тем, как произвести первый разрез,
      мы имели одну часть (саму доску), а в результате их должно стать 64 (все поля доски).
      До сих пор мы считали, что разрезы обязательно проходят между вертикалями и горизонталями досьи, т. е. ровно по границам полей. В следующих дв) к задачах это условие не принимается во внимание.
      Какое максимальное число полей доски можно пересечь одним разрезом?
      KOHEЦ ФPAГMEHTA КНИГИ