Our permutation graph is a disjoint reunion of cycles and then for each cycle the proof goes by induction on the length. The initial steps ($n=1,2,3$) are trivial. For the induction step the key is to find two different $x$ and $y$ such that $x\le\sigma(y)\le\sigma(x)\le y$. Suppose by the sake of contradiction that there are no such $x$ and $y$. Then if $m$ is the greatest number we will have $m>\sigma(m)>\sigma(\sigma(m))>...$, a flagrant contradiction. Once we have found $x$ and $y$, we swap $\sigma(x)$ and $\sigma(y)$ and then apply the induction hypothesis.

Hi, I believe you don't need to cite induction at all. Just showing you have the desired $x$ and $y$ as you did shows you can always make adjustments in the right direction (i.e. without spending more money than you can afford) until you're done.

This is a very slippery problem. We will induct simultaneously on the quantities $n$ and $S = |a_1-1|+ |a_2-2|+\ldots + |a_n-n|$. In the case where these are both zero, we are done immediately. If $a_1 = 1$, remove the first term from the sequence and reduce every other term by one to reduce it to the case of $n-1$. If $a_1 \neq 1$, we will swap two of $a_x$ and $a_y$ to reduce the quantity $S$ by precisely $2|a_x - a_y|$. If we can achieve this, we will be done by induction. Define $b_i$ to be the number $j$ such that $a_j = i$. Consider the set of numbers \[ b_1, b_2 \ldots b_{a_1-1}.\]Since none of them are equal to one, and there are $a_1-1$ of them, at least one of them is greater than or equal to $a_1$. Let $c = b_k \ge a_1$. Observe that $1 \le k < a_1 \le b_k$. Now we swap $a_c$ and $a_1$. Then, the only terms which change in $S$ are the ones involving $1$ and $b_k$, and indeed \[ |a_1 - 1| + |k - b_k| - 2|a_1 - k| = |k-1| - |a_1 - b_k| \]. Hence, we are done by the aforementioned induction. Does anyone know if the previous solution is correct or not?

We proceed by induction on $n$. The small cases are trivial. Assume all smaller cases hold, we consider the case $n$. Notice that every permutation can be decomposed into cycles. Therefore it suffices to consider the case for cycles. Let $(a_1a_2...a_n)$ be the cycle which permutates $(1,2,...,n)$. We take the indices modulo $n$. CLAIM. We can always find $i\neq j$ such that $$a_{i-1}\geq a_j\geq a_i\geq a_{j-1}$$Proof. WLOG assume $a_1=max\{a_k|1\leq k\leq n\}$. We will take $i=2$. Since $a_1$ is the maximum of the $a's$ it suffices to find $j$ such that $$a_j\geq a_2\geq a_{j-1}$$We further divide into three cases: CASE I: $a_2\geq a_n$ We will take $j=1$, hence $a_j=a_1\geq a_2\geq a_n=a_{j-1}$ CASE II: $a_2=min\{a_k|1\leq k\leq n\}$ We will take $j=3$, hence $a_j=a_3\geq a_2\geq a_2=a_{j-1}$ CASE III: $a_2\leq a_n$ but $a_m=min\{a_k|1\leq k\leq n\}$ where $m\neq 2$ Since $a_n\geq a_2\geq a_m$, by discrete continuity there exists some $j$ such that $a_j\geq a_2\geq a_{j-1}$ $\blacksquare$ Now at any moment let $C$ be the coins Petya has spent, if at some moment the permutation can be further decomposed into cycles then we are done by the inductive hypothesis, otherwise let $(b_1b_2...b_n)$ be the cycle and let $S=|b_1-1|+|b_2-2|+...+|b_n-n|$. Let $A=C+S$. Now notice that from the CLAIM we can always find $i\neq j$ such that $b_{i-1}\geq b_j\geq b_i\geq b_{i-1}$. Petya will swap this pair of $(i,j)$. Now $$-\Delta S=|b_{i-1}-b_i|+|b_{j-1}-b_j|-|b_{i-1}-b_j|-|b_{j-1}-b_i|=2(b_j-b_i)=\Delta C$$Hence $C+S$ is an invariant. Since $C$ is increased by $2|b_i-b_j|$ which is a positive number, there must be some point that $S=0$, hence every number returns to its own position, and Petya has spent no more than $|a_1-1|+|a_2-2|+...+|a_n-n|$ coins as desired.

