This is combinatorics, not number theory. But anyway: It is probably about $log_2 n$ (ceiling or floor) since you can split the sequence into two halves (or almost halves in case n is odd) and then interchange these two halves. Then just do the same for each half etc.

LaTeX knows \log. But this is probably the wrong heuristic: in order to get a logarithmic bound, you'd have to be able to do both sides simultaneously, but that's not possible with this move. It's obvious how to get $n - 1$ in a variety of different ways, and it's easy to see that this is optimal for small $n$, but I don't immediately see what invariant to use to get a matching lower bound. (For example, it's natural to hope that descents would be the right invariant, but they aren't; certain applications of the move can decrease the number of descents by 2.)

JBL wrote: It's obvious how to get $n - 1$ in a variety of different ways, and it's easy to see that this is optimal for small $n$. Already for $n=6$ and $n=7$ (and thus for all $n\ge 7$), there are solutions with $n-2$ steps, see attached. So as you say, the exact number may be hard to find. Obviously, $\frac n2<f(n)\le n-2$ for $n>5$. Out of the blue, I would guess though $\lim_{n\to\infty}\frac{f(n)}n=1.$

Attachments:

In fact, $n=5$ has a solution in $3$ moves: 12345 -> 14523 -> 52143 -> 54321 And $n=7$ has a solution in $4$ moves: 1234567 -> 1567234 -> 7215634 -> 7632154 -> 7654321 Let $f:\mathbb{N}\to \mathbb{N}$ be the desired minimal value. Then suppose in the minimum sequence of moves there is a swap of two consecutive blocks, $A$ and $B$, one of which has only one element, call it $x$. Then delete $x$ from the sequence and the same moves take $(1,2,...,x-1,x+1,...n) \to (n,n-1,...,x+1,x-1,...,1)$. Furthermore, one of the moves did nothing to the sequence (i.e. the one that swapped $x$ with another block), so by induction there must be at least $f(n-1)+1$ moves in the sequence. Now let's assume that the moves only swap blocks of length $\ge 2$. Notice that in a block switch only three consecutive pairs of terms change. For example in $(a_1,...a_i ,\underbrace{a_{i+1},... a_{i+p},}_{A} \underbrace{a_{i+p+1},...,a_{i+q},}_{B}...,a_{n}) $ Only $(a_i,a_{i+1})$, $(a_{i+p},a_{i+p+1})$ and $(a_{i+q},a_{i+q+1})$ are affected, call these the cricitical pairs in the swap. Then in order to swap $(i+1,i) \to (i,i+1)$, the pair must be a critical pair at least twice (because swapping the pair directly would involve a block of one element). Since there are $n-1$ pairs that need to be swapped we need at least $\lceil \textstyle\frac{2}{3} (n-1) \rceil $ moves. Except for $n=4$ this bound is tight for at least $n\le 9$. Maybe a clever construction can show that it's tight in general.

if $n=2k$ then$ k+1$ is the answer and if $n=2k+1$ then answer is again $k+1$, I found the official solution, if you want I can post it here

it would be helpful if u did so

Altunshukurlu wrote: if $n=2k$ then$ k+1$ is the answer and if $n=2k+1$ then answer is again $k+1$, I found the official solution, if you want I can post it here Can you please post the solution then?

If what he said about the answer is true then I have found a proof for the necessary condition. We need $(n+1)/2$ moves. We consider a maximal set consisting of consecutive elements of a permutation such that the elements are decreasing, and we call it an inverse block. If the elements are increasing then we call it direct block. So if the permutation is $7245631$ then the inverse blocks are $72, 4,5,631$ and the direct blocks are $7,2,456,3,1$. We show that each move increases the number of inverse blocks by at most $2$. Let $a,(A,\ldots,b),(B,\ldots,c),C$ be some consecutive elements of a permutation, and the parentheses are the two blocks we are going to swap. We count the number of end points of inverse blocks. After the swap we can only have $3$ possible new end points, namely $a,b,c$. If any of them was an endpoint before then the number of endpoints increases by at most $2$. If none of them was an endpoint, then $ A < a, B < b, C < c$. Then if $x$ is the max element among $a,b,c$ then after the swap it is still not an endpoint, since it is bigger than it's next element, which is one of $A,B,C$. Thus the number of endpoints also increases by at most $2$ in this case. From the permutation $n...21$, the first move increases the number of inverse blocks by only $1$. By symmetry, the last move to $12...n$ also increases the number of inverse blocks by $1$. The intermediate moves increases the number of inverse blocks from $2$ to $n-1$. Hence there are at least $2 + (n-3)/2 = (n+1)/2$ moves. It remains to give the construction that achieves equality.

