Question 10
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.