Indian National Mathematical Olympiad

Solution:
We have $f(p)=p$ for all $p \in \mathbb{R}[x]$, or $f(p)=-p$ for all $p \in \mathbb{R}[x]$. These clearly satisfy the given conditions.

Proof
Claim 1 For all $p \in \mathbb{R}[x], f(f(p))=p$.
Proof. Using condition 3 on the polynomials $p$ and $f(p)$, we see that $p-f(f(p))$ has the same set of real roots as $f(p)-f(p)=0$, which is $\mathbb{R}$. Therefore $p-f(f(p))$ is identically zero.

Note that this implies $f$ is bijective. In what follows, $p \sim q$ will mean that $p$ and $q$ have the same set of real roots. Note that putting $f(q)$ for $q$ in condition 2 gives $p-q \sim f(p)-f(q)$ for all $p, q$ (call this statement $(\star)$ ). In particular, putting $q=0$ here, $p \sim f(p)$ for all $p$ (call this $(\star\star)$).

Claim 2 For all non-zero $p \in \mathbb{R}[x]$, $\operatorname{deg} p-1 \leq \operatorname{deg} f(p) \leq \operatorname{deg} p+1$.
Proof. The right inequality is simply condition 2. Now using condition 2 on the polynomial $f(p)$, we see that $\operatorname{deg} f(f(p)) \leq \operatorname{deg} f(p)+1$ which gives $\operatorname{deg} f(p) \geq \operatorname{deg} p-1$ because of claim 1.

Claim 3 For all $p \in \mathbb{R}[x], \operatorname{deg} f(p)=\operatorname{deg} p$.
Proof. Note that nonzero constant polynomials have no root, so by $(\star\star)$, their image must have no root. This is impossible if that image has degree 1; so by condition 2, the image has degree 0, i.e., is a constant polynomial. First consider the case when $\operatorname{deg} p$ is even; assume for now the leading coefficient of $p$ is positive. That means $p(x) \rightarrow \infty$ for $x \rightarrow \pm \infty$, so it has a global minimum, say $C$. Then the polynomial $p+k$ ($k>C$) has no real roots. Using $(\star)$ on $p$ and the constant polynomial $-k$, we see that $f(p)-f(-k)$ has no roots. But this is impossible if $\operatorname{deg} f(p)$ is odd (since $f(-k)$ is a constant), so by claim 2, we must have $\operatorname{deg} f(p)=\operatorname{deg} p$. A similar argument holds if $p$ has negative leading coefficient.

Now if $\operatorname{deg} p$ is odd, then $\operatorname{deg} f(p)$ cannot be even, otherwise $q=f(p)$ would be an even degree polynomial whose image $f(q)=f(f(p))=p$ has odd degree, contradicting the last paragraph. Thus $\operatorname{deg} f(p)$ is odd, and using claim 2, we infer that $\operatorname{deg} f(p)=\operatorname{deg} p$.

We call a polynomial $p$ ninth-grade if all $\operatorname{deg} p$ roots of $p$ are real and distinct. Clearly for any ninth-grade $p$, $p$ and $f(p)$ have the roots and same degree, so $f(p)=c_{p} p$ for some non-zero $c_{p} \in \mathbb{R}$.

Claim 4 Given any non-constant $q \in \mathbb{R}[x]$, we can choose $r$ with degree bigger than $q$ so that both $r$ and $q-r$ are ninth-grade.
Proof. Assume that all real roots of $q$ are inside the interval $[a, b]$. Now choose a number $n$ which has the same parity as $\operatorname{deg} q$ and is bigger than $\operatorname{deg} q$, and choose numbers $c_{1}=a< c_{2}<\cdots<c_{n-1}<c_{n}=b$. Consider the polynomial $p=k\left(x-c_{1}\right)\left(x-c_{2}\right) \cdots\left(x-c_{n}\right)$, so that $k$ has the same sign as the leading coefficient of $q$ (value of $k$ will be chosen later). Clearly $p$ has alternating signs on the intervals $\left(-\infty, c_{1}\right),\left(c_{1}, c_{2}\right), \cdots,\left(c_{n-1}, c_{n}\right),\left(c_{n}, \infty\right)$, and has the same sign as $q$ outside $[a, b]$. Let $k_{1}, k_{2}, \cdots, k_{n-1}$ be the extrema of $p$ on the intervals $\left[c_{1}, c_{2}\right], \cdots\left[c_{n-1}, c_{n}\right]$ in that order, and suppose they are attained at $x_{1}, \cdots x_{n-1}$. Make $|k|$ large enough so that $\left|k_{i}\right|>\max _{x \in[a, b]}|q(x)|$ for all $i$. Then $p+q$ has degree $n$, and has alternating signs at $a-\epsilon, x_{1}, \cdots, x_{n}, b+\epsilon$ for $\epsilon>0$, so it has exactly $n$ distinct roots. Now it is enough to take $r=-p$.

Claim 5 For any $q \in \mathbb{R}[x], f(q)=c_{q} q$ for some non-zero real $c_{q}$.
Proof. We have already proved this for ninth-grade polynomials. Take ninth-grade $r$ so that $q-r$ is ninth grade and $n=\operatorname{deg}(q-r)>\operatorname{deg} q$. Then $q-r \sim f(q)-f(r)=f(q)-c_{r} r$. Since $q-r$ is ninth-grade and has the same degree as $f(q)-c_{r} r$, $q-r=c\left(f(q)-c_{r} r\right)=c f(q)-c_{1} r$ for non-zero reals $c, c_{1}$. Comparing the leading term (which belongs to $r$) on both sides, $c_{1}=1$, therefore $q=c f(q) \Longrightarrow f(q)=c_{q} q$.

Claim 6 For any $p, q \in \mathbb{R}[x], c_{p}=c_{q}$.
Proof. We note that for any two polynomials $p, q$ if $p-q$ has a real root which is not a root of $p$, then $c_{p}=c_{q}$. Indeed, if $s$ is a root of $p-q$ (meaning $p(s)=q(s) \neq 0$), then it's also a root of $f(p)-f(q)=c_{p} p-c_{q} q$, so that $c_{p} p(s)=c_{q} q(s) \Longrightarrow c_{p}=c_{q}$.

Now for any two $p, q$, choose odd $N$ such that $N>\max \{\operatorname{deg} p, \operatorname{deg} q\}$. Then the polynomial $r=x^{N}$ is such that $r-p$ and $r-q$ both have real roots, so $c_{q}=c_{r}=c_{p}$.

Claim 6 clearly means there is $c \in \mathbb{R}$ so that $f(p)=c p$ for all $p \in \mathbb{R}[x]$. Using the fact $f(f(p))=p$, we see that the only possibilities are $c=1$ or $c=-1$, completing the proof.