IMC 1999 · Problem 5

Let $S$ be the set of all words consisting of the letters $x$, $y$, $z$, and consider an equivalence relation $\sim$ on $S$ satisfying the following conditions: for arbitrary words $u, v, w \in S$

(i) $uu \sim u$;

(ii) if $v \sim w$, then $uv \sim uw$ and $vu \sim wu$.

Show that every word in $S$ is equivalent to a word of length at most $8$.