Maths Olympiad Prep

Library / /10 of 27

Algebra Difficulty 6.5 National olympiad Prove it North Macedonia

In each vertex of a regular nn-gon A1,A2,,AnA_1, A_2, \ldots, A_n there is a unique pawn. In each step it is allowed:
1. to move all pawns one step in the clockwise direction or
2. to swap the pawns at vertices A1A_1 and A2A_2.
Prove that by a finite series of such steps it is possible to swap the pawns at vertices:
a) AiA_i and Ai+1A_{i+1} for any 1i<n1 \le i < n while leaving all other pawns in their initial place
b) AiA_i and AjA_j for any 1i<jn1 \le i < j \le n leaving all other pawns in their initial place.

Solution

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

a) We apply first operation i1i-1 times which will bring ii and i+1i+1 as they are at points A1A_1 and A2A_2 and move every other pawn i1i-1 steps in clockwise direction.
We can now apply second operation to swap ii and i+1i+1 as they are at points A1A_1 and A2A_2. This does not affect the position of any other pawn.
We now apply first operation ni+1n-i+1 times returning pawn ki,i+1k \ne i, i+1 to point AkA_k while moving pawn ii to Ai+1A_{i+1} and pawn i+1i+1 to AiA_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)(i, i+1) as they are at points (Ai,Ai+1)(A_i, A_{i+1}) then (i,i+2)(i, i+2) as they are at points (Ai+1,Ai+2)(A_{i+1}, A_{i+2}) and carry on until we swap (i,j)(i, j) as they were at points (Aj1,Aj)(A_{j-1}, A_j). This brings us to the state where ii is at AjA_j and each i+1kji+1 \le k \le j is at point Ak1A_{k-1}.
We can now apply part a) to swap jj with j1j-1 and similarly carry on till we swap jj with i+1i+1. This will place jj at AiA_i and move each i+1kj1i+1 \le k \le j-1 to AkA_k.
This brings us to the state we swapped pawns ii and jj leaving others where they were just as was desired.

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

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.