$P$ is a monic polynomial of odd degree greater than one such that there exists a function $f : \mathbb{R} \rightarrow \mathbb{N}$ such that for each $x \in \mathbb{R}$ ,\[f(P(x))=P(f(x))\](a) Prove that there are a finite number of natural numbers in range of $f$. (b) Prove that if $f$ is not constant then the equation $P(x)-x=0$ has at least two real solutions. (c) For each natural $n>1$ prove that there exists a function $f : \mathbb{R} \rightarrow \mathbb{N}$ and a monic polynomial of odd degree greater than one $P$ such that for each $x \in \mathbb{R}$ ,\[f(P(x))=P(f(x))\]and range of $f$ contains exactly $n$ different numbers. Time allowed for this problem was 105 minutes.
Problem
Source: Iran 3rd round 2014 - final exam problem 6
Tags: algebra, polynomial, function, floor function, algebra unsolved
manuel153
16.09.2014 20:09
So what about $P(x)=x$ and $f(x)=|\lfloor x\rfloor|$? This choice seems to contradict (a).
TheOverlord
16.09.2014 20:24
excuse me , I forgot to add one condition.
UK2019Project
09.04.2020 18:53
Big bump.
kris_001
10.04.2020 08:23
The part (a) and part (b) are similar by considering the Fixed-Point Iteration of $P(x)=x.$ Note that $ran(P)=\mathbb{R}$ and for any $\mathbb{N}\ni y_1\in Ran(f)$ there must exist some $y_2\in Ran(f)$ such that $P(y_2)=y_1.$ Hence we can obtain a (not unique) sequence of $y_n$ satisfying $$P(y_{i+1})=y_i,i=1,2,\cdots.$$
(a): Now we suppose that $|ran(f)|=+\infty$ and select $y_1\gg 1$ such that $P(x)=y_1$ has only one real root. Then we obtain a sequence of $y_i,i=1,2\cdots$ satisfying $$0\leq y_i< y_1, \forall i=1,2,\cdots.$$By Pigeonhole Principle, there must exist $j>i$ such that $y_j=y_i,$ which implies $y_{j-i+1}=P^{i-1}(y_j)=P^{i-1}(y_i)=y_1.$ This is a contradiction with $y_{j-i+1}<y_1.$
(b):If $P(x)=x$ has only one real root and $f$ is not a constant, then the sequence is strictly monotonic. This is a contradiction with the finiteness of $ran(f).$
(c):$n$ is odd: For any fixed $a_1<a_2<\cdots<a_n\in \mathbb{N}.$ Let $$P(x)-x=(x-a_1)(x-a_2)\cdots(x-a_n).$$Denote: $$f(x)=a_i, \forall ~~~x\in \left\{x\in \mathbb{R} | P(x)=a_i\right\},i=1,2,\cdots n.;$$$$f(x)=a_1, ~~~otherwise.$$
$n$ is even: For any fixed $a_1<a_2<\cdots<a_n\in \mathbb{N}.$ Let $$P(x)-x=(x-a_1)(x-a_2)\cdots(x-a_n)^2.$$Denote: $$f(x)=a_i, \forall ~~~x\in \left\{x\in \mathbb{R} | P(x)=a_i\right\},i=1,2,\cdots n. ;$$$$f(x)=a_1, ~~~otherwise,$$