1

Suppose there is a list with finitely many distinct items. In each move we swap two of them. How to show that it is impossible to make moves odd times and make the list back to the original state? (Or is it actually possible?)

user
  • 121
  • Welcome to Mathematics Stack Exchange. The tag is proper. The identity permutation is an even permutation. An even permutation can be obtained as the composition of an even number and only an even number of exchanges (called transpositions) of two elements, – J. W. Tanner Sep 15 '19 at 15:15
  • 2
    If you've gotten far enough in permutations, you can say that the answer is no because the identity permutation is even. –  Sep 15 '19 at 15:16
  • @all thanks you can make that an answer. – user Sep 15 '19 at 15:20

1 Answers1

0

Every permutation can be expressed as a composition of transpositions, which are permutations that just switch two elements. Perhaps the fundamental theorem to intro permutations is that the number of transpositions for a given permutation is not fixed, but the parity of the number is. That is, if a permutation can be achieved from an even number of transpositions, then it cannot be achieved from an odd number of transpositions, and vice-versa.

With that under our belt, the identity permutation is easily seen to be even. Therefore, an odd number of transpositions will never get a list back to its original state.