Тема Многочлены

Симметрические многочлены

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

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

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

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

Подтемы раздела многочлены

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

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

Задача 1#84255

Пусть $p =4k+ 3$ — простое число, а $m- n$ — такая несократимая дробь, что

--1-- --1-- ----1---- m- 02+ 1 + 12+ 1 + ...+ (p− 1)2+ 1 = n

Докажите, что $2m − n$ делится на $p.$

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

Первое решение. Введём обозначение $a =i2+ 1 i$ , для $i=0,...,p− 1$ . Тогда рассматриваемое нами выражение равно

m- σp−1(a0,a1,...,ap−1) n = σp(a0,a1,...,ap−1)

где $σi$ — основной симметрический многочлен степени $i$ . Найдём многочлен, корнями которого являются $ai$ , т. е.

p∏−1(x − 1− i2) i=0

Сделав замену $x− 1= t2$ , получим многочлен

p−1 p−1 p− 1 ∏ (t2− i2)= ∏ (t− i)∏ (t+i)≡ (tp− t)(tp − t)= t2p− 2tp+1+ t2. i=0 i=0 i=0

Теперь, сделав обратную замену, для $p= 4k+ 3$ получаем

p−1 ( ) ∏ (x− 1− i2)≡ (x− 1)p− 2(x− 1)p+1∕2+(x− 1)= xp +...+ p+ 2⋅ p+-1 +1 x − 4. i=0 2

По теореме Виета

σp ≡ 4(modp), σp−1 ≡2(modp),

поэтому $. (2σp− 1− σp)..p$ , и, поскольку $σp$ не кратно $p$ , сокращение произойдёт на число, взаимно простое с $p$ , т. е. $. (2m− n)..p$ . _______________________________________________________________________________________

Второе решение. Рассмотрим дроби вида $x12+1-$ , входящие в нашу сумму, как дроби по модулю $p$ (значением дроби $uv$ по модулю $p$ , где $v ⁄≡ 0(modp)$ , считается решение сравнения $vt ≡u(modp)$ ; при сложении обыкновенных дробей со знаменателями, не кратными $p$ , соответствующие им дроби по модулю также складываются).

Как известно, все числа от 2 до $p− 2$ можно разбить на пары $(x,y)$ в которых $xy ≡ 1(modp)$ . Сложим члены, соответствующие числам $x$ и $y$ которые составляют такую пару:

-1---+ -1---= --x2+-y2+-2---≡1(modp) x2+1 y2 +1 x2y2+ x2+ y2 +1

(так как $2 2 x y ≡ 1(modp)$ ). Складывая $p−3 2$ таких сумм и оставшиеся три слагаемых, получаем, что искомая сумма сравнима по модулю $p$ с $p+1 2 ,$ что и требовалось доказать.

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

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

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

Задача 2#96501

Соотношения Ньютона. Обозначим через $p (x,x ,...,x )= ∑nxk. k 1 2 n i=1 i$ Докажите, что

(a) $k−1 k pk− pk−1σ1+ pk−2σ2+ ...+ (− 1) p1σk−1+ (− 1)kσk$ $= 0$ при $1≤ k≤ n;$

(b) $n−1 n pk− pk−1σ1+ pk−2σ2+ ...+ (− 1) pk− n+1σn−1+ (−1)pk−nσn$ $= 0$ при $k >n.$

(c) Пусть $p$ — нечётное простое. Про целые числа $a1,a2,...,ap$ известно, что $k k k a1 + a2 + ...+ ap$ делится на $p$ при любом натуральном $k.$ Докажите, что все $ai$ попарно сравнимы по модулю $p.$

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

По определению,

∏k ∑k (t− xi)= (−1)k−iσk−iti i=1 i=0

следовательно, при $t= x j$ имеем

∑k 0= (−1)k− iσk−ixji i=0

для произвольного натурального $1≥ j ≥k.$ Суммируя по всем $j,$ получаем

∑k 0= (−1)kkσk+ (−1)k−iσk−ipi i=1

Таким образом, мы показали, что уравнение обращается в верное при $n= k.$

