uniolympiads Ελληνικά

IMC 1997, Day 2, Problem 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.

Original from the official 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.

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

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.

Transcribed from the official solutions, page 4. 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?