2017 IMO SL #C2

Let $n$ be a positive integer. Define a chameleon to be any sequence of $3n$ letters, with exactly $n$ occurrences of each of the letters $a, b,$ and $c$. Define a swap to be the transposition of two adjacent letters in a chameleon. Prove that for any chameleon $X$ , there exists a chameleon $Y$ such that $X$ cannot be changed to $Y$ using fewer than $3n^2/2$ swaps.

Denote $M = \underbrace{aa\dots a}_{n}\underbrace{bb\dots b}_{n}\underbrace{cc\dots c}_{n}$ and $N = \underbrace{cc\dots c}_{n}\underbrace{bb\dots b}_{n}\underbrace{aa\dots a}_{n}$. We claim that we need at least $3n^2$ swaps to transform $M \to N$ and vice versa. Notice that all pairs of $(a, b), (b, c),$ and $(c, a)$ must be swapped hence a minimum of $3n^2$ swaps as desired. Next, we claim that given any chameleon string $X$, one of $M, N$ satisfies the conditions. For the sake of contradiction, suppose otherwise, and that both operations $X \to M$ and $X \to N$ take less than $\tfrac{3n^2}{2}$ swaps. Then, note that $M \to N = M \to X \to N$ must take less than $3n^2$, a contradiction, and we are done. $\square$