Тема Заключительный этап ВсОШ

Закл (финал) 11 класс → .02 Закл 2015

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела заключительный этап всош

Разделы подтемы Закл (финал) 11 класс

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#122901Максимум баллов за задание: 7

Дано натуральное число $N ≥ 3$ . Назовём набор из $N$ точек на координатной плоскости допустимым, если их абсциссы различны, и каждая из этих точек окрашена либо в красный, либо в синий цвет. Будем говорить, что многочлен $P (x)$ разделяет допустимый набор точек, если либо выше графика $P (x)$ нет красных точек, а ниже — нет синих, либо наоборот (на самом графике могут лежать точки обоих цветов). При каком наименьшем $k$ любой допустимый набор из $N$ точек можно разделить многочленом степени не более $k?$

Показать доказательство

Докажем, что $k= N − 2$ подходит. Возьмем произвольные $N − 1$ из данных $N$ точек; существует многочлен степени, не большей $N − 2,$ график которого проходит через них. Этот многочлен, очевидно, разделяет наши точки.

Осталось построить пример допустимого набора, который нельзя разделить многочленом степени, меньшей $N − 2.$ Возьмем график некоторого приведенного многочлена $f(x)$ степени $N − 2$ и расположим на нем $N$ точек, чередуя цвета. Предположим, что некоторый многочлен $P (x),$ степень которого не больше $N − 3,$ разделяет эти точки; можно считать, что ниже графика $P(x0$ нет красных точек, а выше — синих.

Обозначим $Q (x)= f(x)− P(x);$ степень многочлена $Q(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$ непостоянен). Это значит, что на любом интервале между красной и синей точками (красная левее синей) найдется точка, в которой значение $Q′(x)$ положительно. Аналогично, на любом интервале между синей и красной точками найдется точка, в которой значение $Q′(x)$ отрицательно. Итого, мы нашли $N − 1$ точек, в которых $Q′(x)$ принимает значения чередующихся знаков. Между любыми такими соседними точками $Q ′(x)$ имеет корень. Следовательно, у многочлна $Q ′(x)$ не менее $N − 2$ корней. Но это невозможно, так как $Q′(x)$ — многочлен степени $N − 3.$ Противоречие

Предыдущая подтема

Следующая подтема