(a) При $n< k$ тождество очевидным образом получается из присваивания

x = x = ⋅⋅⋅= x = 0 n+1 n+2 k

в тождестве для $n =k.$

(b) Пусть теперь $n= k+ 1.$ Обозначим через $f(x1,...,xn)$ и $g(x1,...,xn)$ соответственно левую и правую части тождества. Из выполнения тождества при $n =k$ следует, что

f(0,x2,...,xk,xk+1)= g(0,x2,...,xk,xk+1) f(x1,0,...,xk,xk+1)= g(x1,0,...,xk,xk+1) ... f(x1,x2,...,0,xk+1)= g(x1,x2,...,0,xk+1) f(x1,x2,...,xk,0)= g(x1,x2,...,xk,0)

Однако из этого следует, что разность $f − g$ представима в виде $h(x1,...,xn)xi$ для любого $i$ (если бы не была, то при каких-то $x1,...,xi−1,xi+1,...,xk+1$ разность была бы ненулевой и одно из равенств, обозначенных выше, не выполнялось бы). Следовательно, разность $f − g$ представима в виде $h(x1,...,xn)x1x2...xkxk+1,$ однако это невозможно так как полная степень и $f$ и $g$ равна $k.$ Аналогичные рассуждения для $n >k +1$ дают индукционный переход и доказывают тождества для произвольного $n.$

(c) Покажем, что все элементарные симметрические многочлены, кроме, быть может произведения, делятся на $p$ как целые числа. Доказательство проведем по индукции. База для $σ1$ верна по условию. Переход будет следовать из предыдущих пунктов.

Рассмотрим многочлен $(x− a1)...(x− ap)$ над $𝔽p.$ Из только, что доказанного следует, что все его коэффициенты равны $0$ по модулю $p,$ кроме, быть может, свободного члена, откуда следует, что все его корни совпадают, то есть мы получили, что $a1,...,ap$ дают одинаковые остатки при делении на $p,$ что и требовалось доказать.

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

Задача 3#68880

Пусть $a,b,c$ — взаимно простые в совокупности натуральные числа, и

( 2 2 2 n n n) Dn = a+ b+ c,a + b+ c ,a + b + c

Найдите все возможные значения $D , n$ где $n−$ натуральное число, кратное 3. Запись $(a,a ,a,...,a ) 1 2 3 k$ обозначает наибольший общий делитель целых чисел $a ,a,a ,...,a . 1 2 3 k$ Целые числа $a ,a,a ,...,a 1 2 3 k$ называются взаимно простыми в совокупности, если $(a ,a,a ,...,a )= 1. 1 2 3 k$

Источники: Иннополис-2023 (см. dovuz.innopolis.university)

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

Пусть $σ,σ ,σ 1 2 3$ — элементарные симметрические многочлены и $n n n sn = a + b + c.$ Воспользуемся формулой Ньютона

sk = σ1sk−1− σ2sk−2+ σ3sk−3

Докажем, что $D ∈ {1,2,3,6}. n$ Предположим, что существуют такие взаимно простые в совокупности $a,b,c$ , что $D n$ отличен от $1,2,3,6.$ Докажем, что тогда $σ ,σ,σ 1 2 3$ имеют общий делитель, больший 1. В самом деле, из формул Ньютона следует, что при разложении $s n$ через $σ ,σ ,σ 1 2 3$ моном, не содержащий $σ 1$ и $σ, 2$ с точностью до знака имеет вид $3σ n3. 3$ Поэтому если $D n$ делит $s = σ 1 1$ и $D n$ делит $2 s2 = σ1 − 2σ2,$ то $Dn$ делит $σ1,2σ2,3σ3.$

При $Dn,$ отличном от $1,2,3,6$ у чисел $σ1,σ2,σ3$ есть общий делитель, больший 1. Пусть $p$ — простой множитель, входящий в этот делитель. Тогда $p$ делит $abc,$ откуда (без ограничения общности) $p$ делит a. Но тогда $p$ делит $(ab+ bc+ ca)$ и $p$ делит $bc,$ т.е. (без ограничения общности) $p$ делит $b.$ Наконец, из того, что $p$ делит $(a+b+ c),$ получаем, что $p$ делит $c.$ Значит, $(a,b,c)≥ p,$ но по условию $(a,b,c)= 1$ — противоречие.

