Let be a positive integer. A good word is a sequence of letters, in which each of the letters , and appears exactly times. Prove that for every good word there exists a good word such that cannot be obtained from by swapping neighbouring letters fewer than times. (IMO Shortlist 2017)
Solution
Let us define the distance of good words and , denoted by , as the smallest number of swaps of neighbouring letters necessary to obtain from (or vice versa). Note that , and that for any three good words , and we have
Furthermore, for a good word denote by 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 , or . By swapping two neighbouring letters in a good word we get a good word . 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 . From this, we can conclude that
for any two good words and . Observe the good words
Note that and , therefore .
Finally, for any good word we have
Therefore, one of the good words and cannot be obtained from by swapping fewer than pairs of neighbouring letters.