Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

Definitions: Let $a_{n}$ be the maximum number of moves required to turn a permutation of $1,2, \dots ,n$ into increasing order. Let $X$ (given any arrangement) be the number of pairs in decreasing (i.e., the wrong) order. We note that $0 \leq X \leq^{n}C_{2}$, that the cards are in increasing order iff $X=0$ (and decreasing order iff $X=^{n}C_{2}$), and that given any arrangement not in either of thee two states it is possible to increase or decrease $X$ by 1, by changing around two adjacent cards. Lemma 1: $a_{4}=3$ Here if $X \leq 3$, then we can reduce it to 0 by a sequence of changing around adjacent cards. If $X \geq 4$, we can increase it to 6 in 2 moves, then swap the cards around. Lemma 2: $a_{5}=4$ If $X \leq 4$, then we can reduce it to 0 by changing one pair of cards at a time. If $X \geq 7$, then we can increase it to 10 similarly and then swap all the cards around If $X= 5$ and there are three cards in either decreasing or increasing order, then we can swap their order around, at which point $X \leq 3$ or $X \geq 8$. From here we can finish as before, in only three moves. So we may assume that there are no consecutive three cards in increasing or decreasing order. Therefore the row of cards goes 'up-down-up-down' or 'down-up-down-up'. We can say that it goes 'down-up down-up' without loss of generality because an 'up-down-up-down' order is equivalent to one 'down-up-down-up' with the card 1 interchanged with 5 and 2 with 4. Let us call the first card $a$, the second $b$, and $c,d,e$ for the third, fourth and fifth cards. Clearly either $b=1$ or $d=1$, since $a,c > b$ and $c,e > d$. If $b=1$, then we begin by swapping $a$ and $b$ around, from which point we only have four cards to arrange, which takes 3 moves by Lemma 1. So we assume that $d=1$. Since $a,c > b$, $b=2$ or $3$. If $b=3$ then $e=5$ and we have two cases to consider: $43512$ and $53412$. We can check that these are possible in 4 moves. If $b=2$, then$e=$ one of $3,4,5$. If $e=5$ then we are done by Lemma 1. If $e=4$ or $3$, then there are 4 cases to consider: $32514 52314$ $42513$ $52413$. We can easily check that these are possible in 4 moves. Hence any arrangement of $1,2,3,4,5$ can be made increasing in 4 moves, that is $a_{5}=4$ Lemma 3: $a_{n}\leq a_{n-1}+2$ Suppose we have a permutation of $1,2 \dots n$, and that the last card is $k$. We arrange the other $n-1$ cards into increasing order: this takes $a_{n-1}$ moves at most. We then have $1,2, \dots (k-1),(k+1) \dots n,k$. We can swap $(k+1), \dots n$ around, at which point the arrangement is $1,2, \dots (k-1),n,(n-1) \dots k$. Then we swap the bit from $n$ to $k$ around. Thus we have arranged $n$ cards into increasing order in $a_{n-1}+2$ moves, proving this Lemma. We have that $a_{5}=4$, by Lemma 3 $a_{6}\leq 6$, $a_{7}\leq 8$, $a_{8}\leq 10$, $a_{9}\leq 12$. Therefore it takes at most 12 moves to arrange cards 1 to 9 in increasing order.

Edit: wrong solution used to be here.

You cannot bring $n$ to the beginning of the list with one move. Consider $n = 5$ with permutation $2,1,5,3,4$.

/spawn Define a move to be when we switch the order of a block. Note that it takes at most 3 moves to get a block of any 4 distinct integers to be strictly increasing or decreasing just by moving blocks with 2 numbers in them. So it takes at most 4 moves to get a block of 4 distinct integers to be strictly increasing. It also takes at most 4 moves to get a block of 4 distinct integers to be strictly decreasing. Also, note that there will always exist a block with 5 numbers such that 9 is either the first number in the block or the last number in the block. When reading left to right, if 9 is the first number of the block, then we want our entire sequence from 1 to 9 to be strictly decreasing. If 9 is the last number of the block, we want our entire sequence to be increasing. So it takes at most 4 moves to get such blocks of 5 into strictly increasing or decreasing order. Observe that if it takes a block with $k$ numbers $m$ moves to get it strictly in increasing or decreasing order, it will take $m+2$ moves to get a block of $k+1$ numbers that contains this entire $k$-block into strictly increasing or decreasing order. Without the loss of generality, suppose we have $a_1 , a_2, a_3, a_4, ..., a_k, a_{k+1}$ with the first $k$ terms in increasing order already and it took $m$ moves to get the sequence $a_1, a_2, a_3, ..., a_k$ into strictly increasing order. If $a_{k+1} > a_k$, we're done so suppose there exists an $a_i$ such that $a_{i-1} < a_{k+1} < a_i$ for some $1\le i \le k$ (if $i=1$, then this algorithm will work too). Then make a move on $a_i, a_{i+1}, a_{i+2}, ..., a_k$. Then the sequence will be $a_1, a_2, ... a_{i-2}, a_{i-1}, a_k, a_{k-1}, ..., a_{i+2}, a_{i+1}, a_i, a_{k+1}$. Make another move on the block that contains $a_k, a_{k-1}, ..., a_i, a_{k+1}$. Now our sequence is in strictly increasing order. Therefore, if it took 4 moves to get our special block with 5 numbers, then it takes 6 moves for 6 numbers, 8 moves for 7 numbers, 10 moves for 8 numbers, and 12 moves for 9 numbers. BAMO WHAMO COMBO WOMBO /despawn

