Track / Stage 6 / 147 of 400 #1787 of 2604

Problem 1787

National Olympiad, first round

Algebra Difficulty 6.2 Prove it Iranian Mathematical Olympiad · Iran

Function $f$ is said to generate function $g$ (and denote it by $f \to g$ ), if $g$ can be written as the composition of function $f$ with itself for several times; i.e., natural number $k$ exists for which $f \circ f \circ \dots \circ f = g$ ( $k$ times).
We want to explore some properties of this relation. For example, it can easily be shown that if $f \to g$ and $g \to h$ , then $f \to h$ . (transitivity)

a) Show that two functions $f \neq g: \mathbb{R} \to \mathbb{R}$ exist for which $f \to g$ and $g \to f$ .

b) Prove that for each function $f: \mathbb{R} \to \mathbb{R}$ there are a finite number of functions $g: \mathbb{R} \to \mathbb{R}$ for which $f \to g$ and $g \to f$ .

c) Does a function $g: \mathbb{R} \to \mathbb{R}$ exist such that the only function that generates it is itself?

d) Does there exist a function that generates functions $x^3$ and $x^5$ ?

e) Prove that if there exists a function that generates two linear polynomials $P$ and $Q$ , then there exists a linear polynomial that generates both $P$ and $Q$ .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

a) Let
$f(x) = \begin{cases} 2 & x = 1 \\ 3 & x = 2 \\ 1 & x = 3 \\ x & x \notin \{1, 2, 3\} \end{cases} \qquad g(x) = \begin{cases} 3 & x = 1 \\ 1 & x = 2 \\ 2 & x = 3 \\ x & x \notin \{1, 2, 3\} \end{cases}$
It is easy to check that $g^2 = f$ and $f^2 = g$ .

b) Suppose $g$ is a function that $f \to g$ and $g \to f$ . It means that there are integers $m$ and $n$ such that $f^m = g$ and $g^n = f$ . So $f^{mn} = f$ and $f$ generates at most $mn - 1$ functions. Therefore, there are only a finite number of functions $g$ .

c) Define $g: \mathbb{R} \to \mathbb{R}$ as follows:
$g(x) = \begin{cases} x + 1 & x \in \mathbb{Z} \\ x & x \notin \mathbb{Z} \end{cases}$
Let $f$ be a real function such that $f \to g$ ( $f^k = g$ ). Note that $g$ is bijective, and hence $f$ is bijective too. If $f(z_0) \notin \mathbb{Z}$ for some $z_0 \in \mathbb{Z}$ , we have:
$f(z_0) = g(f(z_0)) = f^{k+1}(z_0) = f(g(z_0)) = f(z_0 + 1),$
which leads to a contradiction since $f$ is injective. Hence $f(\mathbb{Z}) \subseteq \mathbb{Z}$ . Now, for each integer number $z$ we have:
$f(z + 1) = f(g(z)) = f^{k+1}(z) = g(f(z)) = f(z) + 1.$
Therefore, $f(z) = z + t$ for some integer number $t$ and every integer number $z$ . Next, for every integer number $z$ we have:
$z + kt = f^k(z) = g(z) = z + 1 \Rightarrow kt = 1 \Rightarrow k = t = 1.$
Therefore, $f$ must be equal to $g$ .

d) If $f^m(x) = x^3$ and $f^n(x) = x^5$ for some $m, n \in \mathbb{N}$ , then $x^{3n} = f^{mn}(x) = x^{5m}$ . Therefore, $3^n = 5^m$ . But this equation does not have any solutions in natural numbers.

e) First, we prove a lemma.
Lemma 1. Let $f: \mathbb{R} \to \mathbb{R}$ be a function and $a > b$ two integer numbers such that $f^a$ and $f^b$ are both polynomials of degree 1. Then $f^{a-b}$ is also a polynomial of degree 1.
Proof. $f^{a-b}(x) = f^a \circ ((f^b)^{-1}(x))$ , and the inverse of every polynomial with degree 1 is again a polynomial of degree 1. $\square$

Now, assume that $f^m = P$ , $f^n = Q$ and $(m, n) = d$ for some $m, n, d \in \mathbb{N}$ . Referring to the lemma and using Euclidean algorithm, $f^d$ is a polynomial of degree 1 that generates both $P$ and $Q$ .

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.