Итак, $Dn ∈ {1,2,3,6}.$ Набор $(1,1,2)$ реализует $Dn = 2,$ набор $(1,1,1)$ — $Dn = 3,$ набор $(1,4,7)$ — $Dn = 6.$ Для $Dn = 1$ возьмем простое число $p >3$ и положим $a =b =1, c =p− 2.$ Тогда $a+ b+c =p$ и $p$ не делит $2 2 2 2 a +b + c =p − 4p+ 6,$ откуда $Dn = 1.$

Ответ:

${1,2,3,6}$

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

Задача 4#71961

Зафиксируем 10 натуральных чисел $n ,n ,...,n 1 2 10$ и обозначим через $n$ их сумму $n= n + ⋅⋅⋅+ 1$ $n . 10$ Предположим теперь, что на доске в строчку записаны $n$ чисел $a1,...,an,$ каждое из которых равно либо 0, либо 1. Эти числа (в том порядке как они записаны) разбивают на 10 групп:

a◟1,..◝.,◜an1◞,a◟n1+1,..◝.◜,an1+n2◞,...,a◟n1+⋅⋅⋅n9◝+◜1,...,an◞ n1 n2 n10

Группу назовем ненулевой, если в ней содержится хотя бы одна 1. В результате разбиения, в зависимости от того какие числа $a,...,a 1 n$ были взяты изначально, можно получить то или иное число ненулевых групп. Нас будут интересовать такие наборы $a ,...,a , 1 n$ которые при указанном разбиении дают четное число ненулевых групп. Докажите, что число таких наборов $a1,...,an$ (где ненулевых групп будет четно) находится по формуле:

n−1 1 n n n 2 +2 ⋅(2 1 − 2)⋅(2 2 − 2)⋅...⋅(210 − 2)

Источники: Межвед-2022, 11.6 (см. www.academy.fsb.ru)

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

Искомое число наборов посчитаем, суммируя количество наборов с заданным числом $k$ ненулевых групп:

При $k= 0$ такой набор единственный;
При $k= 2$ их $∑ ni nj 1≤i<j≤10(2 − 1)⋅(2 − 1);$
При $k= 4$ уже $∑ ni nj nl ns 1≤i<j<l<s≤10(2 − 1)⋅(2 − 1)⋅(2 − 1)⋅(2 − 1);$
$...$
При $k= 10$ в итоге $(2n1 − 1)⋅(2n2 − 1)⋅...⋅(2n10 − 1).$

Определим многочлены

σ (x ,...,x )= 1 0 1 10

σk(x1,...,x10)= ∑ xi⋅...⋅xi ,1 ≤k ≤10 1≤i1<⋅⋅⋅<ik≤10 1 k

Как известно из правила раскрытия скобок, такая сумма всевозможных многочленов это сумма по всем наборам и она равна

∑ 0≤k≤10σk(x1,...,x10)= (x1+1)⋅...⋅(x10+ 1),

Если мы сложим эту сумму с суммой таких же многочленов от отрицательных аргументов, то многочлены с нечётными индексами взаимноуничтожатся:

∑ σk(x1,...,x10)+ ∑ σk (−x1,...,−x10) = 0≤k≤10 0≤k≤10

∑ = 2 . σk (x1,...,x10) 0≤k≤10,k..2

Используем полученные результаты:

∑ n n 2N = 2 ..σk (2 1 − 1,...,2 10 − 1)= 0≤k≤10,k .2

n1 n10 n1 n10 =(2 − 1 +1)⋅...⋅(2 − 1+1)+ (− (2 − 1)+1)⋅...⋅((−2 − 1)+ 1)

2N =2n1+...+n10 + (−2n1 + 2)⋅...⋅(−2n10 + 2)

что и требовалось:

N =2n−1+ 1⋅(2n1 − 2)⋅...⋅(2n10 − 2) 2

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

