Recall that a palindrome is a word which is the same when we read it forward or backward. (a) We have an infinite number of cards with words $\{abc, bca, cab\}$. A word is made from them in the following way. The initial word is an arbitrary card. At each step we obtain a new word either gluing a card (from the right or from the left) to the existing word or making a cut between any two of its letters and gluing a card between both parts. Is it possible to obtain a palindrome this way? (4 points) (b) We have an infinite number of red cards with words $\{abc, bca, cab\}$ and of blue cards with words $\{cba, acb, bac\}$. A palindrome was formed from them in the same way as in part (a). Is it necessarily true that the number of red and blue cards used was equal? (6 points) Alexandr Gribalko, Ivan Mitrofanov
Problem
Source: Tournament of Towns Spring 2016
Tags: combinatorics
62861
23.02.2017 11:00
The answer to part (b) is yes (which implies that the answer to part (a) is no). We will solve part (b).
Consider a function $f: \{a, b, c\}^2 \to \{-1, 0, 1\}$ defined by
\begin{align*}
f(a, a) = f(b, b) = f(c, c) = 0,\\
f(a, b) = f(b, c) = f(c, a) = 1,\\
f(a, c) = f(b, a) = f(c, b) = -1.
\end{align*}For a word $x = x_1 x_2 \dots x_n$, define its weight to equal
\[\sum_{1 \le i < j \le n} f(x_i, x_j).\]By using the property that $\sum_{k \in \{a, b, c\}} f(x, k) = \sum_{k \in \{a, b, c\}} f(k, x) = 0$ for all $x \in \{a, b, c\}$, we can show that adding a red card to a word increases its weight by $1$, and adding a blue card decreases its weight by $1$.
However, if words $x$ and $y$ are reverses of each other, then since $f(k_1, k_2) = -f(k_2, k_1)$ for all $k_1, k_2 \in \{a, b, c\}$, we see that $f(x)= -f(y)$. Thus, if $x$ is a palindrome, then $f(x) = 0$, which means that the number of red cards and the number of blue cards to create $x$ must be equal.