I don't think this is true. When $n=2$, you can choose $X=abcabc$, and for every chameleon $Y$, there will always be a way to change into it using fewer than $12$ swaps.

he meant $3n^2/2$ swaps

It suffices to show there always exists a path from $\underbrace{aaa\cdots a}_n\underbrace{bbb\cdots b}_n\underbrace{ccc\cdots c}_n$ to chameleon $X$ to $\underbrace{ccc\cdots c}_n\underbrace{bbb\cdots b}_n\underbrace{aaa\cdots a}_n$ using $3n^2$ swaps, which is quite easy to do. Then, using this path, you can choose $Y$ to be either $\underbrace{aaa\cdots a}_n\underbrace{bbb\cdots b}_n\underbrace{ccc\cdots c}_n$ or $\underbrace{ccc\cdots c}_n\underbrace{bbb\cdots b}_n\underbrace{aaa\cdots a}_n$. One of them will take you less than $3n^2/2$ swaps to reach from $X$, while the other will take you more than $3n^2/2$.

This is a great problem with the idea of inversion index. Consider the two chameleons $$aa\cdots abb \cdots bcc \cdots c, \qquad cc\cdots cbb\cdots baa\cdots a,$$Let’s call the first chameleon $A$ and the second chameleon $B$. Suppose we have a sequence of moves such that $A \to B$. Note each pair of $a$s and $b$s in the first must be swapped, as the second chameleon does not have any $a$s coming before any $b$s. Similarly, each pair of $b$s and $c$s, and each pair of $a$s and $c$s must be swapped. Thus the second chameleon takes at least $3n^2$ swaps to produce from the first, and this is easily achievable. Now consider any other chameleon $X$, and suppose, for the sake of contradiction, it takes less than $\frac32n^2$ swaps to do either $X \to A$ or $X \to B$. Then the sequence $A \to X \to B$ produces $B$ from $A$, and it takes less than $\frac32n^2 + \frac32n^2 = 3n^2$ swaps. This contradicts that it takes at least $3n^2$ swaps to do $A \to B$.

