Problem: 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.

Solution: First,
\begin{lemma*}
  If $p$ is a monic polynomial of degree $n$,
  and $p(1)p(2) < 0$, $p(2)p(3) < 0$, \dots, $p(n-1)p(n) < 0$
  then $p$ has $n$ real roots.
\end{lemma*}
\begin{proof}
  The intermediate value theorem already guarantees
  the existence of $n-1$ real roots.

  The last root is obtained by considering cases on $n \pmod 2$.
  \begin{itemize}
  \ii If $n$ is even, then $p(1)$ and $p(n)$ have opposite sign,
  while we must have either
  \[ \lim_{x \to -\infty} p(x) = \lim_{x \to \infty} p(x) = \pm \infty \]
  so we get one more root.
  \ii The $n$ odd case is similar,
  with $p(1)$ and $p(n)$ now having the same sign,
  but $\lim_{x \to -\infty} p(x) = -\lim_{x \to \infty} p(x)$ instead. \qedhere
 \end{itemize}
\end{proof}

Let $f(n)$ be the monic polynomial and let
$M > 1000\max_{t=1, \dots, n} |f(t)|+1000$.
Then we may select reals $a_1, \dots, a_n$ and $b_1, \dots, b_n$
such that for each $k = 1, \dots, n$, we have
\begin{align*}
  a_k + b_k &= 2f(k) \\
  (-1)^k a_k & > M \\
  (-1)^{k+1} b_k & > M.
\end{align*}
We may interpolate monic polynomials $g$ and $h$ through the $a_k$ and $b_k$
(if the $a_k$, $b_k$ are selected ``generically'' from each other).
Then one can easily check $f = \tfrac12(g+h)$ works.