First, define a function $f: \{ 1, 2, \dots, n \} \mapsto \{ 1, 2, \dots, n \}$ such that $f(i) = a_i$. Clearly, this function is injective and surjective, hence it is a bijection. Claim: If we create a graph with vertices as $1, 2, \dots, n$ and edges from $i \rightarrow f(i)$, then the graph is a collection of disjoint cycles. Proof. We prove the statement with induction on the number of vertices. The base case $n = 0$ is vacuous. For the inductive step, notice that each vertex has an indegree and outdegree of $1$. Now, if $f(1) = 1$ then this gives a cycle of size $1$, so we apply the inductive hypothesis to the remaining $n-1$ vertices. Now assume $f(1) \neq 1$. Starting from vertex $1$, then if we are at vertex $i$ mark $i$ as visited and go to $f(i)$. Since we can always travel out of a vertex, we must eventually return to a visited vertex. Call the first visited vertex we go to $v$. If $v \neq 1$ then $f^{-1}(v)$ must have been visited as well, contradiction, so $v = 1$. Then we have found a cycle with containing $1$ that has $m$ vertices and $m$ edges for some $m$. Applying the induction hypothesis to the graph of the remaining $n-m$ vertices and edges proves the inductive step. $\blacksquare$ We will also prove the following fact which will become useful: Claim: Consider a cycle $a \rightarrow f(a) \rightarrow \dots \rightarrow f^k(a) = a$ where $k\ge 2$. Suppose for some $x, y$ in the cycle, we change the graph such that $x \rightarrow f(y)$ and $y \rightarrow f(x)$. Then the graph now has more than one cycle. Proof. WLOG via shifting, suppose that $a$ and $b$ for some $b \neq a$ were swapped, so $a \rightarrow f(b)$ and $b \rightarrow f(a)$. Then $b \rightarrow f(a) \rightarrow f^2(a) \rightarrow \dots \rightarrow b$, since $b = f^c(a)$ for some $c \ge 1$. This gives one cycle, and the remaining vertices and edges must have at least one cycle among them. $\blacksquare$ Call the complexity of a permutation $a_1, a_2, \dots, a_n$ to be the number of cycles in this function graph. Call the simplicity of a permutation to be $n - k$, where $k$ is the complexity of the permutation. Then I will prove the claim by inducting on the simplicity $s$ of a permutation. Call the penalty of a permutation to be the sum $|a_1 - 1| + |a_2 - 2| + \dots + |a_n - n|$. The case when $s = 0$ is clear, as then there are $n$ cycles which means the permutation must be ordered. For the inductive step, $s \ge 1$ so there exists a cycle with size at least $2$. Suppose the cycle is given by $a, f(a), \dots, f^{k-1}(a), f^k(a) = a$ for some positive integer $k\ge 2$ and a positive integer $1\le a\le n$. Then Claim: There exists $x, y$ in the cycle such that $x \le f(y) \le f(x) \le y$. Proof. Assume FTSOC this is not the case. Now consider the minimal $x$ in the cycle. Then I claim that \[ x < f(x) < \dots < f^k(x) \]We prove this by induction that $x < f(x) < \dots < f^m(x)$ for $1\le m\le k$. The base case $m=1$ is trivial due to minimality of $x$. For the inductive step, assume FTSOC that $f^{m+1}(x) \le f^{m-1}(x)$; then take the $0\le g\le m-2$ such that $f^g(x) \le f^{m+1}(x) \le f^{g+1}(x)$, which must exist. Then notice that \[ f^g(x) \le f^{m+1}(x) \le f^{g+1}(x) \le f^m(x) \]a contradiction. Thus $f^{m+1}(x) \ge f^{m-1}(x)$, but then $f^{m+1}(x) > f^m(x)$, proving the claim. But then this gives us the desired contradiction, as $f^k(x) = x$. $\blacksquare$ Now, for the $x, y$ with $x \le f(y) \le f(x) \le y$ and $x,y$ in the same cycle, we swap them, so the cost is $2|x-y|$ and the penalty of the permutation decreases by \begin{align*} &|f(x) - x| + |f(y) - y| - |f(x) - y| - |f(y) - x| \\ &= (f(x) - x + y - f(y)) - (f(x) - y - f(y) + x) \\ &= 2(y-x) = 2|x-y| \end{align*}now this creates a new permutation $b_i$, and furthermore $b_i$ has more cycles from our previous claim. Hence $b_i$ has less simplicity than $a_i$, and by the inductive hypothesis it is possible to order $b_i$ using a cost less than or equal to the penalty. Then it follows that we can order $a_i$ using a cost less than or equal to the penalty. This completes the induction. $\blacksquare$