Sure, but I also showed that you need at least $\lceil \textstyle\frac{2}{3}(n-1) \rceil$ moves, which is a tighter bound (of course there could be a flaw in my proof). So what we really need is a construction.

Okay, by looking at the examples above, I think I have found a construction. For $n=2k+1$, first swap $23...(k+1)$ with $(k+2)...n$. Then repeatly move the pairs $(2k+3-j,j)$ so that the first element falls into the right position, starting with the pair $(2k+1,2)$ and ends with the pair $(k+2,k+1)$. For $n=2k+2$, we have one more move for one more element so it is easy. Example for $n=9$: $123456789 - 167892345 - 921678345 - 983216745 - 987432165 - 987654321$ in five moves.

What a hard problem !!

Key idea is to observe that number of pairs $(a_i,a_{i+1})$ s.t. $a_{i}< a_{i+1}$ increases by 2 at most and we have 0 at start and n-1 at the end.

kamil9876 wrote: This is combinatorics, not number theory. But anyway: It is probably about $log_2 n$ (ceiling or floor) since you can split the sequence into two halves (or almost halves in case n is odd) and then interchange these two halves. Then just do the same for each half etc. Thats mistake cs u cant do at 2 part together in a one time

Altunshukurlu wrote: if $n=2k$ then$ k+1$ is the answer and if $n=2k+1$ then answer is again $k+1$, I found the official solution, if you want I can post it here What about if n=2? That means k=1 and k+1=2 is the answer, but it is clearly 1.

ocha wrote: Altunshukurlu wrote: if $n=2k$ then$ k+1$ is the answer and if $n=2k+1$ then answer is again $k+1$, I found the official solution, if you want I can post it here Can you please post the solution then? The solution is not complete. The example they brought doesn't work for many numbers and doesn't fit into the answer they got. It is true that the answer is greater or equal to [(n+1)/2]. But that doesn't mean the answer is exactly that number.

Hello,can someone share the complete solution,please?

We claim the desired number of interchanges is $\lceil\frac{n+1}2\rceil$. Consider the number of pairs $(a_i, a_{i+1})$ such that $a_i < a_{i + 1}$. Call such pairs good. In the initial sequence the number of good pairs is $0$. In the final sequence the number of good pairs is $n - 1$. Lemma 1: In the first interchange we can only increase the number of good pairs by $1$. Proof: Suppose that in the sequence $..., k, x, ..., y, a, ..., b, m, ...$ we want to interchange blocks $x, ..., y$ and $a, ..., b$. Because we haven't made any interchanges yet, it holds $k > x > y > a > b > m$. After interchanging the two blocks, our sequence becomes $..., k, a, ..., b, x, ..., y, m, ...$. The only good pair of numbers created is $(b, x)$. Lemma 2: In each interchange, we can increase the number of good pairs by at most $2$. Proof: We will prove we can't increase the number of good pairs by $3$ or more in a single interchange. Consider the sequence $..., k, x, ..., y, a, ..., b, m, ...$ where we want to interchange the blocks $x, ..., y$ and $a, ..., b$. After interchanging the blocks our sequence becomes $..., k, a, ..., b, x, ..., y, m, ...$. Note there were only $3$ new pairs created. Suppose, for the sake of contradiction, $(k, a)$, $(b, x)$, $(y, m)$ are good pairs and none of $(k, x)$, $(y, a)$, $(b, m)$ are good pairs (that would imply that the number of good pairs has increased by $3$). The following inequalities all have to hold: $k > x$, $y > a$, $b > m$, $a > k$, $x > b$, $m > y$. Summing the first and the fourth inequality yields $a > x$. Summing up all other inequalities yields $x > a$. We have reached a contradiction. From Lemma 1 and Lemma 2 we conclude the minimal number of needed interchanges is $\lceil\frac{n + 1}2\rceil$. This sequence of interchanges gives the minimal number (but note the quoted post describes getting $n, n -1, ..., 2, 1$ from $1, 2, ..., n - 1, n$ and the proof above regards the opposite): ninjaturtle wrote: Okay, by looking at the examples above, I think I have found a construction. For $n=2k+1$, first swap $23...(k+1)$ with $(k+2)...n$. Then repeatly move the pairs $(2k+3-j,j)$ so that the first element falls into the right position, starting with the pair $(2k+1,2)$ and ends with the pair $(k+2,k+1)$. For $n=2k+2$, we have one more move for one more element so it is easy. Example for $n=9$: $123456789 - 167892345 - 921678345 - 983216745 - 987432165 - 987654321$ in five moves.

