50th Mathematical Olympiad in Ukraine, Fourth Round (March 24, 2010)

Answer: a) not always; b) always possible.

If we consider $5$ consecutive elements, then from combination $12345$ we can get the following: $$12345\to 14523\to 23514\to 51234\to 53412\to 12453.$$ Last three permutations were cyclically rearranged, so, similarly, we can get three numbers $12534$. If we make symmetric permutations, then we can also permute first three elements of our five numbers: $$12345\to 34125\to 25134\to 23451\to 45231\to 31245.$$ Consider some four positions with numbers $1001$-$1004$, for example. We first locate $1$, $2$, $3$, ..., $1000$. The following shows how this can be done on the example of $500$. Let us suppose that numbers $1$-$499$ are already on their positions. Further we will not touch their permutations. If $500$ is next right from $499$ (on its position), everything is done. If $500$ is on the last position or $n$-labeled, then we swap positions of pairs that occupy positions with numbers $(n-3,n-2)$ and $(n-1,n)$ and $500$ is already not on the last position. If $500$ is on one position after $499$ (labeled as $501$), then we change positions of pairs with following labels at first: $(500,501)$ and $(502,503)$. Let us suppose that $500$ is already on some position $k\in \{502,503,...,n-1\}$, then we are swapping positions of pairs labeled as: $(500,501)$ and $(k,k+1)$ and number $500$ is taking its position. So we will place on their seats all the numbers $1$-$1000$. After this, we similarly symmetrical interchange places of numbers $1005$-$n$. That means that we always can get next permutation:

$1$, $2$, ..., $1000$, $a$, $b$, $c$, $d$, $1005$, $1006$, ..., $n$,

where the set of numbers $(a,b,c,d)$ is some permutation of numbers $(1001,1002,1003,1004)$. Let's see what permutations of $(a,b,c,d)$ we can get. There are just $24$ of them. If we will take in attention next $5$ numbers $(1000,a,b,c,d)$, then using the scheme above we will gain also: $(1000,a,c,d,b)$ and $(1000,a,d,b,c)$. If we will add right-side $1005$ to gained sets of four numbers $(a,b,c,d)$, $(a,c,d,b)$ and $(a,d,b,c)$ and use the scheme above, so we will obtain next permutations: $(b,c,a,d)$, $(c,a,b,d)$, $(c,d,a,b)$, $(d,a,c,b)$, $(d,b,a,c)$, $(b,a,d,c)$. Apply again the scheme to some of obtained permutations and we will get another $3$ variants: $b,d,c,a$, $c,b,d,a$ and $d,c,b,a$. So, we could get $12$ out of $24$. We now have to show that to arrange remaining $12$ numbers in ascending order is impossible.

For any permutation of numbers $1$, $2$, ..., $n$ call as inversion the case when a larger number is left of a smaller, for example the position of $5$ numbers $23514$ has an inversion: $(2,1)$, $(3,1)$, $(5,1)$ and $(5,4)$. Call the quantity of such inversions as "position invariant". Let's show that after performing any authorized operation, the invariant of positions varies by a number which is divisible by $2$. Let us suppose that we have changed numbers $(a,b)$ and $(c,d)$, that occupied positions $(k,k+1)$ and $(l,l+1)$, $k<l$. Then the quantity of inversions will not change after permutation. We have only mentioned inversions associated with numbers located on positions $1$, $2$, ..., $(k-1)$ and $(l+2)$, $(l+3)$, ..., $n$. That means that the quantity of inversions is constant. The quantity of inversions that use the numbers on positions $(k+2)$, $(k+3)$, ..., $(l-1)$ is not changing relative to each other. But if we consider some number $e$, which occupies one of mentioned positions, then with attention to each of those pairs of numbers $(a,b)$ and $(c,d)$, that are transposed, it will change. And this is changing necessarily from $1$ to $0$ or vice versa from $0$ to $1$. Hence the total quantity of changes will be even, so the parity of position invariant will not change. And about the numbers $a$, $b$, $c$, $d$, behind $a$ and $b$, and $c$ and $d$ nothing is changing and behind all other pairs ($4$ at all) will be the same situation. So, the parity of inversions will stay the same.

So, it's easy to understand that we would not move on from position $1$, $2$, $3$, $4$, ..., $n$ (invariant is equal to $0$) to position $2$, $1$, $3$, $4$, $5$, ..., $n$ (invariant is $1$). So we would not obtain other $12$ permutations inside of $a$, $b$, $c$, $d$ permutation.

But all this applies only to try to arrange the numbers in ascending order. Completely the same way you can try to arrange them in descending order. As we see, all the positions were broken into two large groups (with even and odd invariant), that cannot be translated.

Let's count the invariant of such a position: $n$, $n-1$, $n-2$, ..., $3$, $2$, $1$. Every pair here is an inversion, so their total amount is $C_n^2=\frac{n(n-1)}{2}$. If it's an even number, then both of monotone positions locate in the same half and we can transform them between each other. But we cannot get all the positions in general. If this number is odd, vice versa, then any start position with its invariant would be transformed into increasing or decreasing one. So, we just have to find the parity of number $C_n^2=\frac{n(n-1)}{2}$. So if $n$ and $n-1$ have different parity, then that number will be even if one of them is divisible by $4$. That means that $n=4m$ or $n=4m+1$, else it's odd. Hence for $n=2009\equiv 1(\mathrm{mod}4)$ not all the positions could be transformed one to another. And for $n=2010\equiv 2(\mathrm{mod}4)$ from any position with the same scheme we can obtain increasing or decreasing set of numbers instead.