Банк задач по математике

Задача 1.7.1

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

\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ 3 & 5 & 10 & 8 & 11 & 14 & 15 & 6 & 13 & 1 & 4 & 9 & 7 & 2 & 12 \end{pmatrix}.

Через сколько минут все школьники впервые окажутся на своих первоначальных местах?

?

Примечание.

?

Перестановкой множества называется запись элементов этого множества в произвольном порядке. Более строго, перестановкой множества называется взаимно однозначное отображение этого множества на себя (т.е. биекция). Перестановку $f$ удобно изображать в виде ориентированного графа, вершины которого — элементы множества, а рёбра идут из вершины $a_k$ в вершину $f(a_k)$ . Перестановка множества $\{ a_1, a_2, \ldots , a_n\}$ , переводящая $a_k$ в $f(a_k)$ , записывается в виде

\begin{pmatrix} a_1 & a_2 & \ldots & a_n \\ f(a_1) & f(a_2) & \ldots & f(a_n) \end{pmatrix};

обычно $a_k = k$ для всех $k \in \mathscr {R}_n$ . Обратной к $f$ перестановкой называется перестановка $f^{-1}$ , записывающаяся в виде

\begin{pmatrix} f(a_1) & f(a_2) & \ldots & f(a_n) \\ a_1 & a_2 & \ldots & a_n \end{pmatrix}.

Циклом (длины $n$ ) называется перестановка вида

\begin{pmatrix} a_1 & a_2 & \ldots & a_{n-1} & a_n \\ a_2 & a_3 & \ldots & a_n & a_1 \end{pmatrix}.

Эта перестановка коротко обозначается через $(a_1a_2\ldots a_n)$ .

Композицией перестановок $f$ и $g$ называется перестановка $f\circ g$ , определённая формулой $(f\circ g)(x) := f(g(x))$ .

Задача 1.7.2

Найдите композиции перестановок на множестве цифр

?

(1)

$(12)\circ (13)$ ;

(2)

$(12)\circ (23)$ ;

(3)

$(23)\circ (12)$ ;

(4)

$(123)\circ (132)$ ;

(5)

$(12)\circ (13)\circ (12)$ ;

(6)

$(12345)\circ (12)$ ;

(7)

$(12345)\circ (56789)$ .

Ответ дайте в виде композиции непересекающихся циклов. Например, $(123)\circ (234) = (12)\circ (34)$ .

Далее знак композиции опускается.

Задача 1.7.3

Для любой перестановки $f$ существует $k>0$ , для которого $f^k = \mathrm{id}$ (т.е. для которого после $k$ -кратного применения перестановки $f$ каждый элемент перейдёт в себя).

Порядком перестановки $f$ называется наименьшее $k>0$ , для которого $f^k = \mathrm{id}$ .

?

Задача 1.7.4

Существуют ли перестановки 9-элементного множества порядков $7, 10, 12, 11$ ?

?

Задача 1.7.5

Чему равен порядок композиции непересекающихся циклов из $n_1, \ldots , n_k$ элементов соответственно?

Перестановки $(n_1+\ldots +n_k)$ -элементного множества из задачи 1.7.5 называются перестановками типа $\langle n_1, \ldots , n_k \rangle$ . Например, перестановки $(14)(253)$ , $(15)(432)$ типа $\langle 2,3 \rangle$ , а перестановка $(1)(3)(245)$ — другого типа $\langle 1,1,3 \rangle$ .

?

Задача 1.7.6

(1)(2)(3)

Найдите число перестановок типа

?

(1)

$\langle 2,3 \rangle$ ;

(2)

$\langle 3,3 \rangle$ ;

(3)

$\langle 1,2,3,4 \rangle$ .

Задача 1.7.7

(1)(2)(3)

Любая перестановка представляется в виде композиции

?

(1)

непересекающихся циклов;

(2)

транспозиций, т.е. перестановок, каждая из которых меняет местами некоторые два элемента, а остальные оставляет на месте (иными словами, циклов длины 2);

(3)

транспозиций $(1i)$ , $i=2,3,\ldots ,n$ .

Задача 1.7.8

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

Перестановки $a$ и $b$ называются сопряжёнными, если $a = xbx^{-1}$ для некоторой перестановки $x$ .

?

Задача 1.7.9

(1)(2)(3)

?

(1)

Перестановки $a$ и $b$ сопряжены тогда и только тогда, когда их типы одинаковы.

(2)

Пусть $a$ и $x$ — произвольные перестановки $n$ -элементного множества. Тогда

xax^{-1} = \begin{pmatrix} x(1) & x(2) & \ldots & x(n) \\ x(a(1)) & x(a(2)) & \ldots & x(a(n)) \end{pmatrix}.

Иными словами, циклическое разложение перестановки $xax^{-1}$ получается из циклического разложения перестановки $a$ заменой каждого элемента на его $x$ -образ: если $a = \displaystyle \prod_{j=1}^{q}(i_{j1},i_{j2},\ldots ,i_{js_j})$ , то

xax^{-1} = \prod _{j=1}^{q}(x(i_{j1}),x(i_{j2}),\ldots ,x(i_{js_j})).

(3)

Найдите $gf^{-1}g^{-1}f$ для $f := (1,2,\ldots ,N)$ и $g := (N,N+1,\ldots ,L)$ .