uniolympiads English

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

Let XX be an arbitrary set, let ff be an one-to-one function mapping XX onto itself. Prove that there exist mappings g1,g2 ⁣:X→Xg_1, g_2\colon X \to X such that f=g1∘g2f = g_1 \circ g_2 and g1∘g1=id=g2∘g2g_1 \circ g_1 = id = g_2 \circ g_2, where idid denotes the identity mapping on XX.

Πρωτότυπο από το επίσημο PDFLet X be an arbitrary set, let f be an one-to-one function mapping X onto itself. Prove that there exist mappings g 1 , g 2 : X → X such that f = g 1 ◦ g 2 and g 1 ◦ g 1 = id = g 2 ◦ g 2 , where id denotes the identity mapping on X.

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

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

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

Επίσημη λύση

Solution. Let fn=f∘f∘⋯∘f⏟n timesf^n = \underbrace{f \circ f \circ \cdots \circ f}_{n \text{ times}}, f0=idf^0 = id, f−n=(f−1)nf^{-n} = (f^{-1})^n for every natural number nn. Let T(x)={fn(x):n∈Z}T(x) = \{f^n(x) : n \in \mathbb{Z}\} for every x∈Xx \in X. The sets T(x)T(x) for different xx's either coinside or do not intersect. Each of them is mapped by ff onto itself. It is enough to prove the theorem for every such set. Let A=T(x)A = T(x). If AA is finite, then we can think that AA is the set of all vertices of a regular nn polygon and that ff is rotation by 2πn\dfrac{2\pi}{n}. Such rotation can be obtained as a composition of 2 symmetries mapping the nn polygon onto itself (if nn is even then there are axes of symmetry making πn\dfrac{\pi}{n} angle; if n=2k+1n = 2k+1 then there are axes making k2πnk\dfrac{2\pi}{n} angle). If AA is infinite then we can think that A=ZA = \mathbb{Z} and f(m)=m+1f(m) = m + 1 for every m∈Zm \in \mathbb{Z}. In this case we define g1g_1 as a symmetry relative to 12\dfrac12, g2g_2 as a symmetry relative to 0.

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

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

Πώς πήγε;