# Sequence of natural numbers

Numbers $1,2,...,n$ are written in sequence. It's allowed to exchange any two elements. Is it possible to return to the starting position after an odd number of movements?

I know that is necessarily an even number of movements but I can't explain that!

Hint: Define an inversion of a sequence $(a_1,\dots,a_n)$ as a pair $(i,j)$, such that $i<j$ and $a_i>a_j$. Check, that each movement changes the parity of number of inversions.
Try induction -- an easy base case is $n=2$.
• If $n=5$ and I do $(12)(23)(13)(15)(25)(14)(34)$ I have done an odd number of switches without repeating a switch, and every number has moved at least twice. You need to be more subtle in your analysis. – Mark Bennet Jul 5 '13 at 20:09