Гашков С.В. Современная элементарная алгебра в задачах и решениях

8.Граф любой перестановки из Sn имеет ровно n ребер (стрелок)

иявляется объединением попарно непересекающихся циклов (в частности, сам может быть циклом длины n).

9*. (И. Н. Сергеев.) Пусть B и A – k-элементные подмножества En = = {1, . . ., n} и f Sn – такая перестановка, что для любого i из B справед-

ливы соотношения i 6 f(i) A. Докажите, что существует перестановка

g Sn такая, что j > g(j) / A для любого j / B и j 6 g(j) A для любого j B. У к а з а н и е. Примените разбиение на циклы.

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

11*. (Эйлер.) Письма в n конвертах перемешали так, что ни одно письмо не попало по адресу. Сколькими способами это можно сделать? У к а з а н и е. Примените формулу включения-исключения.

12*. (Преобразование пекаря.) Числа n, m, k таковы, что k < m < n

. . ., an, ak+1, . . ., am, a1, . . ., ak. Докажите, что в каждом столбце записаны все числа от 1 до n.

§ 1.10. Циклы и транспозиции

Определение 31. Транспозициями называются циклы длины два. Говорят, что циклы (a1, . . ., ak) и (b1, . . ., bl) не пересекаются, если

{a1, . . . , ak} ∩ {b1, . . . , bl } = . Справедлива следующая теорема.

Теорема 23 (о разложении на циклы). Любая перестановка π из Sn может быть представлена в виде произведения попарно непересекающихся циклических перестановок (единичную перестановку ε Sn можно рассматривать как циклическую перестановку порядка 1), причем это представление единственно с точностью до порядка сомножителей, который может быть любым.

Определение 33. Пару (i, j) назовем инверсией для перестановки π, если i < j и π (i) > π (j). Число всех инверсий у перестановки π обозначаем I(π).

Справедлива следующая теорема.

Теорема 24 (о разложении на транспозиции). (i) Любая перестановка π Sn разлагается в произведение транспозиций, причем наименьшее число сомножителей в таком произведении равно d(π).

(ii) Любая перестановка π Sn разлагается в произведение вида

(1, 2) (2, 3) (3, 4) . . . (n − 1, n),

причем наименьшее число сомножителей в таком произведении равно I(π).

Д о к а з а т е л ь с т в о. Для него понадобятся две леммы.

Лемма 5. Для любой перестановки π Sn и транспозиции τ справедливо равенство |d(π ◦ τ) − d(π)| = 1.

Д о к а з а т е л ь с т в о. Из определения декремента следует, что достаточно проверить, что при умножении перестановки на транспозицию число циклов изменяется на единицу. Будем изображать перестановку π в виде графа, а транспозицию τ = (i, j) – в виде ребра (i, j) на этом графе. Тогда достаточно проверить, что если ребро соединяет два цикла графа π, то в графе перестановки π ◦ τ эти два цикла сливаются в один, а если это ребро соединяет вершины одного цикла, то он распадается на два цикла (остальные циклы в обоих случаях остаются без изменения). Для проверки последнего утверждения достаточно проверить тождества

(k1, . . . , kl) ◦ (m1, . . . , mt) ◦ (kl , mt) = (m1, m2, . . . , mt , k1, k2, . . . , kl), (k1, . . . , ks , . . . , kl) ◦ (ks , kl) = (k1, . . . , ks) ◦ (ks+1, ks+2, . . . , kl).

Лемма 6. Для любой перестановки π Sn и транспозиции

τ= (i, i + 1) справедливо равенство |I(π ◦ τ) − I(π)| = 1.

До к а з а т е л ь с т в о. Непосредственно проверяется, что для обоих перестановок π и π ◦ τ число инверсий среди двух пар hk, ii и hk, i + 1i

(при k < i) и hi, ki, hi + 1, ki (при k > i + 1) одинаково, а пара hk, li при {k, l} ∩ {i, j + 1} = для обоих этих перестановок будет или не будет инверсией одновременно. Остается заметить, что пара hi, i + 1i будет инверсией ровно для одной из перестановок π и π ◦ τ .

Докажем теперь теорему. Пусть π = τ1 . . . τk, где τi – произвольные транспозиции (соответственно транспозиции вида (i, i + 1)). Определим

68 Глава I. Числа и комбинаторика

13. Множество перестановок называется базисом в Sn, если любая перестановка разлагается в произведение перестановок из этого множества, а никакое собственное его подмножество этим свойством не обладает. Докажите, что системы транспозиций {(1, 2), (1, 3), . . ., (1, n)} и {(1, 2), (2, 3), . . . , (n − 1, n)}, а также транспозиция (1, 2) и цикл (1, 2, . . . , n) являются базисами в Sn.

14*. Сопоставим системе транспозиций U Sn граф с вершинами 1, 2, . . . , n, в котором вершины i и j соединяются ребром тогда и только тогда, когда транспозиция (i, j) принадлежит множеству U. Докажите, что U – базис в Sn тогда и только тогда, когда соответствующий граф – дерево.