Here is the write-up by Po-Shen Loh: By definition, C2 is equivalent to: in adjacent-transposition graph, \[ \textbf{radius} \ge 3n^2/2. \tag{1} \]Basic graph theory (p.9 of Diestel's 300-page book): \[ \textbf{radius} \ge \frac{\textbf{diameter}}{2}. \tag{2} \]Algorithms, or statistics: \[ \textbf{bubble-sort-distance} = \textbf{number of inversions}. \tag{3} \]Since $aaabbbccc \longleftrightarrow cccbbbaaa$ has $3n^2$ inversions, diameter $\ge 3n^2$.

Given two chameleons $A$ and $B$ let $d(A, B)$ be the minimal number of swaps required to change $A$ into $B$. Clearly $d$ satisfies the triangle inequality. Now define the two chameleons $$X = \underbrace{aa\dots a}_{n}\underbrace{bb\dots b}_{n}\underbrace{cc\dots c}_{n}$$ $$Y = \underbrace{cc\dots c}_{n}\underbrace{bb\dots b}_{n}\underbrace{aa\dots a}_{n}$$ We claim that $d(X, Y) \geq 3n^2$. To this effect, define $f(A)$ for a chameleon $A$ to be the number of pairs $(p, q)$ of integers with $1 \leq p < q \leq 3n$ such that the $p$th letter of $A$ comes before the $q$th alphabetically. Then clearly $f(X) = 3n^2$ while $f(Y) = 0$. Moreover, any swap applied to a chameleon either increases or decreases $f$ by exactly $1$, because it reverses the alphabetical order for exactly one pair of letters. It follows that at least $3n^2$ swaps must be performed to switch $X$ into $Y$, i.e. $d(X, Y) \geq 3n^2$. Finally, let $Z$ be an arbitrary chameleon. Then by the triangle inequality: $$d(Z, X) + d(Z, Y) \geq d(X, Y) \geq 3n^2$$ Which implies that $\max(d(Z, X) + d(Z, Y)) \geq \frac{3n^2}{2}$, which means that one of the chameleons $X$ and $Y$ cannot be reached from $Z$ using less than $\frac{3n^2}{2}$ swaps, as desired.

We prove that for any Chameleon X, we can choose a Chameleon Y of the form $$Y = \underbrace{aa\dots a}_{n}\underbrace{bb\dots b}_{n}\underbrace{cc\dots c}_{n}$$ With the $a,b,c$ not necessarily in that order, which satisfies the condition of the problem. Note that every swap ONLY affects the position of the two letters one is swapping (everything else is fixed). Also, notice that every swap performed between two equal letters is completely ineffective. Thus, to get any chameleon X to the form $Y = \underbrace{aa\dots a}_{n}\underbrace{bb\dots b}_{n}\underbrace{cc\dots c}_{n}$, the optimal way to do so will be to move the left-most $a$ to the left-most position, the second-leftmost $a$ to the second left-most position, etc. Number all the positions in the initial sequence X with $1,2,...,3n$. Now, for each of $a,b,c$, write the sum of all the numbers associated with each letter. Since $1+2+...+3n=\frac{3n(3n+1)}{2}$, then we must have that for at least one of the letters, this sum is greater than or equal to $\frac{\frac{3n(3n+1)}{2}}{3}=\frac{n(3n+1)}{2}$. Suppose WLOG that the letter with the greatest sum is $a$. Now, if we make our sequence Y of the form $\underbrace{aa\dots a}_{n}\underbrace{bb\dots b}_{n}\underbrace{cc\dots c}_{n}$, then to move all the $a$s to the left-most positions, we will need at least $\frac{n(3n+1)}{2}-\frac{n(n+1)}{2}$ moves. This is because the number of moves required to move the left-most $a$ to the left-most position is exactly its position minus 1, the second left-most a requires its position minus 2, etc., so in the end we get that the total number of moves required is the sum of all the positions of the $a$s minus $1+2+...+n$. Notice that each of these moves will only affect the relative positions of the $a$s in relation to the $b$s and $c$s. Thus, if we want to "unscramble" the $b$s and $c$s, these will require a totally distinct set of moves. So we repeat the argument from before. We number all the positions of the $b$s and $c$s with the numbers $1,2,...,2n$, and we add the the numbers associated with $b$s and $c$s. One of these numbers must exceed $\frac{\frac{2n(2n+1)}{2}}{2}=\frac{n(2n+1)}{2}$. WLOG let this number be the one associated with the $b$s. Thus to move all the $b$s to the left of all the $c$s, by the same argument as before, we will need at least $\frac{n(2n+1)}{2}-\frac{n(n+1)}{2}$ moves. Thus the total number of moves required is greater than or equal to $$\frac{n(3n+1)}{2}-\frac{n(n+1)}{2}+\frac{n(2n+1)}{2}-\frac{n(n+1)}{2}=\frac{3n^2}{2}$$ and we are done.

Construct a graph whose vertices are the words, and two vertices are connected if there is a swap that leads from one to the other. We wish to show that for any vertex, there is another vertex at least $3n^2/2$ away. It suffices to show that the diameter is at least $3n^2$ (suppose $a$ and $b$ are at least $3n^2$ apart, then one of $a$ or $b$ is at least $3n^2/2$ away). But we see that $a\ldots ab\ldots bc\ldots c$ and $c\ldots cb\ldots ba\ldots a$ are at least $3n^2$ apart since the number of inversions in the former (with $a<b<c$) is $0$, and is $3n^2$ in the latter (each swap can add at most one inversion).

This is not a hard combinatorics problem at all. You may just notice the following mono invariant: For each a, assign the number of letters that happen after a that are different from a. Sum up all these values. Now you just need to catch 2 different chameleons which have numbers assigned equal to 0 and 2n^2. This is trivial: aaa...a(whatever) and (whatever)aaa...a. We're done

I'll be quite sad if this is wrong

My solution! $A = \underbrace{aa\dots a}_{n}\underbrace{bb\dots b}_{n}\underbrace{cc\dots c}_{n}$ $B = \underbrace{cc\dots c}_{n}\underbrace{bb\dots b}_{n}\underbrace{aa\dots a}_{n}$ Distance between $A$ and $B$ = The numbers of inversions. Thus, Distance between $A, B$ is $3n^2$ Thus, Distance(A, X)+Distance(B, X) $\ge 3n^2$ W.L.O.G Distance(A, X) $\ge$ Distance(B, X) Distance(A, X) $\ge \frac{3n^2}{2}$ $Q.E.D$

I love your solution IMO2115

Thank you very much

Let $M = \underbrace{aa\dots a}_{n}\underbrace{bb\dots b}_{n}\underbrace{cc\dots c}_{n}$ and $N = \underbrace{cc\dots c}_{n}\underbrace{bb\dots b}_{n}\underbrace{aa\dots a}_{n}$. I claim that we need at least $3n^2$ swaps to transform $M \to N$ and vice versa. Notice that all pairs of $(a, b), (b, c),$ and $(c, a)$ must be swapped hence a minimum of $3n^2$ swaps as desired. I claim that given any chameleon string $X$, one of $M, N$ satisfies the conditions. Suppose not, and that both operations $X \to M$ and $X \to N$ take less than $\tfrac{3n^2}{2}$ swaps. Then, note that $M \to N = M \to X \to N$ must take less than $3n^2$, a contradiction, and we are done. $\blacksquare$

First, we note that $\underbrace{aaa\cdots a}_n\underbrace{bbb\cdots b}_n\underbrace{ccc\cdots c}_n \to \underbrace{ccc\cdots c}_n\underbrace{bbb\cdots b}_n\underbrace{aaa\cdots a}_n$ requires $3n^2$ swaps. Now, one of $X \to \underbrace{aaa\cdots a}_n\underbrace{bbb\cdots b}_n\underbrace{ccc\cdots c}_n$ or $X \to \underbrace{ccc\cdots c}_n\underbrace{bbb\cdots b}_n\underbrace{aaa\cdots a}_n$ will satisfy the problem statement. Assume for contradiction that both use fewer than $\frac{3n^2}{2}$ swaps. Then, since $\underbrace{aaa\cdots a}_n\underbrace{bbb\cdots b}_n\underbrace{ccc\cdots c}_n \to X \to \underbrace{ccc\cdots c}_n\underbrace{bbb\cdots b}_n\underbrace{aaa\cdots a}_n$ takes fewer than $3n^2$ swaps, contradiction.

Suppose the position of $a$ and $c$ in the chamelon $X$ are $a_1,a_2,...,a_n$ and $c_1,c_2,...,c_n$ respectively. Now consider the chamelons $$Y_1=aa...abb...bcc...c$$$$Y_2=cc...cbb...baa...a$$Now if we want to transform $X$ to $Y_1$, the only possible move is to move the $a$'s to the left and the $c$'s to the right. Meanwhile we can do it simultaneously if and only if we swap two $a$ and $c$. Let $N(a,c)$ be the number of $i,j$ with $a_i<c_j$, and let $N(c,a)$ be the number of $i,j$ such that $a_i>c_j$. Now the number of swaps needed to transform $X$ to $Y_1$ is $$2n+1+2n+2+...+3n-(1+2+...+n)+\sum (c_i-a_i)+N(a,c)=2n^2+\sum(c_i-a_i)+N(a,c)$$By symmetry the number of moves needed to transform $X$ to $Y_2$ is $$2n^2+\sum(c_i-a_i)+N(c,a)$$They sum up to $3n^2$ therefore by pigenohle principle we can take $Y$ to be one of $Y_1$ and $Y_2$.

Let there be a chameleon A defined as $\underbrace{aaa\cdots a}_n\underbrace{bbb\cdots b}_n\underbrace{ccc\cdots c}_n$, and a Chameleon B defined as $\underbrace{ccc\cdots c}_n\underbrace{bbb\cdots b}_n\underbrace{aaa\cdots a}_n$. Let there be a graph $G$ such that in each vertex of $G$ there is a Chameleon label to it. Let us first count the number of swaps needet to go from $\underbrace{aaa\cdots a}_n\underbrace{bbb\cdots b}_n\underbrace{ccc\cdots c}_n \to \underbrace{ccc\cdots c}_n\underbrace{bbb\cdots b}_n\underbrace{aaa\cdots a}_n$. First we go from $\underbrace{aaa\cdots a}_n\underbrace{bbb\cdots b}_n\underbrace{ccc\cdots c}_n \to \underbrace{bbb\cdots b}_n\underbrace{aaa\cdots a}_n\underbrace{ccc\cdots c}_n$ -- in $n^2$ swaps. Then from $\underbrace{bbb\cdots b}_n\underbrace{aaa\cdots a}_n\underbrace{ccc\cdots c}_n \to \underbrace{bbb\cdots b}_n\underbrace{ccc\cdots c}_n\underbrace{aaa\cdots a}_n$----in $n^2$-swaps. and lastly we go from $\underbrace{bbb\cdots b}_n\underbrace{ccc\cdots c}_n\underbrace{aaa\cdots a}_n \to \underbrace{ccc\cdots c}_n\underbrace{bbb\cdots b}_n\underbrace{aaa\cdots a}_n$--- in $n^2$-swaps So in total we need $3n^2$ swaps to go $\underbrace{aaa\cdots a}_n\underbrace{bbb\cdots b}_n\underbrace{ccc\cdots c}_n \to \underbrace{ccc\cdots c}_n\underbrace{bbb\cdots b}_n\underbrace{aaa\cdots a}_n$. Let there be a chameleon $C$ between the vertices $A$ and $B$, let denote $|AX|$-as the length of AX(e.g. the number of swaps needed to go from $A->X$) so we have that $|AX|+|XB|>=\tfrac{3n^2}{2}$, So one of them will be less than $\tfrac{3n^2}{2}$ swaps, $\blacksquare$

Let $f(A,B)$ denote the minimum number of swaps required to go from $A \mapsto B$. First we have an important claim. Claim: Let $A=\underbrace{aa\cdots a}_{n}\underbrace{bb\cdots b}_{n}\underbrace{cc\cdots c}_{n}$ and let $A'$ be the reverse of $A$ then $f(A,A')=3n^2$. Proof: Notice that we need to swap every possible pair of $(a,b),(b,c),(c,a)$ which take $n^2$ steps each so we need atleast $3n^2$ steps and we can check that it is infact possible to do it in $3n^2$ steps $\qquad \square$ FTSOC assume that there exists a chameleon $X$ such that for every other chameleon $Y$ we can go from $X \mapsto Y$ in $< \tfrac{3n^2}{2}$ steps. . Notice that by our assumption we mus have that $$f(Y,Z) \leq f(X,Y)+f(X,Z) < 3n^2$$for any two chameleons $Y,Z$. But this contradicts our claim $\qquad \blacksquare$

