# Generalizing the hardest question on the practice math GRE

The most-missed question on the Math GRE is the following:

How many times does $x^{12}$ intersect $e^x$?

Because I told you it was hard, you probably realized it was a trick and got the right answer; or you were among the ~25% who got it right on the test.

I thought this was fun! My question is:

What is the maximum number of times that $e^x$ can intersect a polynomial of degree $n$?

-
@StefanSmith Eventually $e^x$ will overtake any polynomial, so you should get three intersections! –  Macavity Dec 22 '13 at 3:28
@Newb: Alpha shows solutions near $-0.93,1.10,45.92$ –  Ross Millikan Dec 22 '13 at 3:33
@Macavity : I fell for the trick. I will erase my comment in embarrassment. –  Stefan Smith Dec 22 '13 at 4:11

The answer to the GRE question is $3$. The graphs intersect once to the left of the $y$-axis, and twice to the right.

For the general question, here is one suggestion for a possible solution, and a sketch of the construction.

For any $n$ we can construct a polynomial that intersects $e^x$ $n+1$ times. For even $n$, place $n/2$+1 points with different $x$-values above the graph of $e^x$. Place $n/2$ points below the graph of $e^x$ such that their $x$-values alternate with those of the other points. There is then a unique polynomial of degree $n$ containing the $n+1$ points we've chosen. The intermediate value theorem then shows the two graphs intersect $n$ times within the region determined by the chosen points. The extra intersection comes beyond the region when $e^x$ overtakes the polynomial.

The case is similar for odd $n$, making sure the leading coefficient of the polynomial is positive.

To see this is maximal, apply the mean value theorem to the equation $p(x)-e^x=0$ where $p(x)$ is a polynomial of degree $n$. Differentiating $n+1$ times gives the equation $e^x=0$ which has no solutions. It follows that $p^{(n)}(x)-e^x=0$ has at most $1$ solution, $p^{(n-1)}(x)-e^x=0$ has at most $2$ solutions, etc. Thus $p(x)-e^x=0$ has at most $n+1$ solutions.

-

You can always get $n+1$ intersections from a polynomial of degree $n$. Just pick $n+1$ points on $e^x$ and interpolate. As the GRE question hints, if the leading coefficient is positive, the polynomial crosses from below to above $e^x$ at the highest interpolating point, and $e^x$ will exceed the polynomial one more time. This gives $n+2$ by taking $n$ points below $0$ and one point above zero, say $4$. There are no more going toward $-\infty$-you are already on the right side of $e^x$. The question is whether you can exploit the bend in $e^x$ to make $2,4,\dots$ more intersections by choosing the points correctly.

-