Freddy writes down numbers $1, 2,\ldots ,n$ in some order. Then he makes a list of all pairs $(i, j)$ such that $1\le i<j\le n$ and the $i$-th number is bigger than the $j$-th number in his permutation. After that, Freddy repeats the following action while possible: choose a pair $(i, j)$ from the current list, interchange the $i$-th and the $j$-th number in the current permutation, and delete $(i, j)$ from the list. Prove that Freddy can choose pairs in such an order that, after the process finishes, the numbers in the permutation are in ascending order.
Problem
Source: Baltic Way 2007
Tags: algorithm, induction, combinatorics proposed, combinatorics
randomusername
15.02.2015 11:08
We proceed by induction. It is trivial for $n=1$. Suppose an algorithm is possible for any possible permutations or $1,2,\dots,n-1$, now we prove the claim for $1,2,\dots,n$. Let the permutation be $a_1,a_2,\dots,a_n$, where $a_k=n$. Then the list is composed of the pairs $(n,a_{k+1}),(n,a_{k+2}),\dots,(n,a_n)$, and of the pairs generated by the list $a_1,a_2,\dots,a_{k-1},a_{k+1},\dots,a_n$. Let's switch one by one via the pairs $(n,a_{k+1}),(n,a_{k+2}),\dots,(n,a_n)$ in this order, then the result is the permutation $a_1,a_2,\dots,a_{k-1},a_{k+1},\dots,a_n,n$. By the induction hypothesis, we can finish the algorithm using the pairs generated by $a_1,a_2,\dots,a_{k-1},a_{k+1},\dots,a_n$, because it is a permutation of $1,2,\dots,n-1$. This completes the proof.
chaotic_iak
15.02.2015 20:04
Unfortunately the pairs are not the numbers, but the positions (the pairs related to the number $n$ are $(k,k+1), (k,k+2), \ldots, (k,n)$, not $(n,a_{k+1}), (n,a_{k+2}), \ldots, (n,a_n)$). But this is easy to fix; solve $a_1, a_2, \ldots, a_{k-1}, a_{k+1}, a_{k+2}, \ldots, a_n$, and finish with the pairs $(k,n), (k,n-1), \ldots, (k,k+1)$ in that order.
Vedant10
05.07.2020 03:56
https://codeforces.com/contest/1375/problem/E nice
Vedant10
05.07.2020 04:02
that contest today used this problem more or less in code