The idea is to count the number of inversions. Observe that bubble sort changes inversion count by exactly $1$ at any step. Now, consider changing $aa \cdots a bb \cdots b cc \cdots c$ to $cc \cdots c bb \cdots b aa \cdots a$. Observe that there are $3n^2$ inversions here, so it requires at least $3n^2$ moves. For an arbitrary sequence $S$, let $x$ be the difference in the number of inversions to $ABC$, and $y$ be the difference in the number of inversions to $CBA$. Evidently $x + y = 3n^2$, and so one of the two is greater than or equal to $\frac{3n^2}{2}$. Thus we are done.

Consider the strings $S_1 = aa\ldots a bb \ldots b cc \ldots c$ and $S_2 = cc \ldots c bb \ldots b aa \ldots a,$ If we impose an ordering $a < b < c,$ then we see that the latter string has $\tbinom{3}{2} n^2 = 3n^2$ inversions. Note that each swap can change the inversion number by at most one, so it takes at least $3n^2$ swaps to change the first string to the second. Let $m_1$ be the minimum number of moves to transform $X$ into $S_1,$ and let $m_2$ be the minimum number of moves to transform $X$ into $S_2.$ Note that $m_1+m_2 \geq 3n^2,$ as any pair of transformations from $X$ to $S_1$ and $S_2$ gives a transformation from $S_1$ to $S_2$ by composing. Thus, at least one of $m_1, m_2$ is at least $3n^2/2,$ and we find a valid $Y = S_1$ or $S_2$ correspondingly. $\blacksquare$ It's also a fun exercise to show that in general, for a string $X$ of length $n$ containing $k$ different letters (possibly different number of occurences for each letter), consider the $k!$ strings that are permutations of $X$ and have all same letters in contiguous blocks (ex. $aaabbccccdde$ etc.): at least one of these strings is an optimal $Y$ that maximizes the number of swaps needed to transform $X$ to it by swapping.

