Mongolian Mathematical Olympiad

Question

One of the following three types of operations can be performed on a word. Let x, y, z, a, b, and c be letters. (1) Any subword of the form xy can be changed to xzzy. For example, abc azzbc. (2) Any subword of the form xyz can be changed to zyx. For example, cabc ccba. (3) Any subword of the form xyyx can be omitted. For example, abcaacc abcc. Can the word baccba be obtained from the word abccab using the above operations? Note: For xyz, the subwords are x, y, z, xy, yz, and xyz, but not xz.

Accepted Answer

Answer: No. Suppose the number of a's in even positions is subtracted from the number of a's in odd positions in the word. In that case, we obtain a quantity that remains invariant under the given operations. This invariant can be used to determine if one word can be transformed into another using the specified operations. For the word abccab: * Odd-positioned a letters: 2 (positions 1 and 5) * Even-positioned a letters: 0 Thus, the invariant for abccab is 2 - 0 = 2. For the word baccba: * Odd-positioned a letters: 0 * Even-positioned a letters: 2 (positions 2 and 6) Thus, the invariant for baccba is 0 - 2 = -2. Since the invariant values for abccab and baccba are different (2 and -2, respectively), it is impossible to transform abccab into baccba using the given operations.