Projectile polynomials

This post is based on the following game: Super Mario Quadratics.

I will start with an explanation of projectile motion and ramp up to interpolation.

Mathematics - Physics - Polynomials - Data Science

Projectile polynomials

January 17, 2023

A brief overview of projectile motion:

Assumptions: the body is launched inside Earth's gravitational field, there is no air resistance, disregard curvature of the Earth. Up is positive, down is negative (necessary for velocities).

Start: Shoot the object into the air at an angle $\theta$ with initial speed $u$. Gravity acts on the body perpendicularly to the surface of the Earth so our object will be affected in the vertical $y$ direction. Let the vertical velocity at time $t$ be $v_{y}^{(t)}$ and let the horizontal velocity be $v_{x}^{(t)}$.

Notice that since nothing exerts force on the body in the $x$ direction the horizontal velocity stays the same so $v_{x}^{(t)} = v_{x}^{(0)}$ for all $t$.

The vertical velocity is trickier since we have to account for the deacceleration $g=9.81 m/s^2$ in the vertical direction, thus the vertical velocity at time $t$ is $v_{y}^{(t)} = v_{y}^{(0)}\cdot t - g\cdot t$.
The displacement in the $x$ direction is just equal to $s_{x}^{(t)} = v_{x}^{(t)} \cdot t$ since this is motion without acceleration. We know that $v_{x}^{t} = v_{x}^{0} = u \cos(\theta)$ so $s_x^{(t)} = u \cdot t\cos(\theta)$. Denote $x_t=s_x^{(t)}$ and $y_t=s_y^{(t)}$


Velocities in the $x$ and $y$ directions


The $y$ displacement is $s_{y}^{(t)} = v_{y}^{(0)} \cdot t - \frac{g\cdot t^2}{2}$ or $y_t = u \sin(\theta)t - \frac{g\cdot t^2}{2}$.

Now to figure out the equation of the trajectory with $x$ input and $y$ output we need to get $y_t$ in terms of $x_t$. After rearranging equations and boring algebra we get the following:
\[ y = \left (-\frac{g}{2u^2\cos(\theta)} \right )x^2 + (\tan(\theta))x = (\ldots)x^2+(\ldots)x \]
The above "$\ldots$" represent constants. I also omitted $t$ in the index of $x,y$.

Thinking about projectile motion through two different lenses: the $x$-axis and they $y$-axis gives us the following crucial insight:

$\star$ Projectile motion is a combination of a vertical shot and a horizontal uniform straight line movement. $\star$

The chimp and the hunter

The chimp will not survive 😔. In the $y$ direction the bullet is in free fall, just like the chimp, and they start falling at the same time from the same height.

A free fall/vertical shot can be thought of as an infinitely narrow parabola or whenever an object is flying through the air it keeps this parabolic shape (without air resistance).
In conclusion, in our gravitational field here relatively close to the Earth's surface, every falling object traces a parabola.

Back to Mario

Now that we know that every trajectory traces a parabola, we are ready to tackle the Mario game. Could you make an impossible level in this game? Could you place the coins in such a way that no Mario's jump can catch them all?
If you're given some coins, how can you determine the jump without trial and error?

Mathematically said, given $n$ points, does there exist a parabola that fits through all $n$ of these points? It should be obvious that the answer is no for general $n$. Place three collinear points parallel to the ground and you can't fit any (non-degenerate) parabola. Or even easier, place two vertical points. By definition of a function they can't both lie on the graph.

The actual probability of making a possible level with three or more coins is $0$.
But it is obviously (sometimes) possible. Just work backwards from the parabola itself and mark however many points you want.
The problem of finding a graph to fit a set of points is called an interpolation problem. Interpolating means finding a function that fits the given data points. There are many techniques of interpolation, but I'll stick with Lagrange interpolation because it is one of the most fundamental ones and somewhat useful for math olympiads.

$\star$ The Lagrange interpolating polynomial is the unique polynomial of lowest degree that interpolates a given set of data. Given a data set of coordinate pairs $(x_i,y_i)$ with $0 \leq i \leq k$, the Lagrange polynomial $L(x)$ has degree $\leq k$ and assumes each value at the corresponding input $L(x_i) = y_i$. $\star$

Note that fitting polynomials is the same as solving a system of $n$ equations with $n$ variables. If we have $n$ points to fit to a polynomial of degree $n$ there are infinitely many such polynomials. If we have $n+1$ points, then there exists exactly one polynomial of degree $n$ (or none if we don't take the sensible restriction that $x_i$ are distinct). Obviously, the Lagrange polynomial can have degree less than $n$ if the given points lie on a curve of smaller degree.

Polynomial tracing points of a function.

It turns out that this polynomial is relatively easy to find.
For simplicity I'll find it for $n=3$. We want to find the parabola that goes through the points $(x_0,y_0),(x_1,y_1),(x_2,y_2)$.
The simplest way to achieve such a quadratic is if it looked something like this:
\[ p(x) = y_0 \cdot A + y_1 \cdot B + y_2 \cdot C \]
where we can make the letters turn into zero when needed. Obviously $A,B,C$ shouldn't be constants. Let them be polynomials and at least one should have degree $2$. We need $A(x_0) = 1$ and $A(x_1)=A(x_2)=0$. How can we achieve this? Simply take $A(x) = \alpha (x-x_1)(x-x_2)$ but we also need $A(x_0)=1$ so $\alpha = \frac{1}{(x_0-x_1)(x_0-x_2)}$. Hence the first term is $y_0 \cdot \frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}$. Repeating for the remaining $B,C$ we find the general cubic to be:
\[ p(x) = y_0 \cdot \frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}+ y_1 \cdot \frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)} + y_2 \cdot \frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_0)} \ (\bigstar)\]

