Question 178
Let $n$ be a natural number. We call a sequence consisting of $3 n$ letters Romanian if the letters $I, M$ and $O$ each occur exactly $n$ times. A swap is an exchange of two adjacent letters. Show that for every Romanian sequence $X$ there exists a Romanian sequence $Y$ such that at least $\frac{3 n^{2}}{2}$ swaps are needed to obtain the sequence $Y$ from the sequence $X$.