Competition problem — Combinatorics

Library / /56 of 69

Combinatorics Difficulty 6.9 National olympiad Prove it 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$ .

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.

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.