We generalize and induct. We claim the answer is $2n - 6$ moves for general $n$ with $n \geq 5$. For the base case $n = 5$, observe that one of $5$, $1$ is in the positions $1, 2, 4, 5$. Thus we spend at most one move moving one of $5$, $1$ to an outermost number. WLOG we're moving $5$ to the first position. This guarantees that $1$ is in positions $3$ or $4$, since otherwise it would've been in one of the end positions to begin with. Consider the case where $1$ is in position $3$ to begin with. Notice that if the element in position $2$ is $2$ or $3$, then the number of inversions is at most $3$. Swapping two adjacent elements decreases the number of inversions by $1$, so this gives us $1234$ after at most $3$ moves and then we flip it to win. Otherwise we have $4$ in position $2$. However, here we begin with $54$, and we can obviously sort $321$ from any sequence of length $3$. Now consider the case where $1$ is in position $4$ to begin with. The idea now is that we look at reverse inversions so that the sequence tends towards $4321$; then we can just apply what we did for the previous case. Thus the base case is proven. Let $f(n)$ be the number of moves required to sort a sequence of length $n$. Then, the idea for going from $n - 1$ to $n$ is that we fix the first number, call it $i$. Then, after sorting, we get either $$\begin{align*} i, 1, 2, 3, \cdots, i - 1, i + 1, i + 2, \cdots n, \end{align*}$$ or we have $$\begin{align*} i, n, \cdots, i + 2, i + 1, i - 1, \cdots, 3, 2, 1. \end{align*}$$ Each of these costs $f(n - 1) = 2n - 8$ moves, so we just need to sort it to a sorted length $n$ sequence in $2$ moves. For the first case, just flip the sequence from $1$ to $i - 1$, then flip the sequence from $i, i - 1$, to $1$. For the second case, do something similar: flip $n$ to $i + 1$, then flip $i$ to $n$. This proves the inductive step, and so we have solved the problem.

Let $x_i$ denote the maximum number of moves it takes to put a permutation of $1,\ldots,i$ in ascending or descending order. We wish to show $x_9\leq 12$. Lemma: $x_{i+1}\leq x_i+2$ Proof: Consider a row of $i+1$ cards. Let $a$ the card that is last in the row. In $x_i$ or fewer moves, it is possible to put the first $i$ cards in order. WLOG assume they are in ascending order. Consider the (possible empty) set of cards including all cards greater than $a$. Since they are not equal to $a$, they are all in the first $i$, so they have been sorted, so they are in ascending order and form a block of consecutive cards. Reverse this block of cards. Then, all of the cards greater than or equal to $a$ form a block of consecutive cards, since the cards greater than $a$ are at the end of the first $i$ cards and $a$ comes right after. In addition, they are in decreasing order, because the cards greater than $a$ were in ascending order but were reversed, and $a$ comes after them. So, the block of cards greater than or equal to $a$ can be reversed, making all of the cards be in ascending order. So, $i+1$ cards can be sorted in $x_i+2$ moves or fewer. Lemma: $x_5\leq 4$ Proof: Firstly, we will show $x_3=1$. We know that at least one of $1$ and $3$ is in the first or last position. Assume WLOG $1$ is in the first position. Then the row is either $1, 2, 3$ or $1, 3, 2$. In the first case it's already in the right order and in the second case you can switch $3$ and $2$. Next, we claim that if there are 4 cards, it can be put in order in 2 or fewer moves if $1$ or $4$ is in the first or last place. Assume $1$ or $4$ is in the first or last place. WLOG, let $1$ be in the first place. Then, the $2, 3,$ and $4$ can be put in decreasing or increasing order in 1 move. Then, it is either $1, 2, 3, 4$ or $1, 4, 3, 2$, and in the second case you can reverse the last $3$. So, it takes at most $2$ moves to sort if $1$ or $4$ is in first or last place. We will now show that any row of 5 cards can be put in increasing or decreasing order in 4 or fewer moves. Either 1 or 5 is not in the middle spot. Assume WLOG 1 is not in the middle spot. Then, there is a block of 4 consecutive cards where 1 is first or last. So, that block can be sorted in 2 or fewer moves. Then, in a similar way to the previous lemma, the other card can be sorted in in 2 or fewer moves. So, the row of 5 cards can be sorted in 4 or fewer moves. So, $x_5\leq 4$. Putting these two lemmas together we get that $x_9\leq 12$.