can we only swap an equal number of numbers in a block or can the block be unequal (eg: is (5,4,3,2,1) |-> ( 3,2,1,5,4) a legal move, where we swapped "5,4" and "3,2,1" )?

QuantomaticGuy wrote: can we only swap an equal number of numbers in a block or can the block be unequal (eg: is (5,4,3,2,1) |-> ( 3,2,1,5,4) a legal move, where we swapped "5,4" and "3,2,1" )? i think they can be unequal, as many of the above solutions used this fact while considering small cases

Altunshukurlu wrote: Given a permutation $(a_{1}, a_{1},...,a_{n})$ of the numbers $1, 2,...,n$ one may interchange any two consecutive "blocks" - that is, one may transform ($a_{1}, a_{2},...,a_{i}$,$\underbrace {a_{i+1},... a_{i+p},}_{A} $ $ \underbrace{a_{i+p+1},...,a_{i+q},}_{B}...,a_{n}) $ into $ (a_{1}, a_{2},...,a_{i},$ $ \underbrace {a_{i+p+1},...,a_{i+q},}_{B} $ $ \underbrace {a_{i+1},... a_{i+p}}_{A}$$,...,a_{n}) $ by interchanging the "blocks" $A$ and $B$. Find the least number of such changes which are needed to transform $(n, n-1,...,1)$ into $(1,2,...,n)$ The answer is $$\begin{cases} k+1 \text{ if } n=2k \\ k+1 \text{ if } n=2k+1 \end{cases}$$moves. We induct to show the result;when there $n=2$ we swap blocks $2$ and $1$. Suppose there are $n$ coins then we swap the blocks $\{1,2,.............,n-1\}$ and $n$ then $\;\;\;\; \bullet$ If $n-1=2k+1$ is odd then we would need $k+1+1=k+2$ moves. $\;\;\;\; \bullet$ If $n-1=2(k+1)$ then we would need $k+1+1=k+2$ moves,as required.$\blacksquare$

Answer : Minimum number of moves is $\lceil \frac{n+1}{2} \rceil$ We define sequence me $\to$ $a_1,a_2,a_3, \dots $ where $a_i$ is placed in the $i^{th}$ place , $a_1 > a_2 > a_3 > \dots $ and $a_i \in \mathbb{Z^{+}}$ We call a pair { $a_i , a_j$ } good if $a_i < a_j$ and $a_i$ is just before $a_j$ . ( $\dots a_i , a_j , \dots $ ) We define $\varphi (i)$ to be the swapping of consecutive blocks in the $i^{th}$ round $\varphi( \text{last})$ is defined when the result of this swapping leads to $a_1<a_2<a_3 < \dots $ Note : 1st round is the 1st time swapping of block took place , 2nd round is the 2nd time swapping of block took place and so on $\dots $ Claim $ : \varphi(i)$ for ($1<i<$ last) increase the number of good pairs atmost by 2 in me $Proof-$ \[ { \dots a_k , a_l , \dots , a_m,a_n , \dots , a_o,a_p , \dots } \] Lets say $\{a_k,a_l\},\{a_m,a_n\} , \{a_o,a_p\}$ are not good pairs and the above sequence is a result of $\varphi(s)$ By $\varphi(s+1)$ on blocks $a_l , \dots , a_m$ and $a_n, \dots , a_o$ in the above sequence \[ { \dots a_k , a_n , \dots , a_o,a_l , \dots , a_m,a_p , \dots } \] FTSOC lets say $\varphi(s+1)$ forms 3 good pairs $\{a_k,a_n\} , \{a_o,a_l\} , \{a_m,a_p\}$ Now as they are good pairs we get $a_k+a_o+a_m < a_n+a_l+a_p$ which contradicts the fact that $\{a_k,a_l\},\{a_m,a_n\} , \{a_o,a_p\}$ are not good pairs . Hence we are don with our proof Claim $ : \varphi (1)$ and $\varphi ( \text{ last})$ increases the number of good pairs by 1 in me $Proof -$ \[ {a_1 \dots a_k , a_l , \dots , a_m,a_n , \dots , a_o,a_p , \dots } \]By $\varphi(1)$ on blocks $a_l , \dots , a_m$ and $a_n, \dots , a_o$ \[ {a_1 \dots a_k , a_n , \dots , a_o,a_l , \dots , a_m,a_p , \dots } \]The only good pair is $\{ a_o,a_j \}$ Lets take the result of $\varphi( \text{last} - 1)$ to be \[ { \dots a_k , a_l , \dots , a_m,a_n , \dots , a_o,a_p , \dots } \]By $\varphi( \text{last})$ on the above sequence \[ { \dots a_k , a_n , \dots , a_o,a_l , \dots , a_m,a_p , \dots } \]Now we have $a_k<a_n<a_0<a_l<a_m <a_p$ Hence the only good pair is $\{a_o,a_j\}$ and we are done \[ \underbrace{1,2,3,4, \dots n-1,n}_{\text{n-1 good pairs}} \] \[ \underbrace{n-1,n-2,n-3, \dots 2,1}_{\text{0 good pairs}} \] Using the above two claims we get the minimum number of moves to be $\lceil \frac{n+1}{2} \rceil$