dame dame

Consider Chameleons $A=aa\dots abb\dots bcc\dots c$ and $B = cc\dots cbb\dots baa\cdots a.$ Let $f(a,b)$ denote the number of ordered pairs $(a,b)$ of Chameleon $X.$ Define for others similarly. As a result, $$f(a,b) + f(b,a) = f(a,c) + f(c,a) = f(b,c) + f(c,b) = n^2.$$Consider the expressions, for chameleon $X,$ $$F(X) = f(a,b) + f(b,c) + f(a,c) \qquad G(X) = f(b,a) + f(c,b) + f(c,a).$$Note that every swap changes $F(X)$ and $G(X)$ by at most 1. Hence, one needs at least $F(A) - F(X) = 3n^2 - F(X) = M$ moves to transpose $X$ to $A$ and at least $G(B) - G(X) = 3n^2 - G(X) = N$ to transpose $X$ to $B.$ Moreover, since $M+N = 6n^2 - F(X) - G(X) = 3n^2,$ then at least one of $M$ and $N$ is $\ge 3n^2/2.$ $\blacksquare$

Let $C_1$ be the Chameleon $aa...abb...bcc...c$ and let $C_2$ be the Chameleon $cc...cbb...baa..a$. We claim we can always use either $C_1$ or $C_2$ as Chameleon $Y$. Define $f(a,b) = f(a,c) = f(b,c) = 1$ and $f(b,a) = f(c,a) = f(c,b) = -1$. Let the score of a Chameleon be the sum, over all pairs of distinct letters $L_1$ and $L_2$ such that $L_1$ is to the left of $L_2$, of $f(L_1,L_2)$. It is easy to see that $f(C_1) = 3n^2$ and $f(C_2) = -3n^2$. Furthermore, a swap changes the score of a Chameleon by $\pm 2$. Now let $C$ be any Chameleon. If $C$ has a nonnegative score, at least $\frac{3}{2}n^2$ moves would be required to transform $C$ into $C_2$, and if $C$ has a nonpositive score, at least $\frac{3}{2}n^2$ moves would be required to transform $C$ into $C_1$. We are done.

