Track / Stage 6 / 368 of 400 #2008 of 2604

Problem 2008

National Olympiad, first round

Combinatorics Difficulty 6.9 Prove it Mongolian Mathematical Olympiad · Mongolia

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 \rightarrow azzbc$ .
(2) Any subword of the form $xyz$ can be changed to $zyx$ . For example, $cabc \rightarrow ccba$ .
(3) Any subword of the form $xyyx$ can be omitted. For example, $abcaacc \rightarrow 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$ .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.