Задача 5#86846

Пусть $a+ b+ c= 0,a2+ b2 +c2 = 1.$ Найдите $a4 +b4+ c4.$

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

Заметим, что $ab+bc+ ac = (a+b+c)2−a2−b2−c2-= − 1. 2 2$ Значит

4 4 4 2 2 2 2 22 22 2 2 a + b +c = (a +b + c) − 2(a b +b c +c a)=

2 2 2 2 2 = (a +b + c) − 2((ab+bc+ ac) − 2(abc(a+ b+c)))=

= (a2 +b2+ c2)2− 2(ab+bc+ ac)2+ 4abc(a+b+ c)= 1− 1+ 0= 1 2 2

Ответ:

$1 2$

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

Задача 6#86847

Выразите $a4+ b4+ c4$ через элементарные симметрические многочлены.

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

Воспользуемся следующим тождеством:

4 4 4 2 2 2 2 2 a + b+ c = (a + b +c ) − 2(ab+bc+ ac) + 4abc(a +b+ c)=

2 2 2 = ((a+ b+ c) − 2(ab+ bc+ac)) − 2(ab+ bc +ac) +4abc(a+ b+c)

Осталось обозначить симметрические многочлены и получится ответ.

Ответ:

$a4+ b4+c4 = σ4− 4σ2σ + 2σ2+ 4σ σ 1 1 2 2 1 3$

Курсы

Всё необходимое для достижения цели

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

Задача 7#86848

Про целые числа $a,b,c$ известно, что $a +b+ c= 0.$ Докажите, что число $2a4+ 2b4+ 2c4$ является квадратом целого числа.

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

Мы знаем, что сумма четвёртых степеней $a,b$ и $c$ записывается следующим образом:

4 4 4 4 2 2 a +b + c =σ1 − 4σ1σ2+2σ2 + 4σ1σ3

Так как $σ1 = 0,$ то получаем, что $2a4+2b4+ 2c4 =4σ2. 2$

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

Задача 8#86849

Докажите, что произведение всех чисел вида $± √1± √2± ...± √10$ является

(a) целым числом;

(b) квадратом.

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

(a) Рассмотрим многочлен $P(x)=(x2− 1)(x2− 2)...(x2− 10).$ Из теоремы Виета следует, что любой элементарный симметрический многочлен от корней этого многочлена принимает целое значение, так все коэффициенты многочлена $P$ целые. Но так как произведение чисел вида $√- √- √-- ± 1± 2 ±...± 10$ это симметрический многочлен, то и его значение тоже целое.

(b) Разобьем все числа на пары противоположных: $√ - √ -- 1± 2± ...± 10$ и $√ - √ -- − 1 ∓ 2∓...∓ 10.$ Так как пар чётное количество, в каждой паре числа равны по модулю и разных знаков, то достаточно показать, что произведение чисел вида $√- √-- 1± 2 ±...± 10$ является целым. А это можно показать аналогично пункту (a), рассмотрев многочлен $2 2 P = (x − 1)(x − 2)...(x − 10).$

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

Задача 9#86852

Докажите, что у многочлена $P (x ,x,...,x )= ∏ (x − x ) 1 2 n 1≤i<j≤n i j$ все коэффициенты равны $+ 1,− 1$ или $0.$

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

Докажем, что определитель Вандермонда равен с точностью до знака определителю матрицы на рисунке ниже. Легко видеть, что определитель данной матрицы является кососимметрическим многочленом относительно $x1,...,xn$ по свойству определителя (так как определитель матрицы с двумя равными строчками равен $0$ ). Тогда определитель делится на определитель Вандермонда. С другой стороны степени этих однородных многочленов равны, а также равны с точностью до знака коэффициенты при $n− 1n−2 0 x1 x2 ...xn.$ То есть определитель Вандермонда равен определителю матрицы на рисунке с точностью до знака. Но по формуле определителя легко видеть, что каждое слагаемое действительно будет входить с коэффициентом $+1,−1$ или $0$ в данный многочлен. То есть мы получили требуемое.

$PIC$

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

Задача 10#88398