Kinda cute ig Let $A=\underbrace{aa...a}_{n}\underbrace{bb...b}_{n}\underbrace{cc...c}_{n}$ and $B=\underbrace{cc...c}_{n}\underbrace{bb...b}_{n}\underbrace{aa...a}_{n}$. Let us show that for all arrangements $X$ it is impossible to transform $X$ to $A$ and $B$ both in less then $\frac{3n^2}{2}$ moves. Claim: You cannot transform $A$ into $B$ in less than $3n^2$ moves. We define the score of any letter $x$ thusly. If $x=a$ the score is the number of $b$'s and $c$'s the right of $x$. If $x=b$ it is the number of $a$'s to the left and $c$'s to the right of $x$. And, if $x=c$ then it is the number of $a$'s and $b$'s the left of $x$. Clearly, the sum of scores in $A$ and $B$ are $6n^2$ and $0$, respectively. And, the score is decreased by at most $2$ after each move. Thus, we require at least $3n^2$ moves. $\square$ If we have $A \underbrace{\rightarrow \cdots \rightarrow}_{p} X \underbrace{\rightarrow \cdots \rightarrow}_{q} B$ then $p+q \geq 3n^2$. Thus, at least one of $p$ or $q$ is $\geq \frac{3n^2}{2}$. $\blacksquare$

