The answer is $k=N-2$. For any $N$ acceptable points, we can construct a polynomial $P(x)$ of degree $N-2$, which graph passes through $N-1$ of them. Then for any coloring of the points, $P(x)$ divides them. It remains to prove a polynomial of degree $N-3$ can not divide any $N$ acceptable points. Assume on the contrary the least value of $k$ is $N-3$. Let's take a set of points: $A_{i}=(i, y_i)\,,\, i=1,2,\dots,N$. We can choose $y_i,i=1,\dots, N$ such that any polynomial of degree $m\,,\,m=0,1,\dots,N-1$ passes through at most $m+1$ points among the given ones. Note that if $P(x)$ divides $\{A_1,A_2,\dots A_N\}$ we can modify slightly $P$ to a polynomial $P'$ of the same degree such that $P'$ also divides $(A_i)$ but there are no points $A_i$ on the graph of $P'$. Indeed, assume $\deg P=m$. Then $P$ passes through at most $m+1$ among the given points. These $m+1$ points change their color at most $m$ times. For some appropriate $x_i, i=1,2,\dots,m$ we can construct a polynomial $\Delta P(x)=\pm (x-x_1)(x-x_2)\dots (x-x_m)$ which changes its sign at the same points. Then for appropriate small $a$, the polynomial $P'(x)=P(x)+a\cdot \Delta P(x)$ also divides $(A_i)$ but does not pass through any of them. Now, lets color $A_1,A_2,\dots,A_N$ alternatively red,blue, red,blue,... According the assumption there exists a polynomial $P_1(x)$ of degree $k=N-3$, which divides $(A_i)$. We can assume no point $A_i$ lies on the graph of $P_1$. Let's color again the points $A_1,A_2,\dots,A_N$, but now red,red,blue,red,blue,... Again, there exists $P_2$ with degree $N-3$ dividing $(A_i)$. Note that $P_1$ and $P_2$ have different signs at the points $2,3,\dots,N$. It means $P_1(x)-P_2(x)$ has at least $N-2$ zeroes somewhere in the intervals $(2,3),(3,4),\dots,(N-1,N)$. That's $P_1(x)-P_2(x)\equiv 0$ , a contradiction.

Solved with: Kevin Wu, Isaac Zhu, Chris Qiu, Reyna Li, Ryan Yang, Elliot Liu, Alex Zhao, and Eric Shen

Eyed wrote: Solved with: Kevin Wu, Isaac Zhu, Chris Qiu, Reyna Li, Ryan Yang, Elliot Liu, Alex Zhao, and Eric Shen This is what happens when Eric Shen isn't here to do our writeups.

The answer is $\boxed{N-2}$. Construction is to just consider a polynomial with $\deg \le N-2$ passing through $N-1$ of the points (which exists because of Lagrange Interpolation). Now we prove the converse direction. Take the points to be the following: [asy][asy] size(200); draw((-4,0)--(7,0)); dot((-2,1)^^(-1,-1),magenta); dot((0,0)^^(2,0)^^(4,0),cyan); dot((1,0)^^(3,0)^^(5,0),magenta); label("$\cdots$",(6,0.5)); label("x-axes",(-3,-0.5)); [/asy][/asy] Note that if $P$ divides the above points, then it will satisfy the following: $P$ is non-constant. Some reals $a_1 < a_2 < \cdots < a_{N-1}$ satisfy $P(a_i) \cdot P(a_{i+1}) \le 0 ~ \forall ~ i = 1,2,\ldots,N-2$. We will show $\deg P \ge N-2$. Note that each interval $[a_i,a_{i+1}]$ contains a root of $P$. Now call a $a_i$ good if it is a root of $P$ and bad otherwise. If there are are $\le 1$ bad numbers, we are done. Otherwise, let $S = \{i : a_i \text{ is bad } \} = \{b_1,b_2,\ldots,b_t \}$ with $t \ge 2$. Note that the interval $[a_{b_i},a_{b_{i+1}}]$ must contain at least $b_{i+1} - b_i$ roots of $P$ with multiplicity (as it contains $b_{i+1} - b_i + 1$ good numbers, and another root must be there because of the inequality condition on $P$). This implies $P$ has at least $N-2$ roots, and since $P$ is non-constant, so we are done. $\blacksquare$

