Math Problems Vault

Problem 1.8.1

(1)(2)(3)

?

(1)

Can every permutation be represented as a composition of several cycles of length 3?

(2)

Can every permutation be represented as a composition of an even number of transpositions?

(3)

The 15 puzzle. A square box of size $4\times 4$ holds 15 square tiles of size $1\times 1$ numbered $1,2,\ldots ,15$ , and one place is left empty. Initially the tiles are arranged as in the figure on the right. Is it possible, by successively sliding tiles into the empty place, to obtain the arrangement of tiles in the figure on the left?

\begin{array}{|c|c|c|c|} \hline 1 & 2 & 3 & 4 \\ \hline 5 & 6 & 7 & 8 \\ \hline 9 & 10 & 11 & 12 \\ \hline 13 & 14 & 15 & * \\ \end{array} \qquad \qquad \begin{array}{|c|c|c|c|} \hline 1 & 2 & 3 & 4 \\ \hline 5 & 6 & 7 & 8 \\ \hline 9 & 10 & 11 & 12 \\ \hline 13 & 15 & 14 & * \\ \end{array}

Problem 1.8.2

(1)(2)

How does the parity of a cycle of length $n$ depend

?

(1)

on the order in which the elements of the cycle follow one another?

(2)

on $n$ ?

Problem 1.8.3

(1)(2)

?

(1)

The composition of an even (odd) permutation and a transposition is odd (even).

(2)

How can one determine the parity of a composition of permutations, knowing the parities of the factors?

Problem 1.8.4

(1)(2)(3)

Each of the following conditions is equivalent to the permutation being even:

?

(1)

The permutation can be represented as a composition of an even number of transpositions.

(2)

Every representation of the permutation as a composition of transpositions contains an even number of them.

(3)

The permutation can be represented as a composition of several cycles of length 3.

Problem 1.8.5

(1)(2)

?

(1)

Which permutations of an $n$ -element set are more numerous: even or odd ones?

(2)

What is the minimal number of transpositions into which a permutation of an $n$ -element set consisting of $k$ disjoint cycles of length greater than 1 can be decomposed?

Problem 1.8.6

(1)(2)(3)

A permutation $x$ is generated by permutations $p_1, p_2, \ldots , p_k$ if $x = x_1x_2\ldots x_n$ , where for every $1 \leqslant i \leqslant n$ there exists $1 \leqslant j \leqslant k$ such that $x_i = p_j$ .

?

(1)

The set of all even permutations of a finite set is generated by any pair of cycles (each of length at least 2) that have exactly one common element and contain all elements of the set.

(2)

If $nk$ is even, $n>1$ , $k>1$ , then the cycles $(1\ldots n)$ and $(n \ldots n+k-1)$ generate all permutations of the set $\mathscr {R}_{n+k-1}$ .

(3)

If $nk$ is odd, $n>1$ , $k>1$ , then the cycles $(1\ldots n)$ and $(n\ldots n+k-1)$ generate all even permutations of the set $\mathscr {R}_{n+k-1}$ and only them.