Возьмём произвольные  n – 1  из данных n точек; существует многочлен степени, не большей  n – 2,  график которого проходит через них. Этот многочлен, очевидно, разделяет наши точки. Таким образом,  k = n – 2  подходит. Докажем, что уменьшить это число нельзя.   Возьмём график некоторого приведённого многочлена  f(x) степени  n – 2  и расположим на нем n точек, чередуя цвета. Предположим, что некоторый многочлен P(x), степень которого не больше  n – 3,  разделяет эти точки; можно считать, что ниже графика P(x) нет красных точек, а выше – синих.

  Степень многочлена  Q(x) = f(x) – P(x)  равна  n – 2 ≥ 1.  Кроме того, если r и b – абсциссы произвольных красной и синей точек, то  P(r) ≤ f(r)  и  P(b) ≥ f(b),  то есть  Q(r) ≥ 0  и  Q(b) ≤ 0.

  Заметим, что если  Q(s) ≤ Q(t)  при некоторых  s < t,  то существует такая точка  u ∈ (s, t),  для которой  Q'(u) > 0  (здесь использовано, что Q(x) – не константа). Это значит, что на каждом интервале между красной и синей точками (красная левее синей) найдётся точка, в которой значение Q'(x) положительно. Аналогично, на каждом интервале между синей и красной точками найдётся точка, в которой значение Q'(x) отрицательно. Итого, мы нашли  n – 1  точек, в которых Q'(x) принимает значения чередующихся знаков. Между любыми такими соседними точками Q'(x) имеет корень. Следовательно, у многочлена Q'(x) не менее  n – 2  корней. Но это невозможно, так как  Q'(x) – многочлен степени  n – 3.  Противоречие.

k = n – 2.