NMO Selection Tests for BMO and IMO

For convenience, a transposition of two adjacent letters in a word will be referred to as a swap. Notice that swapping identical letters does not change a word, so assume that no swaps are performed.

Define the distance $\text{dist}(w, w')$ of two words $w$ and $w'$ in $W$ to be the minimal number of swaps required to transform $w$ into $w'$ (or vice versa). Clearly, if $w''$ is another word in $W$, then $\text{dist}(w, w') + \text{dist}(w, w'') \ge \text{dist}(w', w'')$. Consequently, if $\text{dist}(w', w'') \ge 3n^2$, then $\max(\text{dist}(w, w'), \text{dist}(w, w'')) \ge 3n^2/2$, so it is sufficient to exhibit two words in $W$ at least $3n^2$ distance apart.

We are presently going to show that the words
$$w_0 = \underbrace{aa\dots a}_{n} \underbrace{bb\dots b}_{n} \underbrace{cc\dots c}_{n} \quad \text{and} \quad w'_0 = \underbrace{cc\dots c}_{n} \underbrace{bb\dots b}_{n} \underbrace{aa\dots a}_{n}$$
are at least $3n^2$ distance apart.

For any word $w$ in $W$ and any pair of distinct letters $\alpha$ and $\beta$ in the alphabet $\{a, b, c\}$, let $f_{\alpha,\beta}(w)$ be the number of pairs of positions in $w$ with $\alpha$ in the left position and $\beta$ in the right. Let $f(w) = f_{a,b}(w) + f_{a,c}(w) + f_{b,c}(w)$.

In particular, $f_{a,b}(w_0) = f_{a,c}(w_0) = f_{b,c}(w_0) = n^2$ and $f_{a,b}(w'_0) = f_{a,c}(w'_0) = f_{b,c}(w'_0) = 0$, so $f(w_0) = 3n^2$ and $f(w'_0) = 0$.

Finally, notice that a swap changes exactly one of $f_{a,b}$, $f_{a,c}$, $f_{b,c}$, the absolute value of the change being 1. Consequently, $f$ changes by 1 at each swap, so $\text{dist}(w, w') \ge |f(w) - f(w')|$, whatever words $w$ and $w'$ in $W$. In particular, $\text{dist}(w_0, w'_0) \ge |f(w_0) - f(w'_0)| = 3n^2$, as claimed.