European Mathematical Cup

We denote a pawn that was initially at point $A_i$ as $i$. We will prove that a) and then use it to show part b).

a) We apply first operation $i-1$ times which will bring $i$ and $i+1$ as they are at points $A_1$ and $A_2$ and move every other pawn $i-1$ steps in clockwise direction. We can now apply second operation to swap $i$ and $i+1$ as they are at points $A_1$ and $A_2$. This does not affect the position of any other pawn. We now apply first operation $n-i+1$ times returning pawn $k\ne i,i+1$ to point $A_k$ while moving pawn $i$ to $A_{i+1}$ and pawn $i+1$ to $A_i$ which is exactly what we wanted.

b) We present 2 possible solutions, one using induction and one not using induction.

Solution not using induction By using the previous problem we can swap pawns $(i,i+1)$ as they are at points $(A_i,A_{i+1})$ then $(i,i+2)$ as they are at points $(A_{i+1},A_{i+2})$ and carry on until we swap $(i,j)$ as they were at points $(A_{j-1},A_j)$. This brings us to the state where $i$ is at $A_j$ and each $i+1\le k\le j$ is at point $A_{k-1}$. We can now apply part a) to swap $j$ with $j-1$ and similarly carry on till we swap $j$ with $i+1$. This will place $j$ at $A_i$ and move each $i+1\le k\le j-1$ to $A_k$. This brings us to the state we swapped pawns $i$ and $j$ leaving others where they were just as was desired.

Solution using induction We use induction on $n$ for the following claim: We can swap any two pawns $1\le i<j\le k$. We note that the basis is exactly part a). We assume the claim holds for some $k$. Hence we can swap any pawns $1\le i<j\le k$ and only need to show that we can swap $i$ and $k+1$ for any $1\le i\le k$. This follows as we can swap $i$ and $k$ then $k$ and $k+1$ by part a). Then again $k+1$ and $i$ as they are now on points $A_k$ and $A_i$.