uniolympiads English

IMC 1999, Ημέρα 2, Θέμα 5

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

(i) uu∼uuu \sim u;

(ii) if v∼wv \sim w, then uv∼uwuv \sim uw and vu∼wuvu \sim wu.

Show that every word in SS is equivalent to a word of length at most 88.

Πρωτότυπο από το επίσημο PDF5. Let S be the set of all words consisting of the letters x, y, z, and consider an equivalence relation ∼ on S satisfying the following conditions: for arbitrary words u, v, w ∈ S (i) uu ∼ u; (ii) if v ∼ w, then uv ∼ uw and vu ∼ wu. Show that every word in S is equivalent to a word of length at most 8. (20 points)

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

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

If vv contains a single letter, say xx, write uu in the form u=u1xu2u=u_1xu_2, and choose w=u2w=u_2. Then uvw=(u1xu2)xu2=u1((xu2)(xu2))∼u1(xu2)=uuvw=(u_1xu_2)xu_2=u_1((xu_2)(xu_2))\sim u_1(xu_2)=u.

In the general case, let the letters of vv be a1,…,aka_1,\dots,a_k. Then one can choose some words w1,…,wkw_1,\dots,w_k such that (ua1)w1∼u(ua_1)w_1\sim u, (ua1a2)w2∼ua1(ua_1a_2)w_2\sim ua_1, …\dots, (ua1…ak)wk∼ua1…ak−1(ua_1\dots a_k)w_k\sim ua_1\dots a_{k-1}. Then u∼ua1w1∼ua1a2w2w1∼…∼ua1…akwk…w1=uv(wk…w1)u\sim ua_1w_1\sim ua_1a_2w_2w_1\sim\ldots\sim ua_1\dots a_kw_k\dots w_1=uv(w_k\dots w_1), so w=wk…w1w=w_k\dots w_1 is a good choice.

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

Write aa in the form a=bcda=bcd, where bb and dd are the first and last four letter of aa, respectively. We prove that a∼bda\sim bd.

It is easy to check that bb and dd contains all the three letters xx, yy and zz, otherwise their length could be reduced. By the lemma there is a word ee such that b(cd)e∼bb(cd)e\sim b, and there is a word ff such that def∼ddef\sim d. Then we can write

a=bcd∼bc(def)∼bc(dedef)=(bcde)(def)∼bd.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 xx and the second is yy, it is easy (but a little long) to check that there are 18 words of length 9 which cannot be written in the form uvvwuvvw.

For five of these words there is a 2-step solution, for example

xyxzyzx zy‾∼xy xzyz xzyz‾y∼xyx zy zy‾∼xyxzy.xyxzyzx\ \underline{zy}\sim xy\ \underline{xzyz\ xzyz}y\sim xyx\ \underline{zy\ zy}\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=xyzyxzxyza=xyzyxzxyz, we have set b=xyzyb=xyzy, c=xc=x, d=zxyzd=zxyz, e=xyxzxzyxyzye=xyxzxzyxyzy, f=zyxyxzyxzxzxzxyxyzxyzf=zyxyxzyxzxzxzxyxyzxyz. The longest word in the algorithm was

bcdedef=xyzyxzxyzxyxzxzyxyzyzxyzxyxzxzyxyzyzyxyxzyxzxzxzxyxyzxyz,bcdedef=xyzyxzxyzxyxzxzyxyzyzxyzxyxzxzyxyzyzyxyxzyxzxzxzxyxyzxyz,
which is of length 46. This is not the shortest way: reducing the length of word aa can be done for example by the following steps:
xyzyxzx yz‾∼xyzyxz xyzy‾ z∼xyzyxzxy zyx‾ yzyz∼xyzyxz xyzyxz‾ yx yz yz‾∼xy zyx zyx‾ yz∼xyzyxyz.xyzyxzx\ \underline{yz}\sim xyzyxz\ \underline{xyzy}\ z\sim xyzyxzxy\ \underline{zyx}\ yzyz\sim\underline{xyzyxz\ xyzyxz}\ yx\ \underline{yz\ yz}\sim xy\ \underline{zyx\ zyx}\ yz\sim xyzyxyz.
(The last example is due to Nayden Kambouchev from Sofia University.)

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 2–3. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;