Тема Высшая проба

Многочлены на Высшей пробе

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

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

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

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

Подтемы раздела высшая проба

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

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

Задача 1#74781

Найдите все действительные числа $d,$ для которых существуют многочлены от одной переменной $P$ и $Q,$ такие что равенство

P(x) P(x+ d) 1 Q(x) − Q(x+-d) = x(x-+1)

выполняется при всех значениях $x$ , кроме конечного числа (есть лишь конечное множество значений $x$ , для которых равенство не выполняется).

Источники: Высшая проба - 2022, 11.4 (см. olymp.hse.ru)

Подсказки к задаче

Подсказка 1

Мы знаем, что 1/x(x+ 1) = 1/x - 1/(x + 1) - так мы удобно для себя разложили правую дробь. Однако, мы знаем, что любую, так называемую иррациональную дробь (то есть, где сверху и снизу - многочлены) можно разложить на сумму вида P_i(x) / (x - alpha_i) ^ n_i, где P_i(x) - не нулевой многочлен, а alpha_i - корень, возможно комплексный(чтобы было линейно разложимо) многочлена Q(x). Поэтому основная идея задачи - разложить дроби в такой вид и смотреть на то, могут ли как-то сократиться подобные. То есть, если у вас есть к примеру, в левой часть какой-то не сократившийся член 1/(x + k), а справа его нет, то это значит, что равенство происходит только в конечном числе точек, что нам не подходит. В правой часть у нас только 1/x - 1/(x + 1), значит и в левой части должно быть также. Значит, по нашему предположению о решении задачи - хотелось бы доказать, что-то насчет 0,1 и их связи с корнями. Если мы хотим доказывать от противоречия и как-то использовать корни, то, с учетом вот этой «несократимости», которая была описана выше, как мы хотим его получить?

Подсказка 2

Удачным был бы шаг решения, когда мы получили какой-то корень отличный от 0 и 1, при этом, такой, чтобы он был корнем Q(x), но не корнем Q(x + d), потому что тогда бы мы получили бы в нашем разложении на сумму дробей что-то, что не сокращается с Q(x + d) и не сокращается с правой частью. И поскольку мы каждый раз прибавляем x + d (напомним - мы можем подставлять почти, с точностью до конечного числа, любые значения и будет выполнено равенство), то наверное правильным решением будет ввести понятие цепи - всевозможных чисел вида alpha + md, где m - целое и alpha - корень Q(x). А также нам надо что-то понимать про то, какие из чисел этой цепи являются корнем или нет. Попробуйте использовать принцип крайнего и получите хорошее утверждение, которое значит больше половины задачи.

Подсказка 3

Нам удобно ввести m_- и m_+ - наименьшее и наибольшее соотвественно число, при котором alpha + md является корнем Q(x) (корректно ли это определение?). Тогда в смысле цепи нам бы хотелось доказать, что если alpha - корень, то 0 и 1 лежат в цепи alpha. Предположим, что хотя бы одно не лежит в цепи. Тогда, корень Q(x) - alpha_i = alpha + m_+ * d не равно ни 0, ни 1. Может ли быть, что это также корень Q(x + d)? А о чем тогда это говорит в связи с предыдущими рассуждениями?

Подсказка 4

Конечно, это не может быть корнем Q(x + d), иначе тогда бы alpha + (m_+ + 1) * d был бы корнем Q(x), что противоречит максимальности. Тогда эта дробь, соответствующая корню, не сократится ни с Q(x + d), ни с правой частью. А потому пришли к противоречию. Значит, для некоторого целого m_1 верно, что alpha + m_1 * d = 0, и для некоторого целого m_2 верно, что m_2 * d + alpha = 1, а значит, (m_2 - m_1) * d = 0 = > для некоторого целого m выполнено, что md = 1 => d = 1/m, где m - целое. Осталось доказать, по хорошему, конструктивно, что все такие d подходят. Если строить пример, то надо строить его в виде уже разложенных в сумму дробей многочленов, потому что нам потом самим раскладывать. Какой тогда пример мы можем привести, если хотим, чтобы после разности очень похожих дробей (по сути - все сместится на 1/m в знаменателях и это будет что-то очень похожее), у нас осталось только 1/x - 1/(x + 1)? Может быть как то, условное «смещение» некоторой последовательности использовать? А как его добиться?