Wao nice.

, contradiction

Really nice C2. Suppose that $a<b<c$. If there are two indices $s_i$ and $s_j$ in the string such that $s_i>s_j,$ call this a misordering. Notice that $aa\cdots abbb\cdots bcc\cdot c$ has $0$ misorderings and $cc\cdots cbb\cdots baa\cdots a$ has $3n^2$ misorderings. Thus, for any string, by pigeonhole, we can find a string that has a number of misorderings differing by at least $\frac{3n^2}{2},$ and since each transposition can resolve or create at most one misordering, we are done.

The number of inversions wrt to the topological orders rgb and wrt the order bgr sum to $3n^2$ clearly. So wrt one order has at least $\frac{3n^2}{2}$ inversions by pigeonhole. Each swap clearly at most one inversion, so we are done by taking $Y$ to be the perfectly sorted string over that order.

ISL marabot solve Let $A=aaa\ldots a bbb\ldots b ccc\ldots c$ and $B=ccc\ldots c bbb\ldots b aaa\ldots a$. Claim: It takes at least $3n^2$ swaps to produce $A$ from $B$ or vice versa. Proof: WLOG we are going from $A$ to $B$. Then every $a$ must be swapped with every $b$, every $b$ must be swapped with every $c$, and every $a$ must be swapped with every $a$. This gives at least $n^2+n^2+n^2=3n^2$ ways and this is clearly achievable. $\blacksquare$ Now back to the problem. Let $Y$ be either $A$ or $B$. If the number of steps from $X$ to $A$ and $X$ to $B$ are fewer than $\frac{3n^2}{2}$, then consider $A\to X\to B$, which must be less than $3n^2$ steps, contradiction. So either $X\to A$ or $X\to B$ is not fewer than $\frac{3n^2}{2}$ steps.

We claim either $C_1 = \underbrace{aaa\cdots a}_n\underbrace{bbb\cdots b}_n\underbrace{ccc\cdots c}_n$ or $C_2 = \underbrace{ccc\cdots c}_n\underbrace{bbb\cdots b}_n\underbrace{aaa\cdots a}_n$ work. Define the distance between two chameleons to be the smallest number of swaps necessary to change one for the other (note that since swaps are reversible, triangle inequality holds). We'll use the following Claim: The distance between $C_1$ and $C_2$ is $3n^2$. Proof: Consider a sequence of swaps $s_1,\dots,s_k$ that transforms $C_1$ in $C_2$. Then, the leftmost $a$ letter of $C_1$ goes into the leftmost $a$ of $C_2$, the second leftmost goes into the second leftmost and so on. Due to this, each $a$ or $c$ needs to participate in at least $2n$ swaps, hence so does each $b$. Therefore, by counting the number of pairs $(letter,swap)$ such that the letter took part in the swap, we conclude that \[2k \ge 2n^2+2n^2+2n^2\]\[k \ge 3n^2,\]which proves the claim. Now, to conclude, note that if a chameleon was a distance smaller than $3n^2/2$ to both $C_1$ and $C_2$, the distance between $C_1$ and $C_2$ would be smaller than $3n^2$, contradicting our claim. $\blacksquare$

