Maths Olympiad Prep

Library / /12 of 22

Combinatorics Difficulty 6.5 National olympiad Prove it Croatia

Let nn be a positive integer. A good word is a sequence of 3n3n letters, in which each of the letters AA, BB and CC appears exactly nn times. Prove that for every good word XX there exists a good word YY such that YY cannot be obtained from XX by swapping neighbouring letters fewer than 32n2\frac{3}{2}n^2 times. (IMO Shortlist 2017)

Solution

Let us define the distance of good words XX and YY, denoted by d(X,Y)d(X, Y), as the smallest number of swaps of neighbouring letters necessary to obtain YY from XX (or vice versa). Note that d(X,Y)=d(Y,X)d(X, Y) = d(Y, X), and that for any three good words XX, YY and ZZ we have
d(X,Y)+d(Y,Z)d(X,Z). d(X, Y) + d(Y, Z) \ge d(X, Z).
Furthermore, for a good word XX denote by F(X)F(X) the number of pairs of positions where the letter in the left position is lexicographically smaller than the one in the right position, i.e. the number of pairs of the form ABAB, ACAC or BCBC. By swapping two neighbouring letters in a good word XX we get a good word XX'. If the letters were identical, those two words would be equal, so we can assume that all swaps involve pairs of different letters. If we swap different letters, we have F(X)F(X)=1|F(X) - F(X')| = 1. From this, we can conclude that
d(X,Y)F(X)F(Y) d(X, Y) \ge |F(X) - F(Y)|
for any two good words XX and YY. Observe the good words
P=AAAnBBBnCCCnandQ=CCCnBBBnAAAn P = \underbrace{AA\dots A}_n\underbrace{BB\dots B}_n\underbrace{CC\dots C}_n \quad \text{and} \quad Q = \underbrace{CC\dots C}_n\underbrace{BB\dots B}_n\underbrace{AA\dots A}_n
Note that F(P)=3n2F(P) = 3n^2 and F(Q)=0F(Q) = 0, therefore d(P,Q)3n2d(P, Q) \ge 3n^2.
Finally, for any good word XX we have
d(P,X)+d(X,Q)d(P,Q)3n2. d(P, X) + d(X, Q) \ge d(P, Q) \ge 3n^2.
Therefore, one of the good words PP and QQ cannot be obtained from XX by swapping fewer than 32n2\frac{3}{2}n^2 pairs of neighbouring letters.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.