MathNet 2018-part-04 — 181 problems (EN–VI) Question 58

Let $n$ be a positive integer, and let $W$ be the set of all words of length $3n$ containing each of the letters $a, b, c$ exactly $n$ times. Prove that for any word $w$ in $W$ there exists a word $w'$ in $W$ that cannot be obtained from $w$ by less than $3n^2/2$ successive transpositions of adjacent letters.
IMO 2017 Shortlist