Let $C_1$ and $C_2$ be the chameleons: $$C_1=\underbrace{aa\ldots a}_{n\text{ times}}\underbrace{bb\ldots b}_{n\text{ times}}\underbrace{cc\ldots c}_{n\text{ times}}$$and $$C_2=\underbrace{cc\ldots c}_{n\text{ times}}\underbrace{bb\ldots b}_{n\text{ times}}\underbrace{aa\ldots a}_{n\text{ times}}.$$ Claim: $C_1$ can be changed into $C_2$ (and vice versa) in less than or equal to $3n^2$ swaps The steps are reversible, so it suffices to show that $C_2$ can be changed into $C_1$ in less than or equal to $3n^2$ swaps. We can label $C_1,C_2$ as: $$C_1=\underbrace{a_1a_2\ldots a_n}_{n\text{ times}}\underbrace{b_1b_2\ldots b_n}_{n\text{ times}}\underbrace{c_1c_2\ldots c_n}_{n\text{ times}}$$and $$C_2=\underbrace{c_1c_2\ldots c_n}_{n\text{ times}}\underbrace{b_1b_2\ldots b_n}_{n\text{ times}}\underbrace{a_1a_2\ldots a_n}_{n\text{ times}}.$$Bubble sort suffices. Then let $X$ be an arbitrary chameleon. Say that $X$ can be changed into $C_1$ in $s$ swaps and $C$ can be changed into $C_2$ in $t$ swaps. Then $s+t$ is at most $3n^2$, but then $\max\{s,t\}\ge\frac{3n^2}2$. So choosing either $Y=C_1$ or $Y=C_2$ must be done in more than $\frac{3n^2}2$ swaps.

Assume towards a contradiction that there is some chameleon $X$ which can be changed into any other chameleon in under $\frac{3n^2}{2}$. Then, consider any two chameleons $Y$ and $Z$. Because $Y$ can be changed into $X$ in under $\frac{3n^2}{2}$ moves and $X$ can be changed into $Z$ in under $\frac{3n^2}{2}$ moves, $Y$ can be changed into $Z$ in under $3n^2$ moves. Let $Y$ be the chameleon with all the $a$'s first, then the $b$'s, then the $c$'s. Let $Z$ be the reverse of $Y$. For a chameleon $A$, let $f(A)$ be the number of ordered pairs $(x, y)$ of letters in $A$ such that $x$ comes before $y$ alphabetically and is before $y$ in $A$. Making a swap can decrease $f(A)$ by at most $1$ since it only changes the ordering of one pair. Since $f(Y)=3n^2$ and $f(Z)=0$, it takes at least $3n^2$ swaps to get from $Y$ to $Z$, a contradiction.

We claim that it takes at least $3n^2$ swaps to go from $a^nb^nc^n$ to $c^nb^na^n.$ $~$ Let $S(x)$ be the number of pairs $(a,b)$ in chameleon $\mathcal{C}$ for which $a$ appears after $b$, plus the number of pairs $(a,c)$ for which $a$ appears after $c$, plus the number of pairs $(b,c)$ for which $b$ appears after $c$. Clearly, every swap affects exactly one pair, so for any chameleon $\mathcal{C}$ achievable from $a^nb^nc^n$ after $k$ moves, $S(\mathcal{C})\le k.$ Note that $S(c^nb^na^n)=3n^2$ so we're done. $~$ Now, for any chameleon $X$, if it takes $<3n^2/2$ swaps to reach $a^nb^nc^n$ and $<3n^2/2$ swaps to reach $c^nb^na^n$ then $a^nb^nc^n\to X\to c^nb^na^n$ uses less than $3n^2$ swaps, contradiction.

Consider chameleons $A=\underbrace{aa\cdots a}_n\underbrace{bb\cdots b}_n\underbrace{cc\cdots c}_n,C=\underbrace{cc\cdots c}_n\underbrace{bb\cdots b}_n\underbrace{aa\cdots a}_n;$ notice that sequence of changes $A\rightarrow X\rightarrow C$ use at least $3n^2$ swaps, so we can't obtain at least one of $A,C$ from $X$ with fewer than $\frac{3n^2}{2}$ swaps, done.

Let $a$ be 0, $b$ be 1, and $c$ be 2. Consider the increasing-sorted string $I$ and the decreasing-sorted string $D$. It takes $3n^2$ steps to go from one of these strings to the other one, since there are $3n^2$ inversions. Therefore, for any given starting string, the sum of the number of moves needed to reach $I$ and the number of moves need to reach $D$ is at least $3n^2$, so there is one of $I$ and $D$ that takes at least $3n^2/2$ moves, so we are done.

Consider chameleons $a \ldots a b \ldots b c \ldots c$ and $c \ldots c b \ldots b a \ldots a$. We require at least $3n^2$ swaps to change one to the other, as we have $n^2$ switches between $a$ and $b$, $a$ and $c$, and $b$ and $c$. Thus there cannot exist a chameleon which can switch to both in under $\frac{3n^2}{2}$ swaps. $\blacksquare$

