MithsApprentice wrote:

Prove that any monic polynomial (a polynomial with leading coefficient 1) of degree $n$ with real coefficients is the average of two monic polynomials of degree $n$ with $n$ real roots.

Let's do some thorough analysis and motivation on this problem.

First, the statement of this problem is nice

Pretty straightforward if you know two general things about polynomial: the main problem is to $\textbf{construct}$ polynomials.
Now, if we were to find 2 polynomials of degree $n$ with $n$ real roots, the first thing that comes to mind is indeed, Intermediate Value Theorem. Why do we think of this?
Basically you wanted to construct a polynomial with $n$ real roots, but to do this you just need $n+1$ distinct points such that $f(a_i) < 0$ if $i \le n + 1$ is odd and $f(a_i) > 0$ if $i \le n + 1$ is even. Then, by Intermediate Value Theorem, there would be a root in the interval $(a_i , a_{i + 1})$ for every $1 \le i \le n$ , satisfying the hypothesis that we wanted.

Keeping that in mind, suppose that we have pick $a_i$ such numbers that $g$ passes through, by $\textbf{Lagrange Interpolation Theorem}$ , we are pretty much done, since there must exists polynomial of degree at most $n$ that pass these $n + 1$ points.
So, we are pretty much done since we can construct two polynomials $g$ and $h$ that has $n$ roots, and we can indeed choose $2f = g + h$ . Formalizing this, choose $g_1, g_2, \dots, g_{n + 1}$ being roots of $g$ , and $h_1, h_2, \dots, h_{n + 1}$ being roots of $h$ , such that
$g_i + h_i = 2f(x_i)$ for some $x_i$ and $|g_i|, |h_i| > M$ for a large value of $M > 100 \cdot | \max_{x_i, 1 \le i \le n } f(x_i) |^{100} + 200$ and $g_i$ switch signs depend on parity ( $h_i$ as well).

Now, there's just one problem left: the polynomial $g$ is not necessarily monic. But this is easy to fixed. Suppose we have pick $n$ points: $g_1, g_2, \dots, g_n$ . This could determine a polynomial of degree $n$ and we could somehow control $g_{n + 1}$ such that this is monic.

Now, if $g$ is monic, we could simply check the leading coefficient of $h = 2f - g$ , is monic as well. So we are done.