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.

  • 1
    $\begingroup$ in fact, each movement, the parity of the number of inversions changes, not necessarily by one. $\endgroup$ – leticia Jul 5 '13 at 21:06
  • $\begingroup$ This of course true. I am sorry - I edited it. $\endgroup$ – Tomas Jul 5 '13 at 21:46

Basically, if you make an odd number of switches, then at least one of the numbers has only been moved once (unless you repeat the same switch over and over which is an easy case to explain). But if you start in some configuration and move a number only once and want to return to the start, you must move again.

Try induction -- an easy base case is $n=2$.

  • $\begingroup$ 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. $\endgroup$ – Mark Bennet Jul 5 '13 at 20:09
  • $\begingroup$ I agree. The approach suggested by Tomas seems very promising. $\endgroup$ – C. Williamson Jul 5 '13 at 20:14
  • $\begingroup$ But your approach can be changed into a viable idea, which is why a made a comment and didn't vote you down. It is a good first thought, and often people who ask questions like this can benefit from seeing how a good first thought can be developed into an answer. I was looking forward to seeing what came next. Problem solvers don't give up ... and since this is a problem solving website ... Thanks for trying. $\endgroup$ – Mark Bennet Jul 5 '13 at 21:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.