The following is from "Mathematical Olympiads 2000–2001 -- Problems and Solutions From Around the World" by Titu Andreescu, Zuming Feng, and George Lee, Jr. The answer is $0$ for $n=1$, $1$ for $n=2$, and $\left\lceil \tfrac 12 (n+1)\right\rceil$ for $n\ge 3$. The cases of $n=1$ and $n=2$ are not difficult to show, so assume from now on that $n\ge 3$. We first show that $\left\lceil \tfrac 12 (n+1)\right\rceil$ is possible. If $n$ is even, then write $n=2m$, and for the first $m$ moves, swap block $a_i , \ldots , a_{i+m-2}$ with $a_{i+m-1}, \ldots , a_{i+m}$ for $i=1,2,\ldots , m$. After this, the sequence is\[m, m-1, m-2, \ldots , 1; \ n, n-1, n-2, \ldots , m+1.\]Next swap block $a_{1},\ldots , a_m$ with $a_{m+1},\ldots , a_n$. The total number of moves is $m + 1$, as desired. If $n$ is odd, then write $n=2m+1$, and for the first $m$ moves, swap block $a_i , \ldots , a_{i+m-1}$ with $a_{i+m}, a_{i+m+1}$ for $i=1,2,\ldots , m$. After this, the sequence is\[m+1, m,m-1, \ldots , 2; \ n, n-1, n-2, \ldots , m+2; \ 1.\]Next swap block $a_{1},\ldots , a_m$ with $a_{m+1},\ldots , a_{2m}$. The total number of moves is $m + 1$, as desired. Now we show that $\left\lceil \tfrac 12 (n+1)\right\rceil$ is the minimum possible number of moves. Consider the number $X$ of neighboring terms of the sequence that are in increasing order. For $n \ge 3$, at least 2 swaps are necessary. The first and last swaps increase $X$ by exactly one. For any other swap, say from\[\ldots , a, \underbrace{b,\ldots , e,} \underbrace{f,\ldots , c,} d,\ldots ,\]to\[\ldots , a, \underbrace{f,\ldots , c,} \underbrace{b,\ldots , e,} d,\ldots ,\]if $X$ were to increase by 3, then it would have to be the case that \[a > b, \ b > c, \ c > d, \ d > e, \ e > f, \ f > a,\]which is not possible. Therefore, $X$ increases by at most 2 with any given move. Because $X$ starts at 0 and must finish at $n - 1$, it is not difficult to see that the number of moves must be at least $\left\lceil \tfrac 12 (n+1)\right\rceil$.

The answer is $\left\lceil \tfrac 12 (n+1)\right\rceil$. First, we can show that this answer works. This could work by induction. let's say all of the cases about $n<2m$ work. At here, if $n$ is even, we can swap the first $m+1$ numbers and use induction. If $N$ is odd we could just swap the same first $m$ and the second $m+1$ and use induction also. Now let's show that this answer is the minimum. Let $a$ be the number of consecutive blocks. If we swap 2 consecutive blocks that contain the ends, we will get $a$ increased by 1. Also if we swap 2 blocks that both do not contain the ends $a$ increase by 3. And it could not increase by 3. so it has to increase by at most 2 and because it has to be $n-1$ at the end, the minimum moves are $\left\lceil \tfrac 12 (n+1)\right\rceil$.