59th Ukrainian National Mathematical Olympiad

Question

There is an infinite sequence of letters a and b. In this sequence, one can perform a substitution abb baa. It is known that regardless of the order of these substitutions, one can only make a finite number of them. Prove that, in that case, substitutions aabb bbaa can also be made only a finite number of times. (Arsenii Nikolaiev)

Accepted Answer

Since there can only be made a finite number of substitutions, there is a number N, starting from which substitutions are not possible. That means that there are no pairs of subsequent letters b. Because, otherwise, on the left from them there is letter a, and substitution is possible. But then the second type of substitution is not possible, either, because starting from N, there is no pair of letters b. And all other pairs of b get moved to the left by each second-type substitution. And there is only a finite number of such moves possible.