15*. В городе n высотных зданий, никакие три из которых не лежат на одной прямой. Турист, гуляя по городу, записывает порядок, в котором они видны ему из разных районов. Сколько разных перестановок зданий будет в его записях?

16. Для любых перестановок f, g Sn справедливо равенство

I(f ◦ g) 6 I(f) + I(g).

17. Назовем знаком перестановки π Sn число sgn(π) = (−1)I(π) . Докажите, что a) sgn(f ◦ g) = sgn(f) · sgn(g); б) sgn(π) = (−1)d(π) ;

18*. Докажите, что знак перестановки из Sn можно определить за Cn операций, где C – константа. У к а з а н и е. Примените пункт б) предыдущей задачи.

19. Перестановку назовем четной, если ее знак равен 1. Множество четных перестановок в Sn обозначим An. Остальные перестановки назовем нечетными. Докажите, что

а) произведение четных перестановок – четно, произведение нечетных перестановок – четно, а произведение четной на нечетную – нечетно;

б) четная перестановка разлагается в произведение всегда четного числа транспозиций, а нечетная – всегда нечетного;

в) порядок нечетной перестановки четен;

г) четных и нечетных перестановок в Sn поровну.

20. Четность перестановки, соответствующей положению маленьких кубиков в кубе Рубика, не меняется при его вращениях.

21*. В игре в пятнадцать нельзя позицию (1, 2, . . ., 14, 15) перевести в позицию (1, 2, . . . , 13, 15, 14).

23*. Любая четная позиция в игре в пятнадцать может быть получена из начальной позиции (1, 2, . . . , 14, 15).

24*. Испанский король решил перевесить портреты своих предшественников на круглой башне замка. Он хочет за один раз менять местами только два соседних портрета, но лишь в случае, если эти короли не правили сразу друг за другом. Расположения портретов, отличающиеся поворотом круга, он считает одинаковыми. Докажите, что при любом начальном положении портретов можно добиться любого другого их расположения.

25*. Некто, имеющий магнитофон старого образца (не кассетный), получил назад от приятеля свои 12 катушек намотанными в противоположные стороны. Сможет ли он, используя пустую 13-ю катушку, перемотать свои катушки в правильном порядке? Какой будет ответ, если число катушек равняется 11?

26*. В таблице m × n за один ход разрешается переставить в любом порядке числа любой строки или любого столбца. За какое наименьшее число ходов можно гарантированно получить произвольную заданную перестановку чисел в таблице?

27. Последовательность {xi } из n чисел назовем k-битонической, если x1 6 . . . 6 xk, xk+1 6 . . . 6 xn. Докажите, что ее можно переставить в монотонном порядке за Cn операций сравнения чисел и их транспозиции, где C – константа.

28*. (Быстрая сортировка слиянием.) Докажите, что любую последовательность {xi } из n чисел можно переставить в монотонном порядке за L(n) < Cn lg n операций сравнения чисел и их транспозиции, где C – константа.

У к а з а н и е. Разбейте массив пополам и отсортируйте в монотонном порядке каждую его часть. Тогда за 2L(n/2) операций получится n/2-битоническая последовательность, откуда имеем оценку L(n) 6 2L(n/2) + Cn. Если n 6 2k, то, итерируя это неравенство k раз,

находим, что L(n) 6 Cnk + C1n 6 C2n log2 n.

29*. Если последовательность {xi } есть перестановка чисел 1, . . . , n, то ее можно монотонно отсортировать за Cn операций.

У к а з а н и е. Разложите перестановку на циклы; циклы на транспозиции можно разложить как в задаче 2, используя только 2n операций записи в массив, после чего сортировка делается по полученному разложению за n операций транспозиции.

Глава II. Числа и группы

§ 2.1. Группа подстановок

Множество Sn всех перестановок множества En, рассматриваемое вместе с операцией умножения перестановок, называем далее группой

перестановок (или группой подстановок).

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

Определение 34. Подмножество G группы Sn называется подгруппой, если вместе с любыми подстановками π и τ оно содержит подстановки π−1 и π ◦ τ (подразумевается, что множество G не пусто).

Легко доказывается следующая

Теорема 25. Для любой подгруппы G группы Sn выполняются следующие утверждения:

(i)существует элемент ε G, для которого при любом элементе

πиз G

π◦ ε = ε ◦ π;

(ii)для любых элементов π1, π2, π3 из G справедливо равенство

π1 ◦ (π2 ◦ π3) = (π1 ◦ π2) ◦ π3;

(iii) для любого элемента π из G найдется элемент τ из G такой, что

π◦ τ = τ ◦ π = ε.

До к а з а т е л ь с т в о. (i) В качестве ε можно взять элемент π ◦ π−1, где π – произвольный элемент из G.

(ii)Утверждение следует из теоремы 21.

(iii) В качестве элемента τ можно взять π−1.

Упражнение 24. 1. Множество перестановок {ε, π, π2, . . . , πk−1} – подгруппа, если k – порядок подстановки π.

2. Множества {ε} и Sn – подгруппы в группе Sn.

Пусть – граф с множеством вершин En = {1, 2, . . . , n}. По определению задается множеством неупорядоченных пар {i, j}, называемых