IMC 1999, Day 2, Problem 5
Let be the set of all words consisting of the letters , and consider an equivalence relation on satisfying the following conditions: for arbitrary words
(i) ;
(ii) if , then and .
Show that every word in is equivalent to a word of length at most .
Original from the official PDF

This transcription was compared symbol by symbol with the original, but not yet by a person.
Work for at least 45 minutes before opening the solution.
Official solution
Solution. First we prove the following lemma: If a word contains at least one of each letter, and is an arbitrary word, then there exists a word such that .
If contains a single letter, say , write in the form , and choose . Then .
In the general case, let the letters of be . Then one can choose some words such that , , , . Then , so is a good choice.
Consider now an arbitrary word , which contains more than 8 digits. We shall prove that there is a shorter word which is equivalent to . If can be written in the form , its length can be reduced by . So we can assume that does not have this form.
Write in the form , where and are the first and last four letter of , respectively. We prove that .
It is easy to check that and contains all the three letters , and , otherwise their length could be reduced. By the lemma there is a word such that , and there is a word such that . Then we can write
Remark. Of course, it is enough to give for every word of length 9 an shortest shorter word. Assuming that the first letter is and the second is , it is easy (but a little long) to check that there are 18 words of length 9 which cannot be written in the form .
For five of these words there is a 2-step solution, for example
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 , we have set , , , , . The longest word in the algorithm was
Transcribed from the official solutions, pages 2–3. This transcription has not been checked a second time; if in doubt, look at the original.
Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.
How did it go?
Moves you mark come back sooner in triage.