What is the maximum number of points at which an $n$-degree polynomial can intersect the power function $x^m, m>n$, $x\in \Bbb R$. 
What is the maximum number $\phi(n,m)$ of real roots of the function $f(x)-p(x)$, where $f(x)=x^m$ and $p(x)$ is an $n$-degree polynomial ($m,n\in \Bbb N_0, m\geq n+1$)?

 A: Since $f-p$ is an $m$-degree polynomial, it has no more than $m$ real roots, so
$$
  \phi(m,n) \leq m.
$$
When $m=n+1$ this limit is attained. Indeed, we can readily observe that $\phi(n,n+1) = n+1$ for example by considering
$$
  p(x) = x^{n+1} - \Pi_{k=1}^{n+1} (x-k).
$$

It is also easy to see that (by considering monotonicity on $(-\infty,0]$ and $[0,\infty)$ separately)
$$
\phi(m,0) = \begin{cases}
1, & m \ \text{ odd}, \\
2, & m \ \text{ even}.
\end{cases}
$$
and that (by considering convexity / concavity on $(-\infty,0]$ and $[0,\infty)$ separately)
$$
\phi(m,1) = \begin{cases}
3, & m \ \text{ odd}, \\
2, & m \ \text{ even}.
\end{cases}
$$


What can be said about $\phi(n,m)$ for $n\geq 2$ and $m\geq n+2$?

Here comes in use the following result on the number of roots of functions that are "$k$-order convex", i.e. their $k$-order derivative is positive:

Lemma 1. If $f^{(k)}\geq 0$ then the set of roots of $f$ either consists of at most of $k$ isolated points, or it is a (non-degenerate) closed interval.


*

*If $m-n-1$ is even then $f^{(n+1)}\geq 0$ (and $>$ whenever $x\neq 0$) and $p^{(n+1)}\equiv 0$. We thus by Lemma 1 conclude that $f-p$ has no more than $n+1$ roots, and this estimate is tight as we can find a polynomial $p$ interpolating any $n+1$ points of $f$.


*If $m-n-2$ is even then $f^{(n+2)}\geq 0$ (and $>$ whenever $x\neq 0$) and $p^{(n+2)}\equiv 0$. We thus by Lemma 1 conclude that $f-p$ has no more than $n+2$ roots. That this bound is tight can be shown by @JyrkiLahtonen's argument applied to $f(x)=x^m$ instead of $f(x)=e^{x^2}$. Specifically, put
$$
p(x)=\begin{cases}
A\prod_{i=1}^l(x^2-i^2) & n=2l, \\
Ax\prod_{i=1}^l(x^2-i^2) & n=2l+1, \\
\end{cases}
$$
and considering $A>0$ large enough it can be achieved that $f-p$ has $n$ roots near the roots $\pm 1, \pm 2, \ldots, \pm l$ (and $0$ for $n$ odd) of the polynomial $p$; specifically we want to choose $A$ large enough to guarantee that the roots of $f-p$ are strictly less than $\tfrac 1 2$ away from the corresponding roots of $p$. What is more, if $A>(l+1)^m$, then besides that $f(x)-p(x)\to \infty$ as $x\to \infty$ we also have that $f(l+1)-p(l+1)<0$. By intermediate value theorem it then follows that $f-p$ has another root  at some $x>l+1$, and analogically it also has a root at some $x<-(l+1)$. In summary, $f-p$ has $n+2$ roots.


Conclusion.
$$
\phi(m,n) = \begin{cases}
n+1, & m-n \ \text{ odd}, \\
n+2, & m-n \ \text{ even}.
\end{cases}
$$