Here's an example of a fitted parabola to three points (thanks to the SciPy library we have an inbuilt function):

The general polynomial for $n$ points is analogous:
\[ p(x) = \sum_{i=0}^{n} \left ( y_i \frac{(x-x_0) \cdots (x-x_{i-1}) (x-x_{i+1}) \cdots (x-x_n)}{(x_i-x_0) \cdots (x_i-x_{i-1}) (x_i - x_{i+1}) \cdots (x_i - x_n)} \right )\]
Note the missing $x_i$ in the numerator and denominator. Also make sure that this polynomial is of degree $n$ indeed and that we are fitting $n+1$ points starting from index $0$.

In conclusion, for any given $n+1$ points we can find a polynomial of degree $n$ that passes through all of those points (assuming $x_i \neq x_j$). Another kind of interpolation is the Newton Interpolation. This kind of polynomial can be very useful in general and even serve as a relatively naive technique in data science where predicting outputs given inputs is crucial.

For example, it is often better than Linear Interpolation and Nearest Neighbors Interpolation since it avoids any jaggedness by its polynomial nature. It does have its problems though. It is usually not useful for large sets of data points since it usually sky-rockets into space at the edges of the interval. This is called the Runge's phenomenon:



Notice the great spikes at around $x=2$ and $x=13$ (one goes beyond the screen). That's typically not what we want. A famous example is interpolating the function $f(x) = \frac 1{1+25x^2}$ at points $x_i = \frac{2i}{n}-1$:



To avoid this in we could use cubic splines which mimic a smooth polynomial passing through our points. You sort your datapoints by their $x$ values and go left to right and fit each two consecutive points with a (typically) cubic curve. We use cubics because we need to be able to have the same slopes (derivatives) at the ends of the intervals in order for the transition to be smooth. You can check that parabolas wouldn't suffice there. So at the end we have smooth connections between points:



Now notice the smoothness of the transitions. This is thanks to the equal derivatives. We have basically made a graph out of $n$ different smaller cubics. Read more about what the algorithm for constructing these cubics looks like here. Cute!

Coming back to our Mario game, it's now trivial to solve every level by simply reading off the coordinates of three distinct coins and putting them into $(\bigstar)$. If the level is possible, not more than three coins are needed because they uniquely determine our parabola/jump. The game does get less precise as you go through the levels and just eyeballing works out but where's the fun in that?
\[ \]

Practice problems


Introductory

Problem 1
Given a polynomial $P(x)$ with degree $n$. For each $k\in$ { $0,1,2,...,n$ }, $P(k)=2^k$. Find $P(n+1)$.
Problem 2
Let \(n \geq 2\) be an integer and take a polynomial \(p(x) = a_0 + a_1x + \dots + a_{n - 1}x^{n - 1}\). Prove that, for any \(x_1, \dots, x_n\) distinct real numbers, \[\sum_{i = 1}^n \frac{p(x_i)}{\prod_{j = 1, j \neq i}^n (x_j - x_i)} = a_{n - 1}.\]

Intermediate

Problem 1
Let $ p$ be a prime number and $ f$ an integer polynomial of degree $ d$ such that $ f(0) = 0,f(1) = 1$ and $ f(n)$ is congruent to $ 0$ or $ 1$ modulo $ p$ for every integer $ n$. Prove that $ d\geq p - 1$.
Problem 2
You are given $N$ such that $ n \ge 3$. We call a set of $N$ points on a plane acceptable if their abscissae are unique, and each of the points is coloured either red or blue. Let's say that a polynomial $P(x)$ divides a set of acceptable points either if there are no red dots above the graph of $P(x)$, and below, there are no blue dots, or if there are no blue dots above the graph of $P(x)$ and there are no red dots below. Keep in mind, dots of both colors can be present on the graph of $P(x)$ itself. For what least value of k is an arbitrary set of $N$ points divisible by a polynomial of degree $k$?

Advanced

Problem 1
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.
Problem 2
Given is a monic polynomial $f$ of degree $n$ with real coefficients and integers $x_0 < x_1 < \ldots < x_n$. Prove that there exist some positive integer $k$, such that $|f(x_k)| \geq \frac {n!}{2^n}$
Problem 3
Let $x_1, x_2, \dots, x_n$ be different real numbers. Prove that \[\sum_{1 \leqslant i \leqslant n} \prod_{j \neq i} \frac{1-x_{i} x_{j}}{x_{i}-x_{j}}=\left\{\begin{array}{ll} 0, & \text { if } n \text { is even; } \\ 1, & \text { if } n \text { is odd. } \end{array}\right.\]