Help with the proof of a lemma used in problem Div1 B: Petr and Permutations

Revision en1, by towrist, 2020-02-02 14:47:41

Here is the link to the problem: 987E - Petr and Permutations

My solution is:

  1. A constructive algorithm to count the number of steps from the identity permutation to the given input permutation. [PROVEN]

  2. Compare the parity of the number of steps required with the parity of $$$3n$$$ and $$$7n+1$$$ and print Petr or Um_nik.

Now, I have used the following lemma: If one permutation $$$P1$$$ can be reached from another permutation $$$P2$$$ in even number of steps, then it is not possible to reach $$$P1$$$ from $$$P2$$$ in odd number of steps. Similarly, vice versa.

I can't prove this lemma, and I have tried:

  • Induction
  • Greedy proof techniques

and they don't seem to work. Any help will be appreciated! Thanks!

Tags #proof, #permutation, #math, #combinatorics

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English towrist 2020-02-02 14:47:41 830 Initial revision (published)