37th Iranian Mathematical Olympiad

Only $n=2$ and $n=3$ are interesting.

Note that if $n$ is not interesting, then any integer greater than $n$ is not interesting as well. So we just need to prove that $n=4$ is not interesting.

We claim that there is no such example for the case $$P_2(x)>P_4(x)>P_1(x)>P_3(x)$$ for infinitesimal positive number $x$.

For the sake of contradiction, assume that there exists an example. Since $P_i(x)-P_1(x)$ also satisfies the inequality, assume that $P_1(x)=0$. Then by contradiction, every $P_i(x)$ has constant term zero.

Now, $P_3(x)$ is always negative for values close to $0$. Therefore, the term with the minimal degree in $P_3(x)$ is of the form $-a{x}^{2b}$, for some positive real number $a$ and positive integer $b$. Analogously, for $P_2(x),P_4(x)$, the terms of the minimal degrees are of the form $a{x}^{2b-1}$, for some positive real number $a$ and positive integer $b$. Let $$\begin{array}{rl}{P}_2(x)& =a_2{x}^{2b_2-1}+\dots \\ P_3(x)& =-a_3{x}^{2b_3}+\dots \\ P_4(x)& =a_4{x}^{2b_4-1}+\dots \end{array}$$ where every $a_i$ is a positive real number and every $b_j$ is a positive integer. Since $P_2(x)>P_3(x)>P_4(x)$ for $x<0$, therefore $$2b_2-1>2b_3>2b_4-1⟹b_2>b_3>b_4⟹P_2(x)<P_4(x),$$ for all sufficiently small positive real numbers $x$, contradicting the assumption $P_2(x)>P_4(x)>0>P_3(x)$.

But we claimed that $n=2,3$ are interesting. The case $n=2$ is trivial and for $n=3$, we have $$P_i(x)=x{Q}_i(x)+c.$$ If $\sigma (i)=i$, we need to find polynomials $Q_i$ such that $Q_1(x)<Q_2(x)<Q_3(x)$ for $x\in (-ϵ,0)$ and $Q_1(x)>Q_2(x)>Q_3(x)$ for $x\in (0,ϵ)$. It's clear that linear polynomials will work.

If $\sigma (1)=1,\sigma (2)=3$ and $\sigma (3)=2$, let $Q_1(x)=0$ and $Q_2(x),Q_3(x)$ be linear polynomials passing through point $0$ with negative leading coefficient. Other permutations are the same and we're done. ■