MathDB

Let

n

be a positive integer. Define a chameleon to be any sequence of

3n

letters, with exactly

n

occurrences of each of the 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 fewer than

3n^2/2

swaps.

Problem Statement