Croatian Mathematical Olympiad

Let us define the distance of good words $X$ and $Y$, denoted by $d(X,Y)$, as the smallest number of swaps of neighbouring letters necessary to obtain $Y$ from $X$ (or vice versa). Note that $d(X,Y)=d(Y,X)$, and that for any three good words $X$, $Y$ and $Z$ we have $$d(X,Y)+d(Y,Z)\ge d(X,Z).$$ Furthermore, for a good word $X$ denote by $F(X)$ the number of pairs of positions where the letter in the left position is lexicographically smaller than the one in the right position, i.e. the number of pairs of the form $AB$, $AC$ or $BC$. By swapping two neighbouring letters in a good word $X$ we get a good word $X^{\prime }$. If the letters were identical, those two words would be equal, so we can assume that all swaps involve pairs of different letters. If we swap different letters, we have $|F(X)-F(X^{\prime })|=1$. From this, we can conclude that $$d(X,Y)\ge |F(X)-F(Y)|$$ for any two good words $X$ and $Y$. Observe the good words $$P=\underset{n}{\underbrace{AA\dots A}}\underset{n}{\underbrace{BB\dots B}}\underset{n}{\underbrace{CC\dots C}}\text{and}Q=\underset{n}{\underbrace{CC\dots C}}\underset{n}{\underbrace{BB\dots B}}\underset{n}{\underbrace{AA\dots A}}$$ Note that $F(P)=3n^2$ and $F(Q)=0$, therefore $d(P,Q)\ge 3n^2$. Finally, for any good word $X$ we have $$d(P,X)+d(X,Q)\ge d(P,Q)\ge 3n^2.$$ Therefore, one of the good words $P$ and $Q$ cannot be obtained from $X$ by swapping fewer than $\frac{3}{2}{n}^2$ pairs of neighbouring letters.