IMC 1999, Ημέρα 2, Θέμα 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 .
Πρωτότυπο από το επίσημο PDF

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.
Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.
Επίσημη λύση
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
Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 2–3. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.
Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.
Πώς πήγε;
Οι κινήσεις που σημειώνεις επιστρέφουν νωρίτερα στη διαλογή.