Часть VI · Структуры Глава 40 из 60
Группы
Картонный квадрат, колода карт, «пятнашки» и кубик Рубика — четыре головоломки, за которыми стоит одна конструкция из четырёх правил. Соберём её и узнаем, почему в «пятнашках» нельзя поменять местами 14 и 15 и сколько раз нужно повторить R U, чтобы кубик собрался снова.
Опирается на: 39 · Ортогональность, МНК и SVD
Вы научитесь
- проверять аксиомы группы и составлять таблицу Кэли небольшой группы
- раскладывать перестановку на циклы, находить её порядок и чётность
- применять теорему Лагранжа и инвариант чётности к головоломкам: «пятнашкам» и кубику Рубика
Прошлая глава закончилась восемью матрицами. Это ортогональные матрицы $2 \times 2$, которые переводят в себя квадрат с центром в начале координат: четыре поворота и четыре отражения. Перемножьте любые две — и снова получится одна из восьми. У этих матриц своя таблица умножения $8 \times 8$, и больше для работы с ними ничего не нужно. Такая же таблица есть у поворотов граней кубика Рубика, у способов перетасовать колоду, у сложения часов на циферблате. Что у них общего?
Отвечать будем на головоломках: картонный квадрат, колода карт, «пятнашки» и кубик Рубика. У кубика 43 квинтиллиона позиций, и к концу главы про каждую можно будет сказать, собирается ли она, даже не пытаясь её собрать.
Картонный квадрат
Вырежьте из картона квадрат, нарисуйте на нём флажок и положите в квадратное гнездо по размеру. Сколькими способами его можно вынуть и положить обратно, чтобы он снова лёг в гнездо? Флажок нужен, чтобы способы различались: чистой картонке всё равно, как она лежит, а нам — нет.
Квадрат можно повернуть вокруг центра на $90^\circ$, $180^\circ$ или $270^\circ$ против часовой стрелки; обозначим эти повороты $r$, $r^2$ и $r^3$ (почему именно так, станет ясно чуть ниже). Можно перевернуть его, отразив в одной из четырёх осей: горизонтальной $h$, вертикальной $v$ или в диагоналях $d$ и $d'$. И можно ничего не делать — это тоже способ, обозначим его $e$. Всего восемь. Каждый из них — симметрия квадрата в смысле главы 23, то есть движение, переводящее фигуру в себя. Других нет, и это стоит доказать: так мы увидим, из чего складывается число восемь.
У квадрата ровно восемь симметрий: тождественное движение, три поворота вокруг центра и четыре отражения.
Хитрость в том, чтобы следить не за всем квадратом, а за двумя соседними вершинами.
Два движения можно выполнить одно за другим, и получится снова одно из восьми: если каждое возвращает картонку в гнездо, то и оба подряд возвращают. Порядок записи возьмём тот же, что у композиции функций и у произведения матриц: $a \circ b$, или просто $ab$, означает «сначала $b$, потом $a$». Тогда $r^2 = r \circ r$ — это дважды повёрнутый на $90^\circ$ квадрат, отсюда и обозначения поворотов.
Таблица Кэли — таблица, в которой на пересечении строки $a$ и столбца $b$ записан результат $a \circ b$. Для конечного набора она описывает операцию целиком.
Заполнять её лучше самим. Виджет ниже делает каждое движение медленно: повороты крутят картонку, а отражения переворачивают её, и тогда флажок виден с изнанки, зеркально.
Две вещи бросаются в глаза, даже когда заполнена половина таблицы. Первая: $r \circ h = d$, а $h \circ r = d'$. Отразить и повернуть — не то же самое, что повернуть и отразить, и таблица несимметрична относительно своей диагонали. Вторая: в каждой строке и в каждом столбце все восемь симметрий встречаются ровно по разу, как цифры в судоку. Первое — особенность квадрата. Второе, как мы скоро докажем, верно для любой такой таблицы.
Заодно видно, откуда взялась таблица из прошлой главы. Каждая симметрия квадрата — ортогональная матрица: $r = \left(\begin{smallmatrix} 0 & -1 \\ 1 & 0 \end{smallmatrix}\right)$, $h = \left(\begin{smallmatrix} 1 & 0 \\ 0 & -1 \end{smallmatrix}\right)$, и так далее, а выполнить движения одно за другим — значит перемножить матрицы. Проверьте: $rh = \left(\begin{smallmatrix} 0 & 1 \\ 1 & 0 \end{smallmatrix}\right)$. Эта матрица меняет координаты местами, то есть отражает в диагонали $y = x$, — это и есть $d$.
Сколько симметрий у прямоугольника, который не квадрат?
Рассуждаем как для квадрата. Вершины снова переходят в вершины, и вершина $1$ может попасть в любой из четырёх углов. Но теперь соседи неравноправны: длинная сторона должна перейти в длинную, так что место для вершины $2$ остаётся одно. Получается $4 \cdot 1 = 4$ симметрии: $e$, поворот на $180^\circ$ и отражения в горизонтальной и вертикальной осях. Отражения в диагоналях пропали: диагональ прямоугольника не делит его углы пополам.
Четыре правила
Отойдём от картона. Что нужно от набора действий, чтобы с ним можно было обращаться так же, как с симметриями квадрата? Всего четыре правила. Первое определение группы, не привязанное ни к симметриям, ни к перестановкам, дал в 1854 году английский математик Артур Кэли — вместе с таблицами, которые теперь называют его именем. Сегодня его записывают так.
Группа — множество $G$ вместе с операцией $\circ$, которая каждой паре элементов $a, b \in G$ сопоставляет элемент $a \circ b$ и подчиняется четырём аксиомам.
- Замкнутость. Для любых $a, b \in G$ результат $a \circ b$ тоже лежит в $G$.
- Ассоциативность. $(a \circ b) \circ c = a \circ (b \circ c)$ для любых $a, b, c \in G$; поэтому скобки можно не ставить.
- Нейтральный элемент. Есть элемент $e \in G$, для которого $e \circ a = a \circ e = a$ при любом $a$.
- Обратный элемент. Для каждого $a \in G$ есть элемент $a^{-1} \in G$, для которого $a \circ a^{-1} = a^{-1} \circ a = e$.
Симметрии квадрата выполняют все четыре. Замкнутость мы видели. Ассоциативность верна для любых преобразований: и $(a \circ b) \circ c$, и $a \circ (b \circ c)$ означают одно и то же — сначала $c$, потом $b$, потом $a$. Нейтральный элемент — $e$. Обратный к повороту — поворот на тот же угол в другую сторону, $r^{-1} = r^3$, а каждое отражение обратно самому себе: перевернули картонку дважды — она легла как лежала.
Переставлять множители аксиомы не разрешают, и правильно делают: у квадрата $rh \ne hr$. Группы, в которых $ab = ba$ для любых двух элементов, называют абелевыми — в честь норвежского математика Нильса Хенрика Абеля. Число элементов конечной группы называют её порядком и обозначают $|G|$.
Группу симметрий правильного $n$-угольника называют диэдральной и обозначают $D_n$ — это те самые наборы $D_n$ из теоремы Леонардо. В ней $2n$ элементов, $n$ поворотов и $n$ отражений; в части книг её поэтому пишут $D_{2n}$. Наш квадрат — это $D_4$, и $|D_4| = 8$.
Группы встречаются на каждом шагу.
| Множество | Операция | $e$ | Обратный | Абелева? |
|---|---|---|---|---|
| целые числа $\mathbb Z$ | сложение | $0$ | $-a$ | да |
| ненулевые рациональные числа | умножение | $1$ | $1/a$ | да |
| циферблат $\mathbb Z_{12}$ | сложение часов | $0$ | $12 - a$ (и $0$ для $0$) | да |
| симметрии квадрата $D_4$ | композиция | $e$ | обратное движение | нет |
| обратимые матрицы $n \times n$ | умножение | $E$ | $A^{-1}$ | нет при $n \ge 2$ |
Про циферблат подробнее. Если стрелка стоит на девяти, через пять часов она покажет два: $9 + 5 = 2$. Отметки $0, 1, \dots, n - 1$ со сложением по кругу образуют группу, которую обозначают $\mathbb Z_n$ (встречается и запись $\mathbb Z/n\mathbb Z$); на обычных часах $n = 12$, а полночь играет роль нуля. Обратимые матрицы образуют группу, потому что произведение обратимых обратимо, а у каждой есть обратная; внутри неё живут ортогональные матрицы из главы 39.
Какое из этих множеств с указанной операцией — группа?
Произведение ненулевых дробей — ненулевая дробь, умножение ассоциативно, нейтральный элемент — $1$, а у $\frac pq$ есть обратный $\frac qp$. Ноль пришлось выбросить: обратного у него нет.
Из аксиом сразу следуют три факта, и каждый пригодится.
В группе ровно один нейтральный элемент, и у каждого элемента ровно один обратный.
Идея в том, чтобы столкнуть двух кандидатов в одном произведении. Пусть $e$ и $e'$ оба нейтральны, и посмотрим на $e \circ e'$. Так как $e'$ нейтрален, это произведение равно $e$. Так как нейтрален $e$, оно равно $e'$. Значит, $e = e'$.
Теперь пусть у элемента $a$ два обратных, $b$ и $c$: $ab = ba = e$ и $ac = ca = e$. Тогда $b = be = b(ac) = (ba)c = ec = c$. В середине цепочки мы переставили скобки по ассоциативности, а по краям воспользовались тем, что $e$ нейтрален.
Если $ab = ac$, то $b = c$; если $ba = ca$, то тоже $b = c$. Поэтому в каждой строке и в каждом столбце таблицы Кэли каждый элемент группы встречается ровно один раз.
Умножим равенство $ab = ac$ слева на $a^{-1}$: $a^{-1}(ab) = a^{-1}(ac)$. По ассоциативности это $(a^{-1}a)b = (a^{-1}a)c$, то есть $eb = ec$ и $b = c$. Для равенства $ba = ca$ умножаем на $a^{-1}$ справа.
Теперь о таблице. В строке $a$ стоят произведения $ax$ по всем $x \in G$. Если бы какой-то элемент встретился в ней дважды, в столбцах $b \ne c$, то было бы $ab = ac$, а мы только что доказали, что тогда $b = c$. Значит, повторов нет. Пропусков тоже нет: любой элемент $y$ стоит в строке $a$ в столбце $x = a^{-1}y$, ведь $a(a^{-1}y) = (aa^{-1})y = y$. Со столбцами рассуждение то же, только $a^{-1}$ приписывается справа.
Проверим, что $b^{-1}a^{-1}$ отменяет $ab$. По ассоциативности $(ab)(b^{-1}a^{-1}) = a(bb^{-1})a^{-1} = aea^{-1} = aa^{-1} = e$, и точно так же $(b^{-1}a^{-1})(ab) = b^{-1}(a^{-1}a)b = b^{-1}b = e$. Обратный элемент единствен, поэтому это он и есть.
Колода карт
Фокусники умеют тасовать колоду идеально: делят 52 карты ровно пополам и вкладывают половины друг в друга, карта через карту. Если верхняя карта при этом остаётся наверху, перетасовку называют внешней. Колода после неё выглядит перемешанной, но фокусник знает то, что сейчас узнаем мы: через восемь таких перетасовок карты вернутся в исходный порядок.
Перетасовка — это перестановка: правило, которое для каждого места говорит, куда уходит лежащая там карта. Перестановку $n$ предметов удобно понимать как взаимно однозначное отображение $\sigma$ множества $\{1, 2, \dots, n\}$ на себя и записывать в две строки: сверху места, снизу — куда с них уходит карта.
$$\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 4 & 1 & 2 \end{pmatrix}: \qquad \sigma(1) = 3,\ \ \sigma(2) = 5,\ \ \sigma(3) = 4,\ \ \sigma(4) = 1,\ \ \sigma(5) = 2.$$
Все перестановки $n$ предметов вместе с композицией образуют группу. Её называют симметрической группой и обозначают $S_n$. Нейтральный элемент — перестановка, которая всё оставляет на месте, обратная к $\sigma$ возвращает каждую карту назад, а ассоциативность у композиции отображений есть всегда. Элементов в $S_n$ столько же, сколько способов расставить $n$ предметов в ряд, то есть $n!$ (глава 45). Для колоды из 52 карт это число из 68 цифр.
Двухстрочная запись громоздка, и есть запись удобнее. Проследим за картой с места $1$: $\sigma$ отправляет её на место $3$, карту с места $3$ — на место $4$, с места $4$ — снова на $1$. Круг замкнулся: $1 \to 3 \to 4 \to 1$. Оставшиеся места $2$ и $5$ обмениваются картами. Так и запишем: $\sigma = (1\,3\,4)(2\,5)$.
Цикл $(a_1\,a_2\,\dots\,a_k)$ — перестановка, которая переводит $a_1$ в $a_2$, $a_2$ в $a_3$, …, $a_k$ обратно в $a_1$ и не трогает остальные элементы; $k$ — длина цикла. Циклы без общих элементов называют независимыми.
Каждая перестановка конечного множества — композиция независимых циклов, и это разложение единственно с точностью до порядка циклов и выбора первого элемента в каждом из них.
Будем следить за элементом, как за картой. Начнём с $a$ и выпишем $a, \sigma(a), \sigma^2(a), \dots$. Множество конечно, поэтому элементы в этом ряду начнут повторяться. Первым повторится именно $a$. Иначе первый повтор выглядит как $\sigma^i(a) = \sigma^j(a)$ с $0 < i < j$, и, применив к обеим частям $\sigma^{-1}$, мы получили бы более ранний повтор $\sigma^{i-1}(a) = \sigma^{j-1}(a)$. Значит, путь из $a$ замыкается в цикл. Берём элемент, не попавший в этот цикл, и повторяем, пока элементы не кончатся. Построенные циклы не пересекаются: если $b$ лежит на пути из $a$, то путь из $b$ — тот же круг. Разложение единственно, потому что цикл, содержащий $a$, задан самой перестановкой: это путь $a, \sigma(a), \sigma^2(a), \dots$ до первого возвращения.
Теперь посчитаем, когда колода вернётся. Для этого нужно ещё одно слово. Порядок элемента $g$ группы — наименьшее натуральное $k$, при котором $g^k = g \circ g \circ \dots \circ g = e$; если такого $k$ нет, порядок бесконечен. У поворота $r$ квадрата порядок $4$, у отражения — $2$, у $e$ — $1$, у числа $1$ в группе $\mathbb Z$ он бесконечен.
Возьмём карту из цикла длины $\ell$. Каждое применение $\sigma$ сдвигает её по циклу на одну позицию, поэтому на своём месте она оказывается ровно тогда, когда число применений кратно $\ell$. Перестановка $\sigma^k$ тождественна, когда на местах все карты сразу, то есть когда $k$ кратно каждой из длин $\ell_1, \dots, \ell_m$. Наименьшее натуральное такое $k$ по определению — их наименьшее общее кратное.
Почему у внешней перетасовки такие короткие циклы, объясняет арифметика. Пронумеруем места с нуля, от $0$ до $51$. Карта с места $i$ из верхней половины уходит на место $2i$, из нижней — на $2i - 51$. Верхняя и нижняя карты стоят на месте, а для остальных место умножается на $2$ «по кругу» из $51$ отметки. Так как $2^8 = 256 = 5 \cdot 51 + 1$, восемь удвоений возвращают каждую карту домой. Этот приём — считать по кругу — станет главным героем следующей главы.
Найдите порядок перестановки $\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 3 & 5 & 1 & 7 & 6 & 4 & 2 \end{pmatrix}$: сколько раз её нужно повторить, чтобы всё вернулось на место?
Раскладываем на циклы: $1 \to 3 \to 1$ даёт $(1\,3)$, а $2 \to 5 \to 6 \to 4 \to 7 \to 2$ даёт $(2\,5\,6\,4\,7)$. Длины $2$ и $5$, порядок $\text{НОК}(2, 5) = 10$.
Чётные и нечётные
Самые простые перестановки меняют местами два предмета и больше ничего не трогают. Их называют транспозициями; транспозиция $(a\,b)$ — цикл длины $2$. Из транспозиций складывается любая перестановка: колоду можно упорядочить, каждый раз меняя местами две карты, — так работают многие алгоритмы сортировки. Достаточно разложить на транспозиции один цикл.
Цикл длины $k$ — произведение $k - 1$ транспозиций: $(a_1\,a_2\,\dots\,a_k) = (a_1\,a_k)\cdots(a_1\,a_3)(a_1\,a_2)$.
Транспозиции справа выполняются первыми. Проследим, куда уходит каждый элемент. Элемент $a_1$ первая транспозиция $(a_1\,a_2)$ отправляет в $a_2$, а дальше $a_2$ никто не трогает: итог $a_2$. Элемент $a_i$ при $1 < i < k$ пропускают все транспозиции до $(a_1\,a_i)$; она переводит его в $a_1$, следующая, $(a_1\,a_{i+1})$, — в $a_{i+1}$, и дальше его не трогают: итог $a_{i+1}$. Элемент $a_k$ дожидается последней транспозиции $(a_1\,a_k)$ и уходит в $a_1$. Остальные элементы не сдвигаются. Ровно так действует цикл.
Разложений у одной перестановки много: $(1\,2) = (1\,3)(2\,3)(1\,3)$ — одна транспозиция или три. Но число транспозиций в разложении всегда одной чётности. Чтобы это доказать, нужна величина, которая от разложения не зависит.
Инверсия перестановки $\sigma$ — пара $i < j$, для которой $\sigma(i) > \sigma(j)$: в нижней строке большее число стоит левее меньшего. У перестановки $\left(\begin{smallmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 4 & 1 & 2 \end{smallmatrix}\right)$ инверсий семь: тройка стоит левее единицы и двойки, пятёрка — левее четвёрки, единицы и двойки, четвёрка — левее единицы и двойки.
Если в перестановке поменять местами содержимое любых двух мест, число инверсий изменит чётность.
Хитрость в том, чтобы нарисовать перестановку проводами: инверсии станут пересечениями, а пересечения легко считать.
Перестановку называют чётной, если у неё чётное число инверсий, и нечётной, если нечётное. Её знак $\operatorname{sgn}\sigma$ равен $+1$ для чётной перестановки и $-1$ для нечётной.
Если перестановка записана как произведение $k$ транспозиций, то $\operatorname{sgn}\sigma = (-1)^k$; поэтому все её разложения в транспозиции имеют одинаковую чётность длины. Кроме того, $\operatorname{sgn}(\sigma\tau) = \operatorname{sgn}\sigma \cdot \operatorname{sgn}\tau$.
У тождественной перестановки инверсий нет, и она чётна. Если $\sigma = t_1t_2\cdots t_k$, где $t_i$ — транспозиции, то $\sigma$ получается из тождественной перестановки $k$ шагами: сначала применяем $t_k$, потом $t_{k-1}$, и так далее. Применить транспозицию $(p\,q)$ после перестановки — значит поменять местами содержимое мест $p$ и $q$, и по теореме каждый такой шаг меняет знак. Поэтому $\operatorname{sgn}\sigma = (-1)^k$. Левая часть зависит только от самой $\sigma$, так что у двух разложений одной перестановки чётность $k$ одинакова. Наконец, если $\sigma$ — произведение $k$ транспозиций, а $\tau$ — произведение $l$, то $\sigma\tau$ — произведение $k + l$ транспозиций, и $(-1)^{k+l} = (-1)^k(-1)^l$.
Считать инверсии по одной утомительно. Циклы дают ответ быстрее.
Чётные перестановки $n$ предметов образуют группу: произведение чётных чётно, тождественная перестановка чётна, а обратная к чётной чётна, потому что $\operatorname{sgn}\sigma \cdot \operatorname{sgn}\sigma^{-1} = \operatorname{sgn} e = 1$. Её называют знакопеременной группой $A_n$. При $n \ge 2$ в ней ровно половина всех перестановок, $n!/2$: приписывание транспозиции $(1\,2)$ взаимно однозначно переводит чётные перестановки в нечётные и обратно.
Сколько инверсий у перестановки с нижней строкой $2\;4\;1\;3$? Чётна ли она?
Двойка стоит левее единицы — одна инверсия; четвёрка левее единицы и тройки — ещё две; остальные пары в правильном порядке. Всего $3$ инверсии, перестановка нечётная. Проверка по циклам: $1 \to 2 \to 4 \to 3 \to 1$, один цикл длины $4$, и $n - c = 4 - 1 = 3$ — тоже нечётно.
Набить руку на композициях, циклах, порядках и знаках можно в тренажёре.
Пятнашки
Зимой 1880 года Америку охватила мода на игру в коробочке $4 \times 4$: пятнадцать пронумерованных фишек и одна пустая клетка. Фишку, соседнюю с пустой клеткой, можно сдвинуть в неё, и цель — расставить фишки по порядку. К весне мода добралась до Европы, а к лету угасла. Придумал игру почтмейстер Нойес Чепмен из городка Канастота в штате Нью-Йорк, примерно в 1874 году; в марте 1880-го он подал заявку на патент. В 1891 году знаменитый составитель головоломок Сэм Лойд объявил изобретателем себя и до конца жизни рассказывал, будто обещал тысячу долларов тому, кто вернёт на место переставленные фишки 14 и 15. Историки головоломок Джерри Слокум и Дик Сонневельд в 2006 году показали, что к изобретению и к моде на игру Лойд отношения не имел. Обещанная премия — скорее всего, часть той же легенды. А вот задача про 14 и 15 настоящая.
Чтобы следить за позицией, будем считать пустую клетку шестнадцатой фишкой. Тогда позиция — перестановка $\pi$ шестнадцати мест: фишка, которой положено стоять на месте $i$, стоит на месте $\pi(i)$. Раскрасим доску в шахматном порядке так, чтобы правый нижний угол, где пустая клетка стоит в собранной позиции, был белым.
В любой позиции, которую можно получить ходами из собранной, перестановка $\pi$ чётна тогда и только тогда, когда пустая клетка стоит на белом поле. В частности, позиция, в которой переставлены только фишки 14 и 15, недостижима.
Хитрость в том, чтобы следить сразу за двумя признаками: каждый ход меняет оба.
Эту половину ответа опубликовал в 1879 году Уильям Джонсон, в заметке о «пятнашках» для «Американского математического журнала». В той же публикации Уильям Стори доказал вторую половину: всё, что не запрещено инвариантом, достижимо. Значит, из $16!$ расстановок фишек и пустой клетки ходами можно получить ровно половину — $10\,461\,394\,944\,000$.
Почему достижимо всё остальное
Любая позиция, в которой перестановка $\pi$ чётна ровно тогда, когда пустая клетка на белом поле, получается ходами из собранной.
Идея: научиться переставлять по кругу любые три фишки, ничего больше не трогая, а потом сложить из таких тройных циклов любую чётную перестановку.
Сначала приведём пустую клетку домой, в правый нижний угол, по любому пути. Инвариант сохраняется, так что перестановка пятнадцати фишек в полученной позиции чётна. Ходы обратимы, поэтому достаточно показать, что с пустой клеткой дома можно получить любую чётную перестановку фишек. Цепочки ходов, которые начинаются и заканчиваются с пустой клеткой дома, назовём петлями. Петли можно выполнять одну за другой и отменять, проходя их задом наперёд, поэтому перестановки фишек, которые они дают, образуют группу $G$. По инварианту $G$ лежит в $A_{15}$; нужно доказать, что $G = A_{15}$.
Пройдём пустой клеткой по замкнутому маршруту через все шестнадцать полей: из угла влево, вверх по третьему столбцу до второй строки, вниз по второму столбцу, вверх по первому до самого верха, вправо по верхней строке и вниз по правому столбцу домой. Пронумеруем поля по порядку обхода числами $1, \dots, 15$. После полного обхода каждая фишка сдвигается на одно поле назад по маршруту, а фишка с поля $1$ — на поле $15$: петля даёт цикл $s$ длины $15$. Маленькая петля — пустая клетка вверх, влево, вниз и вправо вокруг квадрата $2 \times 2$ в правом нижнем углу — переставляет по кругу три фишки на полях $15$, $1$ и $2$. Эти поля идут по маршруту подряд.
Сделаем петлю $s$ несколько раз, потом маленькую петлю, а потом отменим сделанные обходы. Фишки, которые обходы привели на поля $15$, $1$ и $2$, переставятся по кругу, а после отмены обходов окажутся переставленными по кругу между своими исходными полями — тремя полями, идущими по маршруту подряд. Остальные фишки вернутся на место. Так получаются тройные циклы любых трёх подряд идущих по маршруту полей: $(1\,2\,3)$, $(2\,3\,4)$, …, $(13\,14\,15)$, а если пройти маленькую петлю в обратную сторону — и обратные к ним.
Осталось доказать, что такие циклы порождают $A_{15}$. Любая чётная перестановка — произведение чётного числа транспозиций; разобьём их на пары. Пара с общим элементом даёт тройной цикл: $(a\,b)(b\,c) = (a\,b\,c)$. Пара без общих элементов — два тройных цикла: $(a\,b)(c\,d) = (a\,b)(b\,c) \cdot (b\,c)(c\,d)$. Значит, достаточно получить все тройные циклы. Покажем по индукции: из циклов $(1\,2\,3), \dots, (k-2\;k-1\;k)$ и обратных к ним получаются все тройные циклы на числах $1, \dots, k$. При $k = 3$ утверждение верно: тройных циклов на трёх числах всего два, $(1\,2\,3)$ и обратный к нему. Пусть утверждение верно для $k$, и добавим цикл $c = (k-1\;k\;k+1)$. Нужно получить любой цикл $(a\,b\;k+1)$ с различными $a, b \le k$. По предположению индукции нам доступны все тройные циклы на числах $1, \dots, k$, а значит, по сказанному выше, и вся группа $A_k$. Возьмём перестановку $p$ чисел $1, \dots, k$, для которой $p(k-1) = a$ и $p(k) = b$; если она нечётна и $k \ge 4$, сделаем её чётной, приписав справа транспозицию двух чисел, отличных от $k-1$ и $k$. Тогда $p\,c\,p^{-1} = (a\;b\;k+1)$: прямой проверкой, $p\,c\,p^{-1}$ переводит $a$ в $b$, $b$ в $k+1$, $k+1$ в $a$ и не трогает остального. При $k = 3$ чётных $p$ хватает, чтобы получить циклы $(a\,b\,4)$ для трёх пар $(a, b)$ из шести, а остальные — обратные к ним: $(a\,b\,4)^{-1} = (b\,a\,4)$. Все тройные циклы на числах $1, \dots, k+1$ либо не содержат $k + 1$, либо имеют вид $(a\,b\;k+1)$, и индукция завершена. Значит, $G = A_{15}$.
Урок «пятнашек» шире самой игры. Чтобы доказать, что задача нерешаема, не нужно перебирать все попытки. Нужно найти величину, которую не меняет ни один разрешённый ход, — инвариант, — и показать, что у цели она другая. Группы дают для таких величин готовый материал: чётность, порядки, остатки. Ниже тот же приём разберётся с кубиком Рубика.
Сколько подгрупп?
Часовая стрелка прыгает каждый раз на четыре часа вперёд. Какие отметки она посетит? Ноль, четыре, восемь — и снова ноль: всего три. Прыгая по три часа, она посетит четыре отметки, по шесть — две, по пять — все двенадцать: $5, 10, 3, 8, 1, 6, 11, 4, 9, 2, 7, 0$. Три, четыре, два, двенадцать — всё делители двенадцати. Совпадение?
Подгруппа группы $G$ — подмножество $H \subset G$, которое само образует группу с той же операцией: вместе с любыми двумя элементами содержит их произведение, содержит $e$ и вместе с каждым элементом — обратный к нему.
Отметки, которые посещает стрелка, образуют подгруппу $\mathbb Z_{12}$. Так бывает в любой группе: для каждого элемента $g$ все его степени $\dots, g^{-2}, g^{-1}, e, g, g^2, \dots$ образуют подгруппу, её обозначают $\langle g \rangle$. Если порядок $g$ равен $k$, то $\langle g \rangle = \{e, g, g^2, \dots, g^{k-1}\}$ и в ней ровно $k$ элементов: дальше степени повторяются, а раньше повтора быть не может, ведь из $g^i = g^j$ при $0 \le i < j < k$ следовало бы $g^{j-i} = e$. Группу, все элементы которой — степени одного элемента, называют циклической, а этот элемент — её образующей. Циферблат $\mathbb Z_{12}$ циклический: его порождает отметка $1$, а заодно $5$, $7$ и $11$. Повороты квадрата $\{e, r, r^2, r^3\}$ — циклическая подгруппа $D_4$ с образующей $r$.
Смежный класс элемента $g$ по подгруппе $H$ — множество $gH = \{gh : h \in H\}$. На циферблате, где операция — сложение, пишут $g + H$: это подгруппа, сдвинутая на $g$ часов.
Если $H$ — подгруппа конечной группы $G$, то $|H|$ делит $|G|$. Точнее, $G$ разбивается на смежные классы по $H$, каждый из $|H|$ элементов.
Хитрость в том, чтобы разрезать всю группу на сдвинутые копии $H$.
Порядок любого элемента конечной группы делит порядок группы. Группа простого порядка $p$ циклическая, и её порождает любой элемент, кроме $e$.
Порядок элемента $g$ равен числу элементов подгруппы $\langle g \rangle$, как мы видели выше, а это число делит $|G|$ по теореме Лагранжа. Если $|G| = p$ простое и $g \ne e$, то порядок $g$ — делитель $p$, больший единицы, то есть сам $p$. Значит, в $\langle g \rangle$ все $p$ элементов группы.
Поэтому в группе $S_5$ из $120$ элементов нет перестановки порядка $7$: семь не делит $120$. Подгрупп у $D_4$ десять: сама группа, $\{e\}$, пять подгрупп из двух элементов — $\{e, r^2\}$ и по одной на каждое отражение — и три подгруппы из четырёх: повороты $\langle r \rangle$, $\{e, r^2, h, v\}$ и $\{e, r^2, d, d'\}$. Их размеры $1$, $2$, $4$, $8$ — все делят восемь.
Сколько отметок посетит часовая стрелка, если каждый раз прыгает на девять часов вперёд? Иначе говоря, сколько элементов в подгруппе $\langle 9 \rangle$ группы $\mathbb Z_{12}$?
$9, 18 \to 6, 15 \to 3, 12 \to 0$: стрелка посещает $\{0, 9, 6, 3\}$ и возвращается. Четыре отметки — те же, что при прыжках по три часа. Так и должно быть: сдвиг на девять вперёд — это сдвиг на три назад, а $4$ делит $12$.
Кубик Рубика
Венгерский архитектор и преподаватель Эрнё Рубик придумал свой кубик в 1974 году. Кубик — тоже машина перестановок. Каждый поворот грани переставляет 54 цветные наклейки (центральные наклейки граней при этом остаются на месте), и каждая позиция получается из собранной какой-то цепочкой поворотов. Все такие перестановки наклеек образуют группу: цепочки можно выполнять подряд и отменять. Обозначения сборщиков: $R$, $L$, $U$, $D$, $F$, $B$ — четверть оборота правой, левой, верхней, нижней, передней или задней грани по часовой стрелке, если смотреть на эту грань; $R'$ — тот же поворот против часовой, $R2$ — пол-оборота.
Повторим одну комбинацию много раз. Если это $R$, кубик соберётся через четыре поворота. А если $R\,U$ — правую грань, потом верхнюю? Ответ — $105$ раз, и объясняет его формула порядка перестановки.
Сколько всего позиций у кубика? Разберём его и соберём как попало: восемь уголков можно расставить по угловым местам $8!$ способами и каждый повернуть тремя способами, двенадцать рёбер — расставить $12!$ способами и каждое перевернуть двумя. По правилу произведения получается $8! \cdot 3^8 \cdot 12! \cdot 2^{12} = 519\,024\,039\,293\,878\,272\,000$ сборок. Но не все они достижимы поворотами. Нужны два определения. Ориентацию уголка отмечаем по его наклейке цвета верхней или нижней грани: $0$, если она смотрит вверх или вниз, $1$, если уголок повёрнут относительно такого положения на треть оборота по часовой стрелке, $2$ — если против. У каждого ребра выберем главную наклейку: цвета верхней или нижней грани, а если такой нет — цвета передней или задней. Ребро назовём перевёрнутым, если его главная наклейка смотрит вбок, когда ребро в верхнем или нижнем слое, и вправо или влево, когда оно в среднем слое.
В любой позиции, полученной поворотами граней из собранной: перестановка уголков и перестановка рёбер имеют одинаковую чётность; сумма ориентаций уголков делится на $3$; число перевёрнутых рёбер чётно.
В собранной позиции все три закона выполнены: перестановки тождественные, ориентации нулевые. Проверим, что их сохраняет каждый поворот на четверть оборота; пол-оборота — это два таких поворота. Поворот грани переставляет по кругу четыре её уголка и отдельно четыре её ребра: это два цикла длины $4$, каждый из трёх транспозиций, то есть нечётный. Значит, чётности перестановок уголков и рёбер меняются одновременно и остаются равными.
Поворот $U$ или $D$ не трогает ориентаций: наклейки верхнего и нижнего цвета как смотрели вверх или вниз, так и смотрят, и рёбра переезжают внутри своего слоя, не переворачиваясь. Поворот любой другой грани поворачивает четыре своих уголка на $1$, $2$, $1$ и $2$ трети оборота. Это видно по одному уголку: поворот $R$ переносит уголок из правого верхнего переднего угла в правый верхний задний, и его верхняя наклейка оказывается на задней грани, то есть уголок повёрнут. Сумма ориентаций меняется на $1 + 2 + 1 + 2 = 6$ и по-прежнему делится на $3$. Повороты $R$ и $L$ рёбер не переворачивают, а $F$ и $B$ переворачивают ровно четыре ребра своей грани; число перевёрнутых рёбер меняется на чётное число. Каждое из этих утверждений проверяется одним взглядом на кубик или в виджете: сделайте поворот и найдите, куда уехали наклейки.
Разобьём все сборки на дюжины: в каждой дюжине сборки отличаются только тем, как повёрнут один выбранный уголок (три варианта), перевёрнуто ли одно выбранное ребро (два) и переставлены ли два выбранных ребра (два). Поворот уголка меняет сумму ориентаций на $0$, $1$ или $2$, поэтому закону о сумме удовлетворяет ровно один из трёх вариантов. Переворот ребра меняет чётность числа перевёрнутых рёбер, обмен двух рёбер — чётность их перестановки. Значит, в каждой дюжине три закона выполняются ровно для одной сборки, и достижимых позиций не больше двенадцатой части. То, что их ровно столько, то есть что каждая позиция с выполненными законами собирается, доказывает любой полный метод сборки: он приводит к решению каждую такую позицию. Например, послойный метод из учебника «Кубик Рубика» на этом сайте: на последнем шаге он умеет исправить всё, что законы не запрещают.
Сборщики пользуются приёмом, который в теории групп называют коммутатором: $x\,y\,x^{-1}y^{-1}$. Если $x$ и $y$ перестановочны, коммутатор ничего не делает. Повороты граней не перестановочны, но почти: $R$ и $U$ задевают общие детали только в одном углу кубика. Поэтому $R\,U\,R'\,U'$ сдвигает всего семь деталей из двадцати, а остальные возвращает на место; порядок у него $6$. Из таких «почти ничего» и собираются алгоритмы, которые меняют две-три детали и не трогают остальные.
Сколько ходов нужно, чтобы собрать самую запутанную позицию? В июле 2010 года Томас Рокицки, Герберт Коцемба, Морли Дэвидсон и Джон Детридж доказали: не больше двадцати, если поворот грани на пол-оборота считать одним ходом. Перебор занял около 35 лет процессорного времени, которое выделила компания Google. Позиции, требующие ровно двадцати ходов, существуют, поэтому 20 называют числом Бога. Если считать ходом только четверть оборота, число Бога равно 26; это установили в 2014 году.
Научиться собирать кубик, а заодно посмотреть на все эти перестановки вживую, можно в учебнике «Кубик Рубика» на этом сайте.
Одна таблица, разные костюмы
Повороты квадрата $e, r, r^2, r^3$, циферблат из четырёх отметок $\mathbb Z_4$ и четыре комплексных числа $1, i, -1, -i$ с умножением — три разных набора, но таблицы у них одинаковые, если переименовать элементы: $r^k \leftrightarrow k \leftrightarrow i^k$. Умножение на $i$ — поворот на $90^\circ$ (глава 15), и перемножить $i^a$ и $i^b$ — всё равно что сложить часы $a + b$ на четырёхчасовом циферблате.
Изоморфизм групп $G$ и $H$ — взаимно однозначное соответствие $\varphi\colon G \to H$, которое переносит операцию: $\varphi(ab) = \varphi(a)\,\varphi(b)$ для любых $a, b \in G$. Группы, между которыми есть изоморфизм, называют изоморфными и пишут $G \cong H$. Таблица Кэли одной из них получается из таблицы другой переименованием элементов.
Любая циклическая группа из $n$ элементов изоморфна $\mathbb Z_n$: степени образующей складываются, как часы на циферблате из $n$ отметок, — $g^ag^b = g^{a+b}$, и после $g^{n-1}$ снова идёт $g^n = e$. Симметрии правильного треугольника переставляют его вершины, причём разные симметрии — по-разному. Симметрий шесть, и перестановок трёх вершин тоже $3! = 6$, так что получаются все, и $D_3 \cong S_3$. С квадратом так не выйдет: перестановок четырёх вершин $24$, а симметрий только $8$. Например, поменять местами две соседние вершины, оставив две другие на месте, нельзя.
Симметрии прямоугольника, который не квадрат: $e$, поворот на $180^\circ$ и два отражения. Изоморфна ли эта группа циферблату $\mathbb Z_4$?
В $\mathbb Z_4$ есть элемент порядка $4$ — отметка $1$: $1 + 1 + 1 + 1 = 0$. У прямоугольника любая симметрия, повторённая дважды, даёт $e$, и порядки не больше $2$. Изоморфизм сохраняет порядки: из $g^k = e$ следует $\varphi(g)^k = \varphi(g^k) = e$, и наоборот. Значит, соответствия нет. Группу симметрий прямоугольника называют четверной группой Клейна.
Из правила судоку следует сильный вывод: с точностью до изоморфизма любая конечная группа — это группа перестановок.
Каждая конечная группа из $n$ элементов изоморфна некоторой подгруппе симметрической группы $S_n$.
Идея спрятана в строках таблицы Кэли. По правилу судоку строка $g$ содержит каждый элемент группы ровно по разу, то есть умножение слева на $g$, $x \mapsto gx$, переставляет элементы группы. Обозначим эту перестановку $\lambda_g$. Разные элементы дают разные перестановки, потому что $\lambda_g(e) = g$. Операция переносится: $\lambda_{gh}(x) = (gh)x = g(hx) = \lambda_g(\lambda_h(x))$, то есть $\lambda_{gh} = \lambda_g \circ \lambda_h$. Отсюда перестановки $\lambda_g$ замкнуты относительно композиции, среди них есть тождественная $\lambda_e$ и обратная к каждой, $\lambda_{g^{-1}}$. Они образуют подгруппу $S_n$, а соответствие $g \mapsto \lambda_g$ — изоморфизм.
Куда дальше
Циферблат $\mathbb Z_{12}$ — группа по сложению. А если на циферблате умножать? На часах с простым числом отметок, скажем с семью, ненулевые отметки $1, 2, \dots, 6$ образуют группу по умножению: $3 \cdot 5 = 15$, а пятнадцать часов на семичасовом циферблате — это $1$, так что $5$ обратна к $3$. В этой группе шесть элементов, и по теореме Лагранжа порядок любого из них делит шесть, поэтому $a^6$ всегда даёт $1$. Это малая теорема Ферма, доказанная почти даром. На ней держится шифр, которым банк защищает ваш перевод. Остаётся загадка: как двум людям договориться о секретном ключе, если весь их разговор слышат посторонние? Ответ — в главе 41.