Докажите, что для каждого полинома $f(x)∈ Q[x]$ существует такой полином $g(x)∈ Q[x],$ что $g(x2016)$ делится на $f(x).$

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

Многочлен $f(x)$ степени $n$ имеет $n$ комплексных корней $x ,x ,...,x . 1 2 n$ Все симметрические многочлены от этих корней принимают рациональные значения, так как у $f$ все коэффициенты рациональные. Заметим, что многочлен $g(x)$ с корнями $2016 2016 2016 x1 ,x2 ,...,xn$ также имеет рациональные коэффициенты, так как каждый его коэффициент — симметрический многочлен от переменных $2016 2016 2016 x1 ,x2 ,...,xn ,$ который, в свою очередь, выражается через симметрические многочлены от переменных $x1,x2,...,xn.$ Тогда многочлен $2016 g(x )$ имеет корни $x1,x2,...,xn,$ а значит делится на $f(x),$ что и требовалось.

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

Задача 11#86850

Положительные числа $a,...,a ,k 1 n$ таковы, что $a + ...+ a = 3k,a2+ ...a2= 3k2 1 n 1 n$ и $a3+ ...+ a3> 1 n$ $3k3+k.$ Докажите, что какие-либо два из чисел $a1,...,an$ отличаются больше, чем на $1.$

Источники: Всеросс., 2012, ЗЭ, 9.4(см. olympiads.mccme.ru)

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

Перемножив равенство

a1+ a2+...+an =3k (1)

и неравенство

3 3 3 3 a1+ a2+ ...+an >3k + k

получим неравенство

4 4 4 3 3 3 3 3 3 4 2 a1+ a2+ ...+ an +a1a2+ a1a2+ a1a3+a1a3+ ...+an−1an+ an−1an > > 9k +3k (2)

Возведем теперь в квадрат равенство

a2+a2+ ...+ a2= 3k2 (3) 1 2 n

Получим

a41 +a42+ ...+ a4n+ 2a21a22+ 2a21a23+ ...+ 2a2n−1a2n = 9k4 (4)

Вычитая из неравенства $(2)$ равенство $(4),$ получаем

(a31a2− 2a21a22+ a1a32)+ ...+ (a3n−1an− 2a2n−1a2n +an−1a3n)> 3k2

или

$a1a2(a1− a2)2+a1a3(a1 − a3)2+...+an−1an(an−1 − an)2 > 3k2 (5).$

Предположим теперь, что любые два числа отличаются не больше, чем на $1.$ Тогда квадрат их разности не больше $1,$ и из $(5)$ получаем неравенство

a1a2+ a1a3+ ...+ an− 1an >3k2 (6)

Но, если вычесть из квадрата равенства $(1)$ равенство $(3),$ получится равенство

2a1a2+ 2a1a3 +...+ 2an−1an =6k2

что противоречит $(6).$ Значит, найдутся два числа, отличающиеся больше, чем на $1.$

Интенсивы

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

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

Задача 12#86851

Каждые два из действительных чисел $a,a ,a ,a,a 1 2 3 4 5$ отличаются не менее чем на $1.$ Оказалось, что для некоторого действительного $k$ выполнены равенства $a1+ a2+ a3 +a4+ a5 = 2k$ и $2 2 2 2 2 2 a1 +a2+ a3+a4+ a5 = 2k.$ Докажите, что $2 25 k ≥ 3 .$

Источники: Всеросс., 2012, ЗЭ, 10.3(см. olympiads.mccme.ru)

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

Без ограничения общности можно считать, что $a < ...< a . 1 5$ По условию, $a − a ≥ 1 i+1 i$ при всех $i= 1,2,3,4.$ Значит, $aj − ai ≥j− i$ при всех $1 ≤i< j ≤ 5.$ Возведём каждое из полученных неравенств в квадрат и сложим их все. Получим $∑ 2 ∑ 2 2 2 2 2 1≤i<j≤5(aj − ai) ≥ 1≤i<j≤5(j− i) =4 ⋅1 + 3⋅2 + 2⋅3 +4 = 50,$ то есть