Problem

Source: Iran 3rd round 2013 - final exam problem 3

Tags: function, algebra, polynomial, algebra unsolved



Real function $f$ generates real function $g$ if there exists a natural $k$ such that $f^k=g$ and we show this by $f \rightarrow g$. In this question we are trying to find some properties for relation $\rightarrow$, for example it's trivial that if $f \rightarrow g$ and $g \rightarrow h$ then $f \rightarrow h$.(transitivity) (a) Give an example of two real functions $f,g$ such that $f\not = g$ ,$f\rightarrow g$ and $g\rightarrow f$. (b) Prove that for each real function $f$ there exists a finite number of real functions $g$ such that $f \rightarrow g$ and $g \rightarrow f$. (c) Does there exist a real function $g$ such that no function generates it, except for $g$ itself? (d) Does there exist a real function which generates both $x^3$ and $x^5$? (e) Prove that if a function generates two polynomials of degree 1 $P,Q$ then there exists a polynomial $R$ of degree 1 which generates $P$ and $Q$. Time allowed for this problem was 75 minutes.