Подсказка 5

Если мы хотим добиться смещения по последовательности, то нам надо, чтобы при прибавлении 1/m для каждого члена у нас получался следующий, а также, чтобы последний член становился равным 1, чтобы получалось 1/(x + 1). На такую роль очень подходит дробь вида 1/x + 1/(x + 1/m) + 1/(x + 2/m) + … + 1/(x + (m - 1)/m). Тогда все работает. А правда ли, что этот пример работает для всех m? А если взять m = -1? К тому же, стоит, напоследок, перед тем как полностью решить задачу подумать, к чему тут именно конечное число точек, а не нулевое и везде ли мы делали корректные переходы не упуская случай d = 0. Пробегитесь по решению и проверьте на корректность все

Показать ответ и решение

Сразу заметим, что при $d= 0$ равенство из условия невозможно, так что далее мы везде считаем, что $d⁄= 0$ даже когда не напоминаем об этом явно.

Предположим, что такие многочлены $P$ и $Q$ нашлись. Тогда можно считать, что они взаимнопросты (иначе поделим оба на общий множитель — новая пара тоже удовлетворяет условию), и у $Q$ старший коэффициент равен 1 (домножим $P$ и $Q$ на константу , чтобы старший коэффициент стал равен 1). Введем обозначение для разложения $Q$ на линейные множители (естественно, воспользовавшись существованием такого разложения в комплексных числах):

Q(x)=(x− α1)n1(x− α2)n2⋅⋅⋅(x− αk)nk

Для комплексного числа $α$ множество чисел вида $α +md,$ где $m ∈ℤ$ , будем называть цепью числа $α.$

______________________________________________________________________________________________________________________________________________________

Ключевое утверждение:

Если $α$ — корень $Q,$ то числа 0 и 1 принадлежат цепи $α.$

______________________________________________________________________________________________________________________________________________________

Доказательство.

Пусть $α$ — корень $Q,$ тогда обозначим через $m−$ и $m+$ такие минимальное и максимальное значения $m,$ при которых $α+ md$ является корнем $Q.$ Заметим, что $m−$ и $m+$ определены корректно: множество значений $m$ не пусто (поскольку 0 подходит) и конечно, поскольку у $Q$ конечное число корней (первое место, в котором важно, что $d⁄= 0$ ). Тогда пусть не оба числа 0 и 1 лежат в цепи $α.$ Тогда одно из двух чисел $α+ (m− − 1)d$ и $α+ m+d$ не является ни 0 ни 1 (второе место: нам важно, что $α +(m − − 1)d$ и $α +m+d$ — два разных числа). Рассмотрим эти два случая.

Пусть $α+ m+d= αi$ — не равно ни 0 ни 1. Посмотрим на равенство из условия

P-(x)− P(x+-d)= ---1-- = 1− -1-- Q (x) Q(x+ d) x(x+ 1) x x+ 1

и разложим левую часть на простейшие дроби:

P(x)= P (x)+ --P1(x)-- +--P2(x)- +⋅⋅⋅+--Pk(x)- , Q (x) 0 (x− α1)n1 (x− α2)n2 (x− αk)nk

где степень $Pi(x)$ меньше $ni$ при $1 ≤i≤ k,$ причем $Pi ⁄= 0.$

Поскольку $αi$ — корень $Q,$ в разложение $PQ((xx))$ входит член со знаменателем $(x − αi)ni$ и ненулевым числителем. Но $αi$ — не корень $Q (x+ d),$ иначе $α + d= α+ (m +1)d i +$ было бы корнем $Q(x),$ что противоречило бы максимальности $m +$ . Тогда член со знаменателем $ni (x− αi)$ не входит в разложение $P(x+d) Q(x+d),$ значит члену с таким знаменателем слева не с чем сократиться — но он не входит в правую часть — противоречие.

_________________________________________________________________________________________________________________________________________________________________________________

Итак, мы доказали, что если у многочлена $Q$ есть комплексные корни, то в цепь этого корня входят числа 0 и 1, то есть выполняется равенство $-1 d= m$ для какого-то целого $m$ . Если же у $Q$ нет комплексных корней, то он - ненулевая константа, то есть $P(x)- Q(x)$ и $P (x+d) Q-(x+d)$ — многочлены, тогда их разность не может равняться $x(x1+1).$

Осталось показать, что все значения вида $d= 1m,$ где $m ∈ ℤ,m ⁄= 0$ подходят. Для $m >0$ достаточно взять функцию

1+ --11-+ --12-+ ⋅⋅⋅+ ---1m−1- x x+ m x+ m x+ m

и привести сумму к общему знаменателю, числитель взять в качестве $P,$ а знаменатель — $Q.$ Для $m <0$ то же самое сделать с суммой

-−1- ---−1--- --−-1--- -−-1-- x+ 1 + x+ −m−−m1-+ x+ −m−−m2-+⋅⋅⋅+ x+ −1m

Ответ:

$d =-1, m$ где $m ∈ℤ,m ⁄= 0$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

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

Задача 2#75239

Дана пара взаимно-простых многочленов с действительными коэффициентами $P(x)$ и $Q (x)$ степеней $2021$ и $2000$ соответственно (взаимно-простые означает, что не существует многочлена $R (x),$ не равного константе, на который делятся $P(x)$ и $Q(x)).$ Гриша выбирает конечное множество действительных чисел $c1,...,cn$ (помните, в множестве элементы не повторяются, размер множества Гриша тоже выбирает сам), находит число различных кратных действительных корней у многочлена $P (x)+ ciQ(x)$ (при $i$ от 1 до $n$ ) и складывает полученные числа. Какую наибольшую сумму Гриша может получить в результате этого процесса?

Источники: Высшая проба - 2021, 11.5(см. olymp.hse.ru)

Подсказки к задаче

Подсказка 1

Как нам определить является ли какое-то число кратным корнем? Очень просто - надо проверить, что оно зануляет многочлен и его производную(для общего развития - подумайте какое условие нужно записать, чтобы найти корень кратности k, где k - константа). Запишите проверку на кратность корня и подумайте как компактнее записать эти два условия.

Подсказка 2

Верно, компактнее можно записать эти условия так: Q(a) != 0(почему?) и (P(x)/Q(x))’(a) = 0, где а - наш кратный корень. Как тогда оценить количество кратных корней, если все искомые кратные корни - это корни многочлена производной дроби выше?

Подсказка 3

Количество корней не больше степени многочлена, а значит, осталось найти степень и построить пример. Со степенью легко, а из каких соображений строить пример? Нам нужно, чтобы у производной было много корней. Какая теорема помогает нам искать корни производной на промежутке(нам же нужно как то полу конструктивно найти много корней производной)? Если вы поймете, что это за теорема, то подогнать данное в задаче под условие этой теоремы будет не так уж трудно.

Подсказка 4

Будем подгонять ситуацию под условие теоремы Ролля. Нам нужна непрерывность и дифференциируемость на интервале и равные значения в концах. Давайте, чтобы одни корни многочлена не залезали на другие, скажем, что у P(x) все корни действительные и различные и их столько же, какая степень, при этом, все они лежат слева от корней многочлена Q(x) на которые накладываются те же условия. Тогда остается взять за интервалы - интервалы между корнями, проверить, что все требуемые условия для теоремы Ролля выполняются, а также как-то подогнать под условие теоремы Ролля интервалы с концами в корнях Q(x), подумать про их количество и каким, может быть не интервалом, но другим промежутком, можно заменить недостающий интервал, если такой есть(спойлер - есть).

Показать ответ и решение

Оценка.

_________________________________________________________________________________________________________________________________________________________

Лемма. В Гришиной сумме могут быть учтены те и только те числа $α$ , в которых производная функции $P-(x) f(x)= Q (x)$ обращается в ноль, причем каждое такое $α$ может быть посчитано максимум для одного $ci$ .

_________________________________________________________________________________________________________________________________________________________________________________

Доказательство. Как известно, число $α$ является кратным корнем многочлена $T (x)$ если и только если $α$ является корнем многочлена $T (x)$ и его производной $T ′(x)$ . Пусть $α$ — кратный корень $P (x)+ cQ (x)$ , имеем левую из систем:

( ( ( { P(α)+ cQ (α)= 0(∗) ⇔ { Q(α)⁄= 0 ⇔ { ′ Q(′α)⁄= 0 ( P ′(α)+cQ′(α )=0(∗∗) ( P′(α)− PQ((αα))Q ′(α)= 0 ( P(α)Q(αQ)−2P(α)(α)Q(α)= 0

Первая равносильность заслуживает пояснений: из уравнения $(∗)$ если $Q(α)= 0$ что и $P(α)=0,$ то невозможно поскольку многочлены взаимно-просты. Если же $Q (α)⁄= 0$ то деление на него является равносильным переходом, а $c$ однозначно находится из (*). Второй переход: просто поделили на $Q (x).$ Осталось заметить, что $P′(x)Q(x)Q−2(Px()x)Q′(x)$ это в точности производная $P-(x). Q (x)$

______________________________________________________________________________________________________________________________________________________

Итак, мы получили что все числа, посчитанные в гришиной сумме, это корни многочлена $T(x)= P′(x)Q (x)− P(x)Q ′(x),$ который имеет не более чем $4020$ степень (при взятии производной степень многочлена уменьшается на единицу, при перемножении многочленов - складывается, при вычитании не увеличивается), покажем что $T(x)$ не может быть тождественно нулем (на самом деле покажем, что степень ровно $4020$ ). Пусть $p 2021$ и $q 2000$ — старшие (а значит, ненулевые) коэффициенты многочленов $P(x)$ и $Q(x)$ соответственно. Тогда коэффициент $T(x)$ при $x4020$ есть $2021p q − 2000p q = 21p q ⁄= 0. 2021 2000 20212000 20212000$ Таким образом, мы доказали оценку сверху: сумма не может быть больше $4020.$

______________________________________________________________________________________________________________________________________________________

Пример.

Возьмём $P (x)$ и $Q(x)$ такими, что все их корни вещественны, различны и все корни $P(x)$ лежат левее всех корней $Q (x).$ Тогда есть $2020$ отрезков между соседними корнями $P(x),$ на каждом из этих отрезков функция $f(x)$ непрерывна (все корни знаменателя правее), равна нулю в концах отрезка и не равна нулю в остальных точках, значит в какой-то точке производная принимает нулевое значение по теореме Ролля — нашли $2020$ нулей производной. Теперь посмотрим на интервалы между соседними корнями $Q(x),$ и также на открытый луч от самого правого из них до плюс бесконечности. На каждом интервале функция непрерывна, не меняет знак (поскольку не принимает нулевого значения — все корни числителя лежат левее), в концах интервалов $f(x)$ стремиться к бесконечности (поскольку это корни числителя), при $x→ +∞$ аналогично $f(x)$ стремится к бесконечности, поскольку степень числителя больше степени знаменателя. Значит, на каждом из промежутков модуль достигает минимума во внутренней точке, там производная обращается в ноль (альтернативно можно воспользоваться теоремой Ролля для функции $1 f(x)$ ) — нашли еще $2000$ нулей производной.