6

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!

Tomas
  • 4,534
lele
  • 2,392

2 Answers2

2

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.

Tomas
  • 4,534
-3

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$.

N. Mao
  • 411
  • 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 05 '13 at 20:09
  • I agree. The approach suggested by Tomas seems very promising. – N. Mao Jul 05 '13 at 20:14
  • 1
    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. – Mark Bennet Jul 05 '13 at 21:19