Мартин Гарднер - Математические головоломки и развлечения

• Название: Математические головоломки и развлечения
• Автор: Мартин Гарднер
• Издательство: "Мир"
• Жанр: Развлечения
• Год: 1999
• ISBN: 5-03-003340-8

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

---

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

1. Каждой паре элементов множества операция ставит в соответствие некоторый элемент того же множества. Это свойство носит название «замкнутости» множества относительно операции.

2. Операция подчиняется «ассоциативному закону»:

(а о Ь) о с = а о (b о с).

3. Существует элемент е (называемый «единицей»), такой, что

а о е = е о а = а.

4. Для каждого элемента а существует обратный элемент а', такой, что

а о а' = а' о а = е.

Если помимо только что названных четырех условий операция подчиняется еще и коммутативному закону:

а о Ь = b о a,

то группа называется коммутативной, или абелевой.

Целые числа — положительные, отрицательные и нуль — образуют группу относительно сложения (это наиболее известный пример группы). Множество целых чисел замкнуто относительно сложения (прибавить 2 к 3, а затем к 4 — то же самое, что прибавить 2 к сумме чисел 3 и 4); «единицей» группы служит 0, а элементом, обратным (или, как говорят еще, противоположным) целому положительному числу, — то же число, взятое со знаком минус. Группа целых чисел относительно сложения — абелева (2 + 3 = 3 + 2). Если в качестве операции выбрать деление, то целые числа не будут образовывать группы: поделив 5 на 2, мы получим 2,5, а это число не принадлежит множеству целых чисел.

Выясним теперь, с какой группой связана задача о блуждании по линиям «утка и основы». Шесть основных «преобразований» — элементов нашей конечной группы — изображены на рис. 181.

Рис. 181 Шесть элементов группы, возникающей в задаче о блуждании по сети линий.

Преобразование р «переводит стрелку»: начав двигаться по прямой А, вы закончите свой путь на прямой В и, наоборот, начав путь по прямой В, вы в конце концов окажетесь на прямой А (зато, попав напрямую С, вы останетесь на ней до конца). Преобразования q, r, s и t задают другие перестановки начал и концов различных путей.

Преобразование е в действительности ничего не меняет, но математики все равно называют его «преобразованием» в том же смысле, в каком пустое множество, не содержащее ни одного элемента, называют множеством. Для того чтобы выполнить преобразование е, не нужно проводить вообще никаких горизонтальных линий; это «тождественное» преобразование, которое в действительности ничего не преобразует. Шесть элементов группы соответствуют шести различным перестановкам трех символов. Групповая операция, обозначенная символом о, заключается в последовательном выполнении одного преобразования за другим, в добавлении к горизонтальной линии одного преобразования горизонтальной линии следующего преобразования.

Нетрудно проверить, что все свойства группы соблюдены. Множество преобразований замкнуто относительно операции «добавление горизонтальных линий» потому, что какую бы пару его элементов мы ни взяли, концы линий А, В и С окажутся переставленными так же, как и в результате применения к прямым А, В и С одного из шести преобразований. Например, р о t = r, так как, выполнив вслед за преобразованием р преобразование t, мы получим в точности такое же расположение концов линий А, В и С, какое получается при действии лишь одного преобразования г. Добавление горизонтальных линий, очевидно, ассоциативно (то есть, имея три горизонтали, мы можем сначала построить две первые, а затем пристроить к ним третью, но можем действовать и иначе: сначала провести две последние, посмотреть, как выглядит их «сумма», и добавить ее к первой горизонтали; в том и в другом случае результат будет одинаков). Если не проводить никаких горизонталей, то получится единичное, или тождественное, преобразование. Элементы р, q и r совпадают с обратными им элементами, а каждый из элементов s и t обратен другому. (Выполнить вслед за одним преобразованием другое, ему обратное, все равно, что вообще не проводить новых горизонтальных линий.) Полученная группа неабелева (например, если выполнить сначала преобразование q, a потом преобразование р, то результат получится совсем иным, чем в том случае, когда сначала выполняется преобразование р и лишь затем — преобразование q).

Полное описание строения этой группы видно из рис. 182.

Рис. 182 Результаты последовательного выполнения двух преобразований из группы, возникающей в задаче о блуждании по сети линий.

Что получится, если вслед за преобразованием r проделать преобразование s? Найдем букву r среди букв, выписанных слева от таблицы, и букву s среди букв, выписанных сверху. На пересечении r-й строки и s-ro столбца стоит буква р. Иначе говоря, добавив к горизонтальным линиям преобразования r горизонтальные линии преобразования s, мы получим такую же перестановку нижних концов вертикальных линий А, В и С, какая возникает, если провести горизонтальные линии одного лишь преобразования р. Эта чрезвычайно простая группа возникает во многих местах. Например, если обозначить тремя различными буквами вершины равностороннего треугольника, а затем произвести над ним все повороты и отражения, в результате которых он совмещается с самим собой, то окажется, что различных преобразований имеется только шесть и они образуют в точности такую же группу, как только что описанная.

Не обязательно вникать в тонкости теории групп, чтобы интуитивно понять, что, блуждая по сети, никакие два игрока не могут закончить свой путь на одной и той же вертикали. Вообразим, что три вертикальные линии — это просто-напросто три веревки. Каждый раз, проводя горизонтали, мы как-то переставляем нижние концы вертикалей, но точно такого же результата мы достигнем, если перевьем две веревки так, как это делают с прядями волос при заплетании косы. Ясно, что, как бы вы ни заплетали косу и какой бы длинной она ни была, дойдя до ее конца, вы всегда сможете различить все три пряди.

Представим себе, что и мы заплетаем девичью косу из трех прядей. Схематически последовательные перестановки прядей можно изобразить в виде сети (аналогичной той, которой мы пользовались в задаче о трех программистах), но при этом останется неясным, какие пряди оказываются сверху, а какие — снизу. Пригодна ли теория групп для описания действий, производимых нами при заплетании косы, с учетом этого усложняющего топологического фактора? Оказывается, вполне пригодна. Впервые это доказал немецкий математик Эмиль Артин. В его изящной теории кос элементами группы (их бесконечно много) служат «схемы переплетания», а групповой операцией, так же как в задаче о блуждании по сети линий, — последовательное применение одной схемы за другой.

Роль единичного элемента играет схема переплетения, состоящая из трех отдельных вертикалей — не переплетенных между собой прядей («косу еще не начинали заплетать»). Чтобы найти элемент группы, обратный какой-нибудь схеме переплетения, нужно просто взять зеркальное отражение этой схемы. На рис. 183 показана простенькая схема, взятая вместе с обратной ей схемой.

Рис. 183 Коса А — зеркальное отражение косы А'.

Если косу заплести сначала по «прямой», а потом по обратной схеме, то достаточно очевидно, что результат будет топологически эквивалентен заплетанию по единичной схеме: стоит лишь слегка потянуть за конец косы, изображенной на рис. 183, как все ее пряди расплетутся и выпрямятся. (Многие фокусы с распутыванием шнурков и веревочек основаны именно на этом небезынтересном групповом свойстве. Об одном из наиболее эффективных фокусов такого рода мы рассказали в главе 22.) В своей теории кос Артин не только впервые произвел классификацию всех мыслимых типов кос, но и предложил метод, позволивший узнавать, эквивалентны топологически или нет любые две сколь угодно сложные схемы переплетения.