
Problem 3. For a permutation $a_{1}, a_{2}, \ldots a_{n}$ of the numbers $1,2 \ldots n$ it is allowed to change the places of any two consecutive blocks, i.e. from

$a_{1}, \ldots, a_{i}, \underbrace{a_{i+1}, a_{i+2} \ldots, a_{i+p}}_{A}, \underbrace{a_{i+p+1}, a_{i+p+2} \ldots, a_{i+q}}_{B}, a_{i+q+1}, \ldots, a_{n}$ by replacing $A$ and $B$ one can obtain $a_{1}, \ldots, a_{i}, \underbrace{a_{i+p+1}, a_{i+p+2} \ldots, a_{i+q}}_{B}, \underbrace{a_{i+1}, a_{i+2} \ldots, a_{i+p}}_{A}, a_{i+q+1}, \ldots, a_{n}$.

Find the least number of such changes after which from $n, n-$ $1, \ldots 1$ one can obtain $1,2, \ldots n$.


Solution: Call the change of two blocks a move. We shall prove that the least number of moves such that from $n, n-1, \ldots 1$ one can
obtain $1,2, \ldots n$ is $\left\lceil\frac{n+1}{2}\right\rceil$.

Consider the number of pairs $a_{i}, a_{i+1}$ such that $a_{i}a$, $b>c$ and $d>q$ we get $pa+c+q$ and adding the last three implies $p+b+d<a+c+q$, a contradiction. Therefore a move changes the number of pairs $a_{i}, a_{i+1}$ for which $a_{i}<a_{i+1}$ at most by two. It is easily seen that the first and the last moves change this number by one. Therefore if $x$ is desired number we have $2+2(x-2) \geq n-1$ which implies $x \geq\left\lceil\frac{n+1}{2}\right\rceil$. It remaines to find a sequence of $\left\lceil\frac{n+1}{2}\right\rceil$ moves such that from $n, n-1, \ldots 2,1$ we get $1,2, \ldots, n-1, n$. Let $n$ be even number, i.e. $n=2 k$. Number the positions from right to left by $1,2 \ldots n$. First change the places of the blocks from positions $1,2 \ldots, k-1$ and $k, k+1$. Next, change the places of the blocks from positions $2,3 \ldots, k$ and $k+1, k+2$. Third, change the blocks $3,4 \ldots, k+1$ and $k+2, k+3$ and so on. On the $k$-th step change the blocks from positions $k, k+1 \ldots, 2 k-2$ and $2 k-1,2 k$. As a result we obtain $k+1, k+2, \ldots, 2 k, 1,2, \ldots, k$. The
last change is $1,2, \ldots, k$ and $k+1, k+2 \ldots, 2 k$. When $n$ is odd, i.e. $n=2 k+1$ the first change is of the blocks from positions $1,2, \ldots, k$ and $k+1, k+2$ after that $2,3, \ldots, k+1$ and $k+2, k+3$ and so on. The last $k+1$ change is $1,2 \ldots k$ and $k+1, \ldots, 2 k$ and we obtain $1,2, \ldots, 2 k+1$.
