Len 'n' be a positive integer. Define a 'chameleon' to be any sequence
of 3n letters 'a', 'b', and 'c'. Define a 'swap' to be the transposition
of two adjacent letters in a chameleon.
Prove that for any chameleon X, there exists a chameleon Y such that
X cannot be changed to Y using fever than 3n^2 / 2 swaps.

-----------------------

Something like reflected chameleon by center?
Does not work, the chameleon cound be symmetric (if n is even)

...

Or we get Y be rotating a->b->c->a?
Let X be a chameleon
  abcabcabc...abc
then Y is
  bcabcabca...bca
In every triple, I need
  abc -> bac -> bca
2 swaps.
That is 2n swaps in total to get X -> Y.
  < 3n^2 / 2 (at least for big n)
Also does not work.

...

Idea1.
  What about proving that there exists Y without explicit construction?
Idea2.
  Or, Y could be also one of the chameleons
  a..ab..bc..c
  b..ba..ac..c
  ...

Ad idea2.
How many swaps do I need for getting
  a..ab..bc..c -> c..cb..ba..a ?
If it is more than 3n^2, then every chameleon is distant at least
  3n^2 / 2 steps from "a..ab..bc..c" or "c..cb..ba..a".
So, let's count the steps.
  aaaaa bbbbb ccccc
  -- 2n steps -->
  aaaa bbbbb ccccc a
  -- 2n steps -->
  aaa bbbbb ccccc aa
  ...
  after 2n^2 steps from the start
  ...
  bbbbb ccccc aaaaa
  -- n steps ->
  c bbbbb cccc aaaaa
  -- n steps ->
  cc bbbbb ccc aaaaa
  ...
  after further n^2 steps
  ...
  ccccc bbbbb aaaaa
  That is 3n^2 steps in total.

This is really promissing, now I just need to prove that this
  a..ab..bc..c -> c..cb..ba..a
  process is optimal.

If I look only at 'a's, I can move only one 'a' per move to the right.
So the sum of the positions of 'a's will raise always by only 1.
If I get them from the left, to the right, I needed at least as many
steps as
  sum_of_a_positions(c..cb..ba..a) - sum_of_a_positions(a..ab..bc..c)
  that is
  (2n+1 + 2n+2 + ... + 3n) - (1 + 2 + ... + n) = 2n^2

Similarly, I want to estimate the positions of 'c's, but now I need
to take care of the fact that the swap ac -> ca improves the state
of the 'a' and the 'c' simultaneously.
* Solution:
  Ignore 'a's in evaluating the positions of 'c's, that is
  by a position of a 'c' I mean its position only among the 'c's and 'b's.
  * Then, any step swapping an 'a' does not affect any position of any 'c'.
  * And a bc-swap can lower a position of just one 'c' by just one.
* So we need at least the following number of further steps:
  sum_of_c_positions(a..ab..bc..c) - sum_of_c_positions(c..cb..ba..a)
  that is
  (1 + 2 + ... + n) - (n+1 + n+2 + ... + 2n) = n^2

In the end, we need at least 3n^2 swaps to get from
  a..ab..bc..c
  to
  c..cb..ba..a
Therefore, for any chameleon X, if we choose
  Y = a..ab..bc..c, or Y = c..cb..ba..a,
we need at least 3n^2/2 swaps to get from X to Y.

In other words, it is not possible to get from X to Y in less than
3n^2/2 swaps.

Problem Solved!