|
|
 |
Условие
Дано натуральное число n > 3. Назовём набор из n точек на координатной плоскости допустимым, если их абсциссы различны, и каждая из этих точек окрашена либо в красный, либо в синий цвет.
Будем говорить, что многочлен P(x) разделяет допустимый набор точек, если либо выше графика P(x) нет красных точек, а ниже – нет синих, либо наоборот (на самом графике могут лежать точки обоих цветов). При каком наименьшем k любой допустимый набор из n точек можно разделить многочленом степени не более k?
Решение
Возьмём произвольные 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.
Замечания
Немного изменив рассуждения, можно показать, что в качестве f(x) можно взять любую функцию, у которой (n–2)-я производная не имеет корней; подойдёт, например, f(x) = 2x. Действительно, из того, что у Q'(x) не меньше n – 2 корней, следует, что у (n–2)-й производной функции Q(x) не менее одного корня; но Q(n–2)(x) = f (n–2)(x) – P(n–2)(x) = f (n–2)(x). Противоречие.
