2017 IMO Shortlist C2

Let $n$ be a positive integer. Define a chameleon to be any sequence of $3 n$ 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 $3 n^{2} / 2$ swaps. (Australia)

令 $n$ 为正整数。将变色龙定义为 $3 n$ 个字母的任意序列，其中每个字母 $a、b$ 和 $c$ 恰好出现 $n$ 次。将交换定义为变色龙中两个相邻字母的换位。证明对于任何变色龙 $X$，都存在变色龙 $Y$，使得使用少于 $3 n^{2} / 2$ 交换无法将 $X$ 更改为 $Y$。 (澳大利亚)