11.4. Given a natural number $N \geqslant 3$. We call a set of $N$ points on the coordinate plane admissible if their abscissas are distinct, and each of these points is colored either red or blue. We will say that a polynomial $P(x)$ separates an admissible set of points if either there are no red points above the graph of $P(x)$ and no blue points below, or vice versa (points of both colors may lie on the graph itself). For what smallest $k$ can any admissible set of $N$ points be separated by a polynomial of degree no more than $k$?

(K. Tyschuk)
Answer. $k=N-2$.

Solution. We will prove that $k=N-2$ works. Take any $N-1$ of the given $N$ points; there exists a polynomial of degree not greater than $N-2$ whose graph passes through them. This polynomial, obviously, separates our points.

It remains to construct an example of an admissible set that cannot be separated by a polynomial of degree less than $N-2$. Take the graph of some reduced polynomial $f(x)$ of degree $N-2$ and place $N$ points on it, alternating colors. Suppose that some polynomial $P(x)$, whose degree is not more than $N-3$, separates these points; we can assume that there are no red points below the graph of $P(x)$, and no blue points above it.

Denote $Q(x)=f(x)-P(x)$; the degree of the polynomial $Q(x)$ is $N-2 \geqslant 1$. Moreover, if $r$ and $b$ are the abscissas of any red and blue points, respectively, then $P(r) \leqslant f(r)$ and $P(b) \geqslant f(b)$, which means $Q(r) \geqslant 0$ and $Q(b) \leqslant 0$.

Notice that if $Q(s) \leqslant Q(t)$ for some $s < t$, then there exists a point $x \in (s, t)$ such that $Q'(x) > 0$ (here we use the fact that $Q(x)$ is non-constant). This means that on any interval between a red and a blue point (the red one being to the left of the blue one), there is a point where the value of $Q'(x)$ is positive. Similarly, on any interval between a blue and a red point, there is a point where the value of $Q'(x)$ is negative. Thus, we have found $N-1$ points where $Q'(x)$ takes values of alternating signs. Between any such neighboring points, $Q'(x)$ has a root. Therefore, the polynomial $Q'(x)$ has at least $N-2$ roots. But this is impossible, since $Q'(x)$ is a polynomial of degree $N-3$. Contradiction.

Remark. By slightly modifying the reasoning, we can show that $f(x)$ can be any function whose $(N-2)$-th derivative has no roots; for example, $f(x)=2^x$ will work. Indeed, from the fact that $Q'(x)$ has at least $N-2$ roots, it follows that the $(N-2)$-th derivative of the function $Q(x)$ has at least one root; but $Q^{(N-2)}(x)=f^{(N-2)}(x)-P^{(N-2)}(x)=f^{(N-2)}(x)$. Contradiction.