Consider the chameleon $a\dots ab \dots bc \dots c$ and its inversion. It requires $3n^2$ swaps to get from one to the other, $n^2$ per groups of letters swapping. Hence, if it takes less than $3n^2/2$ swaps to get to one, it must take more than $3n^2/2$ to get to the other. $\square$

Consider the chameleons $a \dots a b \dots b c \dots c$ and $c\dots c b\dots b c \dots c.$ It is clear that we require at minimum $3n^2$ swaps to get from one to the other. Thus, for every chameleon $X,$ one of these two chameleons will take at least $3n^2/2$ swaps, otherwise there is a contradiction.

Let $c_j$ be the character in the $j$th position. Define an inversion to be whenever there exist two numbers $i$ and $j$ such that $i < j$, yet $c_i$ is lexicographically larger than $c_j$. Then the sequence $S = AAA \dots ABBB\dots BCCC \dots C$ has 0 inversions, whereas $T = CCC \dots CBBB \dots BAAA \dots A$ has $3n^2$ inversions. Every operation to a sequence will either increase the number of inversions by $1$, maintain the same number of inversions, or decrease it by $1$. Thus, it follows that if we are given some sequence $X$ with $I$ inversions where $0 \leq I \leq 3n^2$. Changing $X$ to $T$ will require at least $3n^2-I$ operations whereas changing $X$ to $S$ will require at least $I$ operations. Note that $\max(I, 3n^2 - I) \geq \frac{3n^2}{2}$, thereby proving the intended result.

Take the chameleons A - $aa \cdots abb \cdots bcc \cdots c$ and B - $cc \cdots cbb \cdots baa \cdots a$. Now if we want to go from $A \to B$, we need at least $3n^2$ swaps, since we have $n^2$ switches between a and b, a and c, b and c. Now take a chameleon X, and assume that it takes less than $\frac{3}{2}n^2$ swaps to go from $X \to A$ or $X \to B$ $\Rightarrow$ $A \to X \to B$ takes less than $\frac{3}{2}n^2 + \frac{3}{2}n^2 = 3n^2$ swaps - contradiction, since it takes at least $3n^2$ swaps to go from $A \to B$ $\Rightarrow$ we need at least $\frac{3}{2}n^2$ swaps $\Rightarrow$ we are ready.

Let $f$ be the number of $a\dots b$ plus $b\dots c$ plus $a\dots c$. $f$ changes exactly $1$ in each move. $f$ of the sequence $a\dots ab\dots bc\dots c$ is $3n^2$ and $c\dots b\dots a$ is $0$ hence for any chameleon, there exists another one with distance at least $3n^2/2$ as desired.$\blacksquare$

Consider the sequences \[A=\underbrace{a\dots a}_{n}\underbrace{b\dots b}_{n}\underbrace{c\dots c}_{n},\qquad B=\underbrace{c\dots c}_{n}\underbrace{b\dots b}_{n}\underbrace{a\dots a}_{n}.\]We attempt to swap from $A$ to $B$. There exist $3n^2$ pairs of "incorrectly-ordered" letters $ab$, $bc$, and $ac$ in $A$ which must be reversed to $ba$, $cb$, and $ca$ in $B$. We can correct one pair at a time per swap, yielding at least $3n^2$ swaps needed. Assume that $X$ can be changed to both $A$ and $B$ in less than $1.5n^2$ swaps. Then $A\to X\to B$ requires less than $3n^2$ swaps, a contradiction. $\blacksquare$

Chameleons can play games now apparently... ? Call a pair of letters nice if the two letters read left to right are either $(a,b)$, $(b,c)$ or $(c,a)$. The total number of nice pairs in a chameleon could be as low as $0$ ($ccbbaa$) or as high as $3n^2$ ($aabbcc$), and it changes by at most one in a swap, so for $Y$, just pick the one of the two extremes that is further away from $X$.