Câu hỏi 178
Cho $n$ là một số tự nhiên. Ta gọi một dãy gồm $3 n$ chữ cái là dãy Romania nếu mỗi chữ cái $I, M$ và $O$ xuất hiện đúng $n$ lần. Một phép đổi chỗ (swap) là phép hoán đổi hai chữ cái kề nhau. Chứng minh rằng với mọi dãy Romania $X$, tồn tại một dãy Romania $Y$ sao cho cần ít nhất $\frac{3 n^{2}}{2}$ phép đổi chỗ để nhận được dãy $Y$ từ dãy $X$.