IMC 1999 · Day 2 · P11

First we prove the following lemma: If a word $u \in S$ contains at least one of each letter, and $v \in S$ is an arbitrary word, then there exists a word $w \in S$ such that $uvw \sim u$.

If $v$ contains a single letter, say $x$, write $u$ in the form $u = u_1 x u_2$, and choose $w = u_2$. Then $uvw = (u_1 x u_2) x u_2 = u_1 ((x u_2)(x u_2)) \sim u_1 (x u_2) = u$.

In the general case, let the letters of $v$ be $a_1, \dots, a_k$. Then one can choose some words $w_1, \dots, w_k$ such that $(u a_1) w_1 \sim u$, $(u a_1 a_2) w_2 \sim u a_1$, …, $(u a_1 \dots a_k) w_k \sim u a_1 \dots a_{k-1}$. Then $u \sim u a_1 w_1 \sim u a_1 a_2 w_2 w_1 \sim \dots \sim u a_1 \dots a_k w_k \dots w_1 = uv(w_k \dots w_1)$, so $w = w_k \dots w_1$ is a good choice.

Consider now an arbitrary word $a$, which contains more than 8 digits. We shall prove that there is a shorter word which is equivalent to $a$. If $a$ can be written in the form $uvvw$, its length can be reduced by $uvvw \sim uvw$. So we can assume that $a$ does not have this form.

Write $a$ in the form $a = bcd$, where $b$ and $d$ are the first and last four letter of $a$, respectively. We prove that $a \sim bd$.

It is easy to check that $b$ and $d$ contains all the three letters $x$, $y$ and $z$, otherwise their length could be reduced. By the lemma there is a word $e$ such that $b(cd)e \sim b$, and there is a word $f$ such that $def \sim d$. Then we can write $$a = bcd \sim bc(def) \sim bc(dedef) = (bcde)(def) \sim bd.$$

Remark. Of course, it is enough to give for every word of length 9 an shortest shorter word. Assuming that the first letter is $x$ and the second is $y$, it is easy (but a little long) to check that there are 18 words of length 9 which cannot be written in the form $uvvw$.

For five of these words there is a 2-step solution, for example $$xyxzyzxzy \sim xyxzyzxzyzy \sim xyxzyzy \sim xyxzy.$$ In the remaining 13 cases we need more steps. The general algorithm given by the Solution works for these cases as well, but needs also very long words. For example, to reduce the length of the word $a = xyzyxzxyz$, we have set $b = xyzy$, $c = x$, $d = zxyz$, $e = xyxzxzyxyzy$, $f = zyxyxzyxzxzxzxyxyzxyz$. The longest word in the algorithm was $$bcdedef = xyzyxzxyzxyxzxzyxyzyzxyzxyxzxzyxyzyzyxyxzyxzxzxzxyxyzxyz,$$ which is of length 46. This is not the shortest way: reducing the length of word $a$ can be done for example by the following steps: $$xyzyxzxyz \sim xyzyxzxyzyz \sim xyzyxzxyzyxyzyz \sim xyzyxzxyzyxzyxyzyz \sim xyzyxzyxyz \sim xyzyxyz.$$ (The last example is due to Nayden Kambouchev from Sofia University.)