0
$\begingroup$

Considering a permutation of [1, 2, ..., n], it is fairly obvious that on doing n/2 swaps we arrive at the permutation [n, n-1, ..., 1]. This can be achieved by swapping the first element with the last, the second with the second from the last, and so on.

The part I'm having trouble with is writing a formal theoretical proof for this problem. I tried my hand at induction but haven't made much progress.

Any pointers would be well appreciated !

$\endgroup$
  • $\begingroup$ Look at the cycle notation of the permutation.... $\endgroup$ – Lord Shark the Unknown Feb 5 at 18:52
  • $\begingroup$ You could try a proof with complete induction. Start with $n=1$ and $n=2$, then step from $n=2k$ to $n=2k+1$ and $n=2k+2$. $\endgroup$ – Wolfgang Kais Feb 5 at 21:54
  • $\begingroup$ What exactly are you trying to prove? Guess 1: that it's possible to reach the reversed permutation from the identity permutation with at most n/2 swaps. Guess 2: that a certain sequence of n/2 swaps results in the reversed permutation. $\endgroup$ – Peter Taylor Feb 6 at 13:40
  • $\begingroup$ I think your first guess is closer to what I'm trying to prove. Any pointers? $\endgroup$ – user641888 Feb 7 at 1:42
0
$\begingroup$

A formal theoretical proof. Let $\sigma$ be the inverse permutation of the set $[n]=\{1,\dots,n\}$, that is $\sigma(i)=n+1-i$ for each $i\in [n]$. For each $1\le i\le \lfloor \tfrac n2\rfloor$ let $\sigma_i$ be a transposition of elements $i$ and $n+1-i$, that is $\sigma_i(i)=n+1-i$ and $\sigma_i(n+1-i)=i$. Let $\rho=\prod_{i=1}^{\left\lfloor \tfrac n2\right\rfloor}\sigma_i$ and $j\in n$ be any element. If $n$ is odd and $j=\tfrac{n+1}2$ then $\rho(j)=j=\sigma(j)$. Otherwise there exists a unique $i$, $1\le i\le \tfrac n2$ such that $j\in \{i,n+1-i\}$. Then $\rho(j)=\sigma_i(j)=n+1-j=\sigma(j).$ That is $\rho=\sigma$.

$\endgroup$

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.