Problem 1420

Without loss of generality, we can assume that $P_1, \dots, P_n$ are pairwise distinct. We will first show that $|S_y| = n$ for any $y \in \mathbb{R}$ and $\deg P_i$ is odd for any $i \in [n]$. To see this, let $a$ be the number of polynomials with odd degrees, and $b$ be the number of those with even degrees. Since $Y := \{P_i(x) \mid x \in \mathbb{R} \text{ such that } P_i(x) = P_j(x) \text{ for some } j \neq i\}$ is finite, we can choose some $M > 0$ such that all elements in $Y$ have absolute value less than $M$. We can further enlarge this $M$ so that for any $y > M$ and $i = 1, \dots, n$, we have
$$|\{x \in \mathbb{R} | P_i(x) = y\}| = \begin{cases} 1, & \text{if } 2 \nmid \deg P_i(x); \\ 2, & \text{if } 2 \mid \deg P_i(x), \end{cases}$$
and for any $y < -M$ and $i = 1, \dots, n$, we have
$$|\{x \in \mathbb{R} | P_i(x) = y\}| = \begin{cases} 1, & \text{if } 2 \nmid \deg P_i(x); \\ 0, & \text{if } 2 \mid \deg P_i(x). \end{cases}$$
With this choice of $M$, we have that $|S_y| = a + 2b$ for any $y > M$, and that $|S_y| = a$ for any $y < -M$. This shows that $b = 0$, $a = n$ and $|S_y| = n$ for any $y \in \mathbb{R}$.

Now since the degrees of the polynomials are odd, we know that for any $y \in \mathbb{R}$ and for any $i \in [n]$ there exists at least one $x$ such that $P_i(x) = y$. Therefore for any $y \notin Y$ and any $i \in [n]$ we know that there is exactly one $x$ that satisfies $P_i(x) = y$. As a consequence, we know that for any $i \in [n]$ the polynomial $P_i$ has to be strictly increasing except at finitely many points. Since $P_i$ is a polynomial, this shows that $P_i$ is strictly increasing everywhere. This forces $Y$ to be empty as otherwise for any $y \in Y$ we would have $|S_y| \le n - 1$. Now if $\deg P_i \ne \deg P_j$, it is clear that $P_i - P_j$ still has odd degree. Therefore there is a real root $x$ of $P_i - P_j$, and so $Y$ is nonempty, which is a contradiction. Therefore all the degrees have to be the same, as desired.