Polynomial divides set of points Given a set of points in the plane with distinct $x$-coordinates, each point colored black or white. A polynomial $P(x)$ "divides" the set of points if no black point lies above $P(x)$ and no white point lies below $P(x)$, or vice versa. Points of any color can lie on $P(x)$.
What is the least $k$ such that any valid set of $n$ points can be divided by a polynomial of degree at most $k$? We can do $k=n-2$ by having a polynomial pass through any $n-1$ points, thus trivially satisfying the condition of dividing the points. 
 A: For all $n$, there is a way to choose the points & colors that forces $ P $ to have degree at least $ n-2 $ .
Assume $ n \geq 3 $ (the smaller cases are easy).
Choose the points $ \{(i,0) | 1 \leq i \leq n-2\} \cup \{(n-1,1),(n,n^2)\}$.  Color them alternating white and black in order of their $ x $-coordinates.
For any $ 1 \leq i \leq n-3 $, we have that either $ P(i) \geq 0$ and $ P(i+1) \leq 0 $ or vice versa.  Since $ P $ is non-zero somewhere between $ i $ and $ i + 1 $ ($ P $ can't be the $ 0 $ polynomial - that doesn't divide the points), $ P $ has a root somewhere in $ [i,i+1]$.  It is possible for two of these roots to be the same, but it's not hard to see that this must either be double root, or there will be additional roots in one of the two intervals.  This gives a root of $P$ for each $ i $, totaling $ n - 3 $ roots.
Assume that $ P $ has degree $ k = n-3 $.  Then $ P $ can't have more roots than we've already found.  Let $ x_1, x_2 ... x_{n-3} $ be these roots.
Since the two last points are both above the $x$-axis, and one of those points is a lower bound, $ P $ must stay above the $x$-axis after its last root.
Now we consider the two cases, when the final point is a lower bound or an upper bound.
Case 1: The final point is an upper bound.
The point at $(n-2,0)$ is also an upper bound.  $ P $ is, after its last root, on the "wrong" side of the $x$-axis for this point.  Its last root is at most $ n-2 $, so it must pass through the point $(n-2,0)$.
Then it will be on the wrong side of the $x$-axis for the previous point, and the previous root is at most $ n-3 $, so $ P $ must pass through the point $(n-3,0)$.
This continues through all the points, and $ P $ must pass through the 2nd point, only to be on the wrong side of the $x$-axis for the first point.  But then $ P $ already has $n-3$ roots, so it can't cross the $x$-axis again to get to the correct side for the 1st point.  Thus, we have a contradiction.
Case 2: The final point is a lower bound.
Since we know all the roots of $ P $, we can write it as $ P(x) = a \displaystyle\prod_{i=1}^{n-3} (x-x_i)$.
Now, we can give an upper bound for $
\dfrac{P(n)}{P(n-1)}\\
= \dfrac{\displaystyle\prod_{i=1}^{n-3} (n-x_i)}{\displaystyle\prod_{i=1}^{n-3} (n-1-x_i)} \\
\leq \dfrac{\displaystyle\prod_{i=1}^{n-3} (n-i)}{\displaystyle\prod_{i=1}^{n-3} (n-1-(i+1))} \\
= \dfrac{\displaystyle\prod_{i=1}^{n-3} (n-i)}{\displaystyle\prod_{i=1}^{n-3} (n-2-i)} \\
= \dfrac{\displaystyle\prod_{i=3}^{n-1} i}{\displaystyle\prod_{i=1}^{n-3}i}\\
= \dfrac{(n-1)!/2}{(n-3)!}\\
= \dfrac{(n-1)(n-2)}{2}\\
< n^2
$
But since the last point, $(n,n^2)$ is a lower bound, and the 2nd last point, $(n-1, 1)$ is an upper bound, we have $ P(n) \geq n^2 $ and $ P(n-1) \leq 1 $, so $ \dfrac{P(n)}{P(n-1)} \geq n^2 $, and we've reached a contradiction.
