ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 65253
Темы:    [ Интерполяционный многочлен Лагранжа ]
[ Многочлен n-й степени имеет не более n корней ]
[ Возрастание и убывание. Исследование функций ]
[ Примеры и контрпримеры. Конструкции ]
[ Доказательство от противного ]
Сложность: 4+
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Автор: Тыщук К.

Дано натуральное число  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).  Противоречие.

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Вариант 2014/2015
этап
Вариант 5
класс
Класс 11
задача
Номер 11.4

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .