Тема ПитерГор (Санкт-Петербургская олимпиада)

Многочлены на Питергоре

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

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

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

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

Подтемы раздела питергор (санкт-петербургская олимпиада)

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

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

Задача 1#82682

Дан многочлен $P(x)$ с целыми коэффициентами. Для некоторого натурального $n$ числа $P (0),P(1),...,P (2n+ 1)$ делятся на $22n$ . Докажите, что значения многочлена $P(x)$ во всех целых точках делятся на $2n 2$ .

Источники: СПБГОР - 2024, 11.6 (см. www.pdmi.ras.ru)

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

Подсказка 1

Чтобы доказать, что у нас многочлен во всех точках кратен чему-то, бывает удобно представлять этот многочлен в виде, когда мы поделили его на какой-то другой с остатком, то есть представить P(x) = Q(x) * S(x) + R(x), и делили мы на многочлен на Q(x). Тогда если мы докажем, что во всех точках Q и R кратны чему-то, то докажем это и для P(x). Тогда, давайте сразу возьмём в качестве Q какой-то многочлен, который кратен 2^2^n. К примеру, x(x - 1)…(x - (2^n + 1)). Докажите, что такой многочлен действительно кратен 2^2^n, а после поймите какие условия тогда мы получаем на R(x).

Подсказка 2

Q(x) кратен, поскольку у нас произведениe k последовательных целых чисел кратно k!, и при этом у k! мы можем посчитать степень вхождения 2. В таком случае, на R(x) накладываются ровно такие же условия, как на P(x). А что значит, если многочлен, который принадлежит Z[x](поймите почему), и имеет степень меньшую, чем у Q, а также в хотя бы в deg(Q) подряд идущих целых точках кратен некоторому числу?

Подсказка 3

Это значит, что он кратен этому числу во всех целых точках, поскольку мы можем поделить на это целое число и индукцией показать, что если многочлен целочисленный в хотя бы t+1 подряд идущей целой точке, при том, что его степень не больше t, то он целочисленный во всех целых точках. Что тогда это нам даёт в рамках задачи?

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

Среди $2n +2$ подряд идущих целых чисел $x$ , $x − 1$ , …, $x− (2n +1)$ есть хотя бы $[(2n+ 2)∕2]$ кратных двум, хотя бы $[(2n+ 2)∕4]$ кратных $4$ , и т.д. Значит, суммарная степень вхождения $2$ в их произведение не меньше

∑ n k ∑ n−k n−1 n−2 n− 3 n [(2 +2)∕2 ]= 1+ [2 ]= (2 + 1)+2 + 2 +...+1= 2 k k

Поэтому все значения многочлена $Q(x)= x(x− 1)...(x− (2n +1))$ в целых точках кратны $22n.$

Поделим $P(x)$ на $Q(x)$ с остатком: $P(x)=Q (x)S(x)+R(x)$ . Поскольку старший член $Q(x)$ равен 1, $R (x)∈ ℤ[x]$ , причем $R(x)$ будет удовлетворять тем же условиям, которым удовлетворяет $P(x)$ , и к тому же будет иметь степень не выше $2n+ 1$ . Поделив его на $22n$ , мы получим многочлен степени не выше $2n+1$ , значения которого $2n+2$ подряд идущих целых точках целые. Из этого следует, что целыми являются все его значения в целых точках (это доказывается по индукции с использованием разностного многочлена). Таким, образом, у многочлена $R(x)$ все значения в целых точках кратны $22n$ , а тогда это верно и для многочлена $P (x)$ .

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

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

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

Задача 2#89862

Пусть $f(x)$ — квадратный трёхчлен, $g(x)$ —многочлен степени 3. Может ли многочлен $f(g(x))$ иметь шесть различных корней, являющихся степенями 2?

Источники: СПБГОР - 2023, 11.1 (см.pdmi.ras.ru)

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

Подсказка 1

Что если a является корнем f(g(x))? Что можно сказать про g в этой точке? А сколько раз g может принимать конкретное значение?

Подсказка 2

Многочлен g(x) принимает каждое действительное значение не более 3 раз. А если a — корень f(g(x)), то g(a) — это корень f(x). В каком тогда случае f(g(x)) будет иметь 6 корней?

Подсказка 3

У f(x) есть два различных корня, каждое из которых достигается g(x). Давайте попробуем записать корни f(g(x)) через корни f(x). Пусть корни последнего это a и b. Что если предположить, что они действительно степени двойки?

Подсказка 4

Пусть двойки в некоторых степенях это корни многочленов g(x) - a и g(x) - b. С помощью чего можно записать условие на корни?

Подсказка 5

С помощью разложения на скобки! k1(x-2^(a₁))(x-2^(a₂))(x-2^(a₃)) + a = k2(x-2^(b₁))(x-2^(b₂))(x-2^2(b₃)).

Подсказка 6

Обратите внимание на коэффициенты перед x^2.

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

Заметим, что многочлен $g(x)$ принимает каждое действительное значение не более 3 раз, так как у него степень ровно 3. Если $a$ — корень $f(g(x))$ , то $g(a)$ — корень квадратного трёхчлена $f(x) =⇒$ 6 корней у многочлена $f(g(x))$ достигаются только в том случае, если у $f(x)$ есть 2 различных корня, каждый из которых достигается ровно трижды многочленом $g(x)$ . Скажем, $a,b$ — корни $f(x)$ , $a1 a2 a3 2 ,2 ,2$ — корни многочлена $g(x)− a$ , $b1 b2 b3 2 ,2 ,2$ — корни многочлена $g(x)− b$ . Тогда справедливо следующее:

k1(x− 2a1)(x− 2a2)(x − 2a3)+a =g(x)=k2(x− 2b1)(x− 2b2)(x− 2b3)+b

Понятно, что $k = k ⁄= 0 1 2$ , как коэффициенты при $x3$ . Рассмотрим коэффициент при $x2$ у левой и правой части равенства:

a a a b b b k1(21 +2 2 + 23)= k1(21 +2 2 + 23)

a1 a2 a3 b1 b2 b3 2 + 2 +2 = 2 + 2 +2

Предположим, что наши корни различны. Но тогда одно и то же натуральное число представимо в двоичной системе счисления двумя разными способами — противоречие. Значит, рассматриваемый многочлен не мог иметь 6 различных корней, являющихся степенями двойки.

Ответ: нет

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

Задача 3#70482

Иван и Кощей играют в следующую игру. Изначально на доске записан многочлен $x− 1.$ За один ход можно заменить многочлен $f(x),$ записанный на доске, на многочлен $n+1 ax − f(− x)− 2,$ где $n$ — степень многочлена $f(x),$ а $a$ — один из его вещественных корней. Игроки ходят по очереди, начинает Иван. Выигрывает тот игрок, после хода которого на доске будет написан многочлен, не имеющий вещественных корней. Сможет ли Иван победить Кощея?

Источники: СПБГОР - 2022, 11.3 (см. pdmi.ras.ru)

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

Подсказка 1

Вспомним полезную теорему про многочлен нечётной степени! Что в таком случае можно сказать про Ивана?

Подсказка 2

Да, он точно не проиграет, ведь на его ходе всегда будет получаться многочлен нечётной степени, у которого всегда есть хотя бы один вещественный корень! А что можно сказать про Кащея? Для ответа на этот вопрос: рассмотрите f(0), где f - многочлен чётной степени, с положительным старшим коэффициентом!

Подсказка 3

Да, поскольку у нас изначально многочлен равен x-1(корень 1), то Кащей может на каждом шаге брать вместо a - положительный корень предыдущего многочлена(который всегда существуют)! А тогда, у многочлена Кащея тоже всегда будет вещественный корень!

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

Ивану достаётся многочлен нечетной степени, поэтому он не может проиграть. Однако Кощей тоже не может проигрывать: для этого ему достаточно каждый раз выбирать положительный корень. Заметим, что свободный член всегда равен $− 1.$ Легко проверить, что при такой стратегии Кощея Ивану будут доставаться многочлены нечетной степени с чередующимися знаками коэффициентов (старший - положительный), и поэтому у них есть лишь положительные корни; а Кощею будут доставаться многочлены четной степени с положительным старшим коэффициентом и свободным членом $− 1,$ поэтому у них существует положительный корень

Ответ:

Нет

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

Задача 4#71907

Дан многочлен $f(x)$ степени $2000.$ При этом у многочлена $f(x2− 1)$ ровно $3400$ корней, а у многочлена $f(1− x2)$ ровно $2700$ корней. Докажите, что расстояние между какими-то двумя корнями $f(x)$ меньше $0,002.$

Источники: СпбОШ - 2019, задача 11.1(см. www.pdmi.ras.ru)

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

Пусть $f(x)$ имеет корни $c,...,c, 1 k$ где $k ≤2000.$ Так как многочлен $f(x2− 1)$ имеет ровно $3400$ корней, а уравнение $2 x − 1= ci$ имеет не более двух решений, то не более чем $k− 1700$ корней $f$ лежат за пределами $[−1,∞)$ — множества значений $2 x − 1.$ Аналогично, так как $( 2) f 1− x$ имеет ровно 2700 корней, а уравнение $2 1− x = ci$ — не более двух решений, то не более чем $k− 1350$ корней $f$ лежат за пределами $(−∞, 1]$ — множества значений $2 1 − x .$ Значит, не менее

k− (k − 1350)− (k− 1700)= 3050− k≥ 1050

корней $f(x)$ лежат на $[−1,1],$ откуда следует, что среди них есть два на расстоянии менее $0,002.$

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

Задача 5#73376

Коэффициенты многочлена $f(x)$ — целые числа, по модулю не превосходящие 5000000. При этом каждое из уравнений $f(x)= x,f(x)=2x,...,f(x)= 20x$ имеет целый корень. Докажите, что $f(0)= 0.$

Источники: СпбОШ - 2018, задача 10.4(см. www.pdmi.ras.ru)

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

Подсказка 1

Попробуйте обратить внимание на простые числа. Понятно, что если f(0) делится на большое количество простых чисел, то оно либо равно 0, либо больше 5000000. Как мы знаем, второе невозможно.

Подсказка 2

Причём логично рассматривать простые числа, меньшие 20, потому что, используя уравнения из условия, можно манипулировать остатками.

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

Докажем, что $f(0)$ делится на все простые числа, меньшие $20,$ из этого будет следовать, что либо $f(0)= 0,$ либо оно по модулю больше $2⋅3⋅5⋅7⋅11⋅13⋅17⋅19 >5000000.$

Действительно, пусть $f(0)$ не кратно какому-то $p,$ меньшему $20.$ Тогда $x≡ 0 (mod p)$ не может являться решением ни одного из уравнений из условия (левая часть не делится на $p,$ а правая часть делится).

Но очевидно, что решения уравнений $f(x)= x,f(x)= 2x,...,f(x)= px$ должны давать попарно различные остатки при делении на $p$ при условии, что эти остатки ненулевые(иначе вычтем из первого уравнения второе, левая часть сравнима с 0 по модулю $p,$ а правая нет). Однако уравнений у нас $p,$ а возможных остатков $p− 1$ — противоречие.

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

Задача 6#76055

Многочлен $P(x)$ с целыми коэффициентами и натуральное число $a> 1$ таковы, что для любого целого $x$ найдётся целое $z,$ для которого $aP(x)= P(z).$ Найдите все такие пары $(P (x);a).$

Источники: СПбОШ - 2016, задача 10.7(см. www.pdmi.ras.ru)

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

Нам понадобится следующая стандартная лемма.

Лемма. Предположим, что $A,B$ — вещественные числа, причем $A ⁄=±1,$ и многочлен $P(x)$ степени $k >0$ удовлетворяет равенству $k P (Ax +B )=A P (x).$ Тогда $k P(x)=α(x− x0),$ где $-B- x0 = −A −1.$

Доказательство. Положим $Q(x)=P (x +x0).$ Тогда

k k Q(Ax)= P(Ax+ x0)= P(A(x+ x0)+ B)= A P (x+ x0)= A Q(x)

Приравнивая в полученном уравнении $Q(Ax)= AkQ(x)$ коэффициенты при степенях $x,$ видим, что все они, кроме коэффициента при $xk,$ равны $0.$

Ясно, что многочлен $P (x)≡ 0$ удовлетворяет условию при любом $a> 1,$ а многочлен, равный ненулевой константе, не удовлетворяет условию ни при каком $a.$ Пусть теперь степень многочлена $P$ равна $k> 0$ и

k k−1 P(x)= αx +βx + ...

Сделаем несколько наблюдений, не пользуясь соображениями целочисленности из условия задачи. Будем считать, что $α >0$ (для $α <0$ рассуждения аналогичны). Рассмотрим равенство

aP(x)= P(z) (1)

как уравнение относительно $z = z(x).$ Многочлен $P(x)$ монотонен и непрерывен на некотором луче вида $[M, +∞ ).$ Поэтому при больших положительных $x$ это уравнение всегда имеет решение $z(x)> M,$ (непрерывно) зависящее от $x.$ Очевидно, что $z(x)→ +∞$ при $x → +∞.$ При четном $k$ для больших $x$ существует также решение $z(x)< 0;$ в этом случае $z(x)→ − ∞$ при $x → +inf.$

Рассмотрим случай $z(x)> M.$ Пусть $a =ρk$ при некотором вещественном $ρ> 1.$ При фиксированном $x$ и $z =z(x),$ найденном из уравнения $(1),$ рассмотрим переменный вещественный параметр $𝜃,$ для которого

P(ρx+𝜃)− P(z)=P (ρx+ 𝜃)− aP(x)= (βρk−1+ kαρk−1𝜃− βa)xk−1+ ... (2)

Положим $β(a−ρk−1) 𝜃0 =-kαρk−1--$ (для этого значения $𝜃$ коэффициент при $xk−1$ равен $0$ ).

Мы утверждаем, что существует $limx→+∞ (z(x)− ρx)= 𝜃0.$

Доказательство. Рассуждая по определению, выберем числа $𝜃− < 𝜃0 < 𝜃+.$ Тогда при $𝜃= 𝜃−$ и $𝜃= 𝜃+$ правая часть формулы $(2)$ при достаточно больших $x$ принимает большие по модулю значения разных знаков, в то время как при $𝜃= 𝜃0$ правая часть формулы $(2)$ относительно мала по сравнению с этими значениями. В силу монотонности многочлена получаем, что $z(x)$ лежит между $ρx+ 𝜃−$ и $ρx+ 𝜃+.$

Для больших $x,$ для которых $z(x)< 0,$ аналогично получаем, что $z(x)+ ρx$ имеет некоторый конечный предел $Θ.$

Рассмотрим теперь большое натуральное $x.$ Среди чисел $z(x),z(x+ 1),z(x+ 2)$ два имеют одинаковый знак. Если, например, $z(x)$ и $z(x+ 1)$ отрицательны, то

ρ =(z(x +1)+ ρ(x+ 1))− (z(x)+ ρx)+ z(x)− z(x +1)

есть сумма целого числа $z(x)− z(x+ 1)$ и функции от $x,$ стремящейся к $0$ при возрастании $x.$ Отсюда получаем, что число $ρ$ целое. Аналогичное рассуждение верно и для других вариантов, и во всех случаях получаем, что $2ρ$ — целое число. Тогда целочисленные выражения $2z(x)± 2ρx,$ имеющие предел, должны быть постоянными при больших $x.$ Таким образом, хотя бы одно из равенств $z(x)=ρx+ 𝜃0$ , $z(x)= −ρx+ Θ$ имеет место при бесконечно многих $x$ (отметим, что из этого следует целочисленность $𝜃0$ или соответственно $Θ$ ). Значит, либо многочлен $P(ρx+ 𝜃0)− aP(x),$ либо многочлен $P (− ρx +Θ )− aP(x)$ имеет бесконечно много корней, следовательно, он тождественно равен $0.$ Применяя лемму, получаем, что $P (x)= α(x− x0)k,$ где $x0$ — рациональное число.

Для решения задачи заметим, что с точностью до множителя (не влияющего на существование целого $z,$ такого что $P(z)= aP (x)$ ), можно считать, что $P(x)= (px+ q)k,$ где $p> 0$ и $q$ — взаимно простые целые числа. Тогда равенство $(1)$ означает, что $pz+ q = ±a1∕k(px+ q),$ знак минус возможен при четном $k.$ Сразу ясно, что $a1∕k$ — рациональное число, т.е. $a$ — точная $k$ -я степень. Пусть $a =rk.$ Получаем $pz = ±r(px +q)− q,z = ±rx+ (±r− 1)q∕p.$ Итак, при $q = 0$ годится любое целое $r> 1,$ в противном случае при нечетных $k$ нужно, чтобы $r − 1$ было кратно $p,$ а при четных $k$ — чтобы $r±1$ было кратно $p.$

Ответ:

$1)P(x) ≡0$ и $a$ любое;

$k 2)P(x)= c(px+ q) ,$ где $k,p$ — натуральные числа, $c,q$ — целые, $c⁄= 0$ и $p$ и $q$ взаимно просты; для этого случая число $a$ должно быть больше $1$ и иметь вид $k a= r ,$ где $r≡ 1$ (mod $p$ ) при нечетных $k$ и $r ≡±1$ (mod $p$ ) при четных $k.$

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Предыдущий раздел

Следующий раздел