Iranian Mathematical Olympiad

a) We set an example using induction on $n$. For $n=1$, consider the following pair of polynomials of degree 2
$$h_1(x) = x^2 + x, \ h_2(x) = -x^2.$$
Now for any function $f: \mathbb{R} \to \mathbb{R}$, if $P_1(x)=h_1(f(x))$ and $P_2(x)=h_2(f(x))$ are polynomials, then $P_1(x) + P_2(x) = f(x)$ is a polynomial.

Now assume that $(h_1, h_2, \dots, h_{n+1})$ is a good $(n+1)$-tuple of $n$-variable polynomials. Define the following $(n+2)$-tuple $(g_1, g_2, \dots, g_{n+2})$ of polynomials with $n+1$ variables as
$$\begin{cases} g_i(x_1, x_2, \dots, x_{n+1}) = h_i(x_1, x_2, \dots, x_n), & 1 \le i \le n+1, \\ g_{n+2}(x_1, x_2, \dots, x_{n+1}) = x_1^2 + x_{n+1}, & i = n+2. \end{cases}$$
Now let $f_1, f_2, \dots, f_{n+1} : \mathbb{R} \to \mathbb{R}$ be some functions such that for all $1 \le i \le n+2$
$$P_i(x_1, \dots, x_{n+1}) = g_i(f_1, f_2, \dots, f_{n+1}),$$
is a polynomial. By induction hypothesis we obtain that $f_1(x), f_2(x), \dots, f_n(x)$ are polynomials. Note that $f_1(x)^2$ is a polynomial.
Therefore, $f_{n+1} = P_{n+2} - f_1^2$ is also a polynomial.
The degree of all $g_i$'s are more than 1. Therefore the given example is a good $(n+2)$-tuple.

b) According to the Fundamental Theorem of Symmetric Polynomials, for any symmetric polynomial $h_i(x_1, \dots, x_n)$ there exists another polynomial $g_i(x_1, \dots, x_n)$ such that
$$h_i(x_1, \dots, x_n) = g_i \left( \sum_{sym} x_i, \sum_{sym} x_i x_j, \dots, x_1 x_2 \cdots x_n \right).$$
Now assume that for some $n > 1$ there exists a good $(n + 1)$-tuple of symmetric polynomials. Consider the following functions
$$f_1(x) = |x|, \ f_2(x) = -|x|, \ f_3(x) = f_4(x) = \dots = f_{n+1}(x) = 0.$$
Note that
$$\left\{ \begin{array}{l} \sum_{sym} f_i f_j = -x^2, \\ \\ \sum_{sym} f_{i_1} f_{i_2} \cdots f_{i_k} = 0, \quad \forall k \neq 2. \end{array} \right.$$
Therefore,
$$P_i(x) = h_i(f_1(x), \dots, f_n(x)) = g_i(0, -x^2, 0, \dots, 0) = H_i(-x^2).$$
Where $H_i$ is a polynomial with real coefficients. So for any $i$, $P_i(x)$ is a polynomial, and therefore all $f_i$'s are polynomials, too. But $f_1$ and $f_2$ are not polynomials. Contradiction, hence the claim. ■