International Mathematical Olympiad

To start, notice that the swap of two identical letters does not change a chameleon, so we may assume there are no such swaps. For any two chameleons $X$ and $Y$, define their distance $d(X,Y)$ to be the minimal number of swaps needed to transform $X$ into $Y$ (or vice versa). Clearly, $d(X,Y)+d(Y,Z)⩾d(X,Z)$ for any three chameleons $X$, $Y$, and $Z$.

Lemma. Consider two chameleons $$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}}\text{.}$$ Then $d(P,Q)⩾3n^2$.

Proof. For any chameleon $X$ and any pair of distinct letters $u,v\in \{a,b,c\}$, we define $f_{u,v}(X)$ to be the number of pairs of positions in $X$ such that the left one is occupied by $u$, and the right one is occupied by $v$. Define $f(X)=f_{a,b}(X)+f_{a,c}(X)+f_{b,c}(X)$. Notice that $f_{a,b}(P)=f_{a,c}(P)=f_{b,c}(P)=n^2$ and $f_{a,b}(Q)=f_{a,c}(Q)=f_{b,c}(Q)=0$, so $f(P)=3n^2$ and $f(Q)=0$.

Now consider some swap changing a chameleon $X$ to $X^{\prime }$, say, the letters $a$ and $b$ are swapped. Then $f_{a,b}(X)$ and $f_{a,b}(X^{\prime })$ differ by exactly 1, while $f_{a,c}(X)=f_{a,c}(X^{\prime })$ and $f_{b,c}(X)=f_{b,c}(X^{\prime })$. This yields $|f(X)-f(X^{\prime })|=1$, i.e., on any swap the value of $f$ changes by 1. Hence $d(X,Y)⩾|f(X)-f(Y)|$ for any two chameleons $X$ and $Y$. In particular, $d(P,Q)⩾|f(P)-f(Q)|=3n^2$, as desired.

Back to the problem, take any chameleon $X$ and notice that $d(X,P)+d(X,Q)⩾d(P,Q)⩾3n^2$ by the lemma. Consequently, $\max \{d(X,P),d(X,Q)\}⩾\frac{3n^2}{2}$, which establishes the problem statement.

---

Alternative solution.

We use the notion of distance from Solution 1, but provide a different lower bound for it. In any chameleon $X$, we enumerate the positions in it from left to right by $1,2,\dots ,3n$. Define $s_c(X)$ as the sum of positions occupied by $c$. The value of $s_c$ changes by at most 1 on each swap, but this fact alone does not suffice to solve the problem; so we need an improvement.

For every chameleon $X$, denote by $X_{\bar{c}}$ the sequence obtained from $X$ by removing all $n$ letters $c$. Enumerate the positions in $X_{\bar{c}}$ from left to right by $1,2,\dots ,2n$, and define $s_{\bar{c},b}(X)$ as the sum of positions in $X_{\bar{c}}$ occupied by $b$. (In other words, here we consider the positions of the $b$'s relatively to the $a$'s only.) Finally, denote $$d^{\prime }(X,Y):=|s_c(X)-s_c(Y)|+|s_{\bar{c},b}(X)-s_{\bar{c},b}(Y)|.$$ Now consider any swap changing a chameleon $X$ to $X^{\prime }$. If no letter $c$ is involved into this swap, then $s_c(X)=s_c(X^{\prime })$; on the other hand, exactly one letter $b$ changes its position in $X_{\bar{c}}$, so $|s_{\bar{c},b}(X)-s_{\bar{c},b}(X^{\prime })|=1$. If a letter $c$ is involved into a swap, then $X_{\bar{c}}=X_{\bar{c}}^{\prime }$, so $s_{\bar{c},b}(X)=s_{\bar{c},b}(X^{\prime })$ and $|s_c(X)-s_c(X^{\prime })|=1$. Thus, in all cases we have $d^{\prime }(X,X^{\prime })=1$.

As in the previous solution, this means that $d(X,Y)⩾d^{\prime }(X,Y)$ for any two chameleons $X$ and $Y$. Now, for any chameleon $X$ we will indicate a chameleon $Y$ with $d^{\prime }(X,Y)⩾3n^2/2$, thus finishing the solution.

The function $s_c$ attains all integer values from $1+\cdots +n=\frac{n(n+1)}{2}$ to $(2n+1)+\cdots +3n=2n^2+\frac{n(n+1)}{2}$. If $s_c(X)⩽n^2+\frac{n(n+1)}{2}$, then we put the letter $c$ into the last $n$ positions in $Y$; otherwise we put the letter $c$ into the first $n$ positions in $Y$. In either case we already have $|s_c(X)-s_c(Y)|⩾n^2$.

Similarly, $s_{\bar{c},b}$ ranges from $\frac{n(n+1)}{2}$ to $n^2+\frac{n(n+1)}{2}$. So, if $s_{\bar{c},b}(X)⩽\frac{n^2}{2}+\frac{n(n+1)}{2}$, then we put the letter $b$ into the last $n$ positions in $Y$ which are still free; otherwise, we put the letter $b$ into the first $n$ such positions. The remaining positions are occupied by $a$. In any case, we have $|s_{\bar{c},b}(X)-s_{\bar{c},b}(Y)|⩾\frac{n^2}{2}$, thus $d^{\prime }(X,Y)⩾n^2+\frac{n^2}{2}=\frac{3n^2}{2}$, as desired.