Let $f(n)$ be the least number of moves needed to guarantee being able to make the numbers monotonic. Consider a list of $n+1$ numbers then take the first $n$ numbers and make it monotonic in at most $f(n)$ moves. If it is increasing let the sequence be $$1,2,\dots,k-1,k+1,\dots,n,k.$$ Then, flip $(k+1,\dots,n)$ and flip $(n,n-1,\dots,k)$ to get $1,2,\dots,n.$ If it is decreasing let the sequence be $$n,n-1,\dots,k+1,k-1,\dots,1,k.$$ Then, flip $(k-1,\dots,1)$ and then flip $(1,2,\dots,k)$ to get $n,n-1,\dots,1$ as desired. Thus, $f(n+1)\le f(n)+2.$ Note that $f(3)=1$ by checking the six cases. Thus, if there is a one or four in either of the two ends, we can do it in two moves. Otherwise, we can do it in three. Now, regardless of position of $5$ in the case with $5$ cards, if either one or four is one of the two ends, then $f(5)\le 4$ as desired. Otherwise, either two or five is one of the two ends. This is basically the same thing, so we're done.

ISL Marabot solve First, there is at least $3$ numbers in one side of $9$ and we can check $6$ cases to see that we can always sort these four numbers in two moves. Now,let there be $x,a_1,a_2,\dots a_k$ in the row in this order where $a_1,a_2,\dots a_k$ are sorted. Now if this is sorted with $x$ then we are done. Otherwise let, $x$ should lie after $a_{i}$, then we perform, $(x,a_1,\dots, a_i,a_{i+1},\dots, a_k)$ $\mapsto (x,a_i,\dots, a_1,a_{i+1},\dots, a_k)$ $\mapsto (a_1,\dots, a_i,x,a_{i+1},\dots, a_k)$ So we can sort them in $2$ moves. And we can do the similar process if $x$ lies after the sorted list. So we can add the rest $5$ numbers into the sorting list in at most $10$ moves. $\blacksquare$

First take the maximal size substring $S=a_1\dots a_s$ which has all increasing or all decreasing numbers. If $s=9$ we are done. If $s\ge 3$ then repeat the following algorithm: Take a value $a$ adjacent to $S$. WLOG suppose $a$ is to the left of $S$. Take $i$ such that $a_i<a<a_{i+1}$. Write $$(a,a_1,\dots,a_i)\to (a,a_i,\dots,a_1)\to (a_1,\dots,a_i,a)$$ thus sorting $a$ into $S$. Hence in two operations we can increase $s$ by one, and therefore we can achieve the goal in $12$ or less moves. It is important for later to note that if $a\in \{1,9\}$ then the above algorithm takes only one step. If $s=2$ then it suffices to show that in one move we can create a substring $S$ where: Its size is at least $3$. Numbers are all increasing or all decreasing. At least one of $1$ and $9$ is not in $S$. By the third condition and the observation made previously, we can complete the rest in $11$ or less moves, bringing the total to $12$ or less moves. Luckily this is simple. Evidently there exists a substring of size three $(1,x,y)$ or $(y,x,1)$ where $1<x>y$. Swapping yields $(1,y,x)$ or $(x,y,1)$. Hence this works unless $x=9$, which implies $1$ and $9$ are adjacent. Furthermore if there exist $(b,a,1,x,y)$ then we fail as only one of $a$ and $x$ is equal to $9$. Hence $1$ is on either the leftmost two squares or the rightmost two squares. The same holds for $9$, which is an obvious contradiction. $\blacksquare$