By Legrange Interpolation, it isn't difficult to see that $\text{deg} ~ P = N-2$ always works, because there will exist a polynomial passing through $N-1$ points this is a valid dividing polynomial, regardless of the color and location of the final point. Now we show that if $\text{deg} ~ P \leq N-3$, a dividing polynomial $P$ doesn't necessarily exist. Consider $N$ points named $\alpha_i, 1 \leq i \leq N$ on the $x$-axis alternately colored red and blue, and shift the rightmost two points slightly above the $x-$axis, keeping their $x-$coordinate the same. Suppose $P$ is a dividing polynomial. We will show that $\text{deg} ~ P > N-3$. Observe that $P$ must intersect the $x$-axis at every interval $[\alpha_i, \alpha_{i+1}]$. If $P$ passes through $\alpha_i$ and $\alpha_{i+2}$, and doesn't intersect any point in between, we say that $P$ jumps from $\alpha_i$. Let $k$ be an index such that $P$ jumps from $\alpha_k$. WLOG assume that $\alpha_k$ is blue. Then by the condition of the problem, all red points must lie above (or on) the graph of $P$, as $\alpha_{k+1}$ is red and lies above $P$. Additionally, $P$ must intersect the $x$-axis at the interval $(\alpha_{k+2}, \alpha_{k+3}]$. Now we perform a shift i.e. instead of intersecting the $x$-axis at $\alpha_{k+2}$, we change the graph of $P$ such that it intersects the $x$-axis at some point in $(\alpha_{k+1}, \alpha_{k+2})$ (of course, such a polynomial must exist by just changing the root from $\alpha_{k+2}$ to $\alpha_{k+2} - \epsilon$ for a sufficiently small $\epsilon$). Observe that this does not cause any problems, as the only change was that $\alpha_{k+2}$ moved from being on the graph of $P$ to being below the graph of $P$, while $\alpha_{k+1}$ is above the graph, and since they are of different colors, this causes no problems. Thus, we may conclude that a dividing polynomial without any jumps exists. Consequently, $P$ intersects the $x$-axis at every interval $[\alpha_i, \alpha_{i+1})$, for all $1 \leq i \leq N-2$ From this, we easily see that $P$ must have a degree of at least $N-2$, as desired.

oops The answer is $k=N-2$. For any set of $N$ acceptable points, interpolate any $N-1$ of them with a polynomial of degree (at most) $N-2$, which clearly works. It remains to show that $k=N-3 $ doesn't work. To do this, we will first need the following key lemma. Lemma: If a polynomial $P$ of degree (at most) $k$ divides an acceptable set of at least $k+2$ points, then that set is divisible by a polynomial of degree (at most) $k$ which passes through at least $k+1$ of its points. Proof: We take $P$ and slightly perturb it. Suppose that $P$ passes through exactly $a \leq k$ points with $x$-coordinates $x_1,\dots,x_a$. Consider the graph of $Q(x)=P(x)+a(x-x_1)\dots(x-x_n)$. If we start $a$ at $0$ and either increase it or decrease it continuously, the graph of the resulting polynomial also varies continuously, so by picking $|a|$ minimal such that $Q(x)$ passes through one of the points that it doesn't already pass through, no other point which previously lied above $Q$ now lies below $Q$ and vice versa (it's possible for additional points to end up on $Q$ but that's fine). Since $\deg Q \leq k$ as well, by repeatedly doing this until we cannot, we stop when we get a polynomial that passes through at least $k+1$ points as desired. $\blacksquare$ Now, consider the set $S$ of the $N$ points $(1,0),\ldots,(N-3,0),(N-2,0),(N-1,(N-2)!),(N,(N-1)!)$, coloring a point red iff its $x$-coordinate is the same as $N$. Call the base the $N-3$ points $(1,0),\dots,(N-3,0)$ and the auxillary the other three points. Also, let "point $a$" refer to the point with $x$-coordinate $a$ (just for convenience). To show that this works, suppose FTSOC we have a polynomial $P(x)$ of degree (at most) $N-3$ that divides the points in this set. By our lemma, we can suppose that it passes through $N-2$ points. Consider the following cases on which $N-2$ points these are: Case 1: $P$ passes through every point in the base. Then it must be of the form $c(x-1)\dots(x-(N-3))$. Further, we must have $c \in \{0,1,2\}$, where $P(x)$ passes through point $N-2+c$. If $c=0$, then red point $N$ and blue point $N-1$ lie above $P(x)$ which is bad. Similarly, if $c=2$ then red point $N-2$ and blue point $N-1$ lie on the same side of $P(x)$, and if $c=1$ then red points $N$ and $N-2$ lie on different sides of $P(x)$. Thus this case cannot hold. Case 2: $P$ passes through every point in the base except for some point $a$. Then it must be of the form $(x-1)\ldots(x-(a-1))(x-(a+1))\ldots(x-(N-3))R(x)$, where $R(x)$ is a linear polynomial that passes through two of the points $(N-2,0),(N-1,N-a-1),(N,2(N-a))$. Evidently the (single) root of $R$ is greater than $N-3$. Thus, If the two points are $(N-2,0),(N-1,N-a-1)$, then $P(x)$ passes below the red point $N$, but passes below $a$ iff $a$ and $N$ have opposite parity: contradiction. If the two points are $(N-2,0),(N-1,N-a-1)$, then $P(x)$ passes above the blue point $N-1$, but still passes below $a$ iff $a$ and $N$ have opposite parity: contradiction. If the two points are $(N-1,N-a-1),(N,2(N-a))$, then $P(x)$ passes above the red point $N-2$, but... you know where this is headed, right? Contradiction. This completes case 2. Case 3: $P$ passes through every point in the base except for points $a,b$ with $a<b$. Then it must also pass through all points in the auxillary, so it's of the form $(x-1)\ldots (x-(a-1))(x-(a+1))\ldots(x-(b-1))(x-(b+1))\ldots(x-(N-3))R(x)$, where $R(x)$ is a quadratic polynomial that passes through the points $(N-2,0),(N-1,(N-a-1)(N-b-1)),(N,2(N-a)(N-b))$. The bulk of this case involves proving that the other root (not equal to $N-2$) of $R(x)$ is greater than $b$. This is true iff the quadratic with roots $N-2$ and $b$ that passes through $(N-1,(N-a-1)(N-b-1))$ passes below $(N,2(N-a)(N-b))$. This quadratic evidently has leading coefficient $N-a-1$, so at $x=N$ it equals $2(N-a-1)(N-b)<2(N-a)(N-b)$ as desired. given this, it follows that $a$ (sim. $b$) lies above $P(x)$ iff it lies above $(x-1)\ldots (x-(a-1))(x-(a+1))\ldots(x-(b-1))(x-(b+1))\ldots(x-(N-3))$. For $a$, this happens iff $a$ and $N-3$ are the same parity, but for $b$ this happens iff $b$ and $N-3$ are the opposite parity. Thus if $a$ and $b$ are the same parity (equiv. color) they lie on opposite sides of $P(x)$, and if they're opposite parity then they lie on the same side of $P(x)$, obtaining the desired contradiction. Since these three cases cover all possible $P(x)$ under our lemma, we have proven that such a polynomial $P$ cannot exist, so we're done. $\blacksquare$

We claim the answer $k=N-2$. Firstly, take the Lagrange interpolating polynomial of $N-1$ points from set as an example. Now, take a polynomial $f(x)$ of degree $N-2\geq 1$ and choose $N$ points on it's graph, with alternative coloring in order of $x-$coordinate increasing. We claim, that the set of chosen points can't be divisible by a polynomial of degree at most $N-3$. Assume the opposite; let $g(x)$ be a dividing polynomial with $\deg g\leq N-3,$ and WLOG no red points lie below it's graph. Define $h(x)=f(x)-g(x);$ clearly if we pick two consecutive points with abscissas $b$ (the blue one), $r$ (the red one), then $h(b)\leq 0\leq h(r).$ In case $b<r$ there exist $a\in (b;r)$ such that $h'(a)> 0$. In case $r<b$ there exist $a\in (r;b)$ such that $h'(a)<0$. Thus there is a sequence of $N-1$ points in which $h'(x)$ alternates it's sign, and so it has at least $N-2$ roots. But $\deg h'=\deg h-1=N-3,$ contradiction.

Nice and quite subtle problem. The answer is $N-2$. Construction: Take any polynomial $P$ of degree $N-2$ passing through any of the $N-1$ points. Bound: Let the points $P_i = (i, 0)$ with $i \in [n] \setminus \{3\}$ and let $P_3 = (3, 1)$. Color $P_i$ red if $i \in \{1, 3\} \cup \{2i \mid 4 \leq 2i \leq n\}$ and blue otherwise. We have essentially two cases: First Case: Suppose all red points lie on or above $P$. Then, $P$ must be increasing in the interval $[1, 2]$. Now, if $P$ is increasing in $[2, 3]$ too, it passes through some point $(3, a_3)$ with $0 < a_3 \leq 1$. But by condition it must pass through $(4, a_4)$ for $a_4 \leq 0$, thus $P$ has a critical point somewhere in that interval. Similarly, note that $P$ passes through $(2i, a_{2i})$ with $a_{2i} \leq 0$ and $(2i+1, a_{2i+1})$ with $a_{2i+1} \geq 0$, hence $P$ alternates increasing and decreasing in the intervals $[2i, 2i+1]$ and $[2i+1, 2i+2]$. It follows that $P$ has at least $N - 3$ critical points, and $\deg P \geq N-2$. Second Case: Suppose all red points lie on or below $P$. We may repeat the same argument as previous to obtain at least $N-3$ critical points in this case too.

wow cool statement

The answer is $k=N-2$. To show this $k$ works, choose the first $N-1$ points and find the interpolating polynomial of degree at most $N-2$. Choose the blue/red direction based on whether the polynomial is above or below the last point. To show this $k$ is necessary, consider the points \[Y=(-1,1),Z=(0,1),X_1=(1,0),X_2=(2,0),\dots,X_{N-2}=(N-2,0),\]set $Y$ and $X_{\text{even}}$ to be blue and the rest red. ($N-2\geq1$ since $N\geq3$, so at least one $X$ point exists.) Clearly $P$ must be nonconstant. The main claim is that given three points $Q_1(x_1,y_1),Q_2(x_2,y_2),Q_3(x_3,y_3)$, with $x_1<x_2<x_3$ and $y_2\leq y_1$ and $y_2\leq y_3$, if $P$ is nonconstant, goes below $Q_2$ and above $Q_1$ and $Q_3$ then $P$ has a local minimum on the open interval $(x_1,x_3)$. Restrict $P$ to $[x_1,x_3]$, since it is continuous it attains an absolute minimum on this interval. If this minimum coincides with either $y_1$ or $y_3$, then it must also equal $y_2$ by the inequality condition, so $x_2$ is where the minimum occurs. Otherwise, the minimum doesn't occur at either endpoint so it must occur in the open interval. The claim works similarly if all the signs pertaining to the $y$ coordinate are flipped, by considering $-P$. Now we count the number of turning points of $P$. In the case that the polynomial goes above red points, we can find a minimum of the function on the intervals $(1,3),(3,5),\dots,(x-2,x)$ where $x$ is the largest odd number less than or equal to $N-2$. This is done by applying the claim to $X_{2i-1},X_{2i},X_{2i+1}$. We can find a maximum of the function on the intervals $(2,4),(4,6),\dots,(y-2,y)$ similarly, where $y$ is the largest even number less than or equal to $N-2$. Finally, applying the claim to $Y,Z,X_2$ we get another maximum on $(-1,2)$. This adds up to $N-3$ turning points, which shows the degree is at least $N-2$. They are all distinct because the intervals where the maximums occur don't overlap, same with the minimums. In the other case, we swap maximums and minimums, with the exception that we apply the final claim to $Y,X_1,X_2$ to get a minimum on $(-1,2)$. In this case, degree $N-2$ is also forced.

Answer $N-2$. To bound take $(1,0),(2,0),\dots,(N-2,0),(N-1,1),(N,1)$ where $(x,y)$ red iff $x$ odd. Notice $P=0$ fails. Suppose red points are above the graph. Then for $1<x<3$ there is a local maximum, since either $P$ goes above $0$ and then the maximum of $P$ on $[1,3]$ is not an endpoint, or $P(2)=0$ is a local maximum. Similarly, for $2<x<4$ there is a minimum, and $3<x<5$ has a maximum, and so on until $N-4<x<N-2$. Now if $N$ is odd then there is a local maximum in $N-2<x<N$ since either $P$ goes above $1$ and the maximum on $[N-2,N]$ is not an endpoint, or $P(N-1)=1$ is a local maximum. If $N$ is even there is a local minimum in $N-3<x<N-1$ since either $P$ goes below $0$ and the minimum on $[N-3,N-1]$ is not an endpoint, or $P(N-2)=0$ is a local minimum. Thus we have found $N-3$ distinct local extrema, so $P'$ has degree $\ge N-3$ so $P$ has degree $\ge N-2$. Similarly, we can check this still holds for blue points above the graph. To construct, interpolate a polynomial through $P-1$ of the points, which will have degree $\le N-2$.