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

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

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

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

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

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

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

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

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

Задача 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.$

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

Подсказка

Рассмотрите произведение множителей вида (t - x_i). Распишите их через сигмы. Как теперь можно проверять тождества?

Подсказка 1, пункт а

Присвойте x_(n+1) = x_n = …=x_k = 0, проверьте, аккуратно тождество.

Подсказка 1, пункт б

Попробуйте подставлять вместо переменных нули, после чего заметьте какие-нибудь тождества и докажите задачу по индукции.

Подсказка 1, пункт с

Докажите по индукции, что симметрические многочлены делятся на p, как целые числа. Как это может помочь при решении задачи?

Подсказка 2, пункт с

Рассмотрите многочлен (x-a_1)(x-a_2)…(x-a_p) над F_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

А давайте для начала попробуем ручками проверить различные a, b, c - чтобы понять, каким вообще может быть D.

Подсказка 2

Пупупу… а теперь посмотрим внимательно на условие. Каким свойством обладают скобки вида: (aⁿ + bⁿ + cⁿ)?

Подсказка 3

Да, эти скобки симметричны! Если поменять какие-то две переменные местами, то выражение не изменится. А теперь, учитывая, что мы получили какие-то значения D - попробуйте перейти к симметрическим многочленам. К какому противоречию мы придём?

Подсказка 4

Верно, мы придём к тому, что существует какое-то просто p, которое делит произведение abc. Теперь нужно аккуратно доказать, что в таком случае простое p делит каждое из чисел a, b, c! Тогда, мы докажем, что возможны только D = {1, 2, 3, 6}.

Подсказка 5

Остаётся только привести пример чисел a, b, c для каждого возможного D!

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

Пусть $σ,σ ,σ 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)

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

Подсказка 1

Нас просят найти количество наборов, подходящих под условие. То есть, нам нужно, чтобы количество не нулевых групп было четно. Но если оно четно, то оно равно 0, 2, …, 10. Значит, надо посчитать, сколько у нас вариантов для 0 групп, для 2 групп и так далее, и просуммировать. Давайте начнем с простого. Сколько у нас вариантов для 0 не нулевых групп? А для 2?

Подсказка 2

Для 0 все совсем ясно - это 1 вариант, так как подходит только 000…0. Для 2 - нам надо сначала выбрать номера групп, а потом для каждой из групп найти количество вариантов и перемножить. Как-будто просится «Цэшка», но ведь у нас количество вариантов при разных выборах номеров групп будет разным. Поэтому, нам надо суммировать по всем 1 <= i < j <= 10. А что конкретно нам надо суммировать? Сколько у нас будет вариантов выбора последовательности для группы n_i, к примеру?

Подсказка 3

Верно, нам будут подходить все варианты кроме того, когда в нашей группе стоят все нули. Поэтому для 2 групп у нас будет сумма по тому, что написано выше, величин (2^n_i - 1) * (2^n_j - 1). Меняется ли что-то при увеличении количества групп? Нет. Значит, нашли сколько всего вариантов, но пока это сумма. Значит, теперь нам надо доказать, что она сворачивается в то, что написано в условии. То есть, нам надо доказать, что сумма сумм равна некоторому выражению. А на что эти суммы похожи, если вспомнить формулу раскрытия скобок в выражении (x_1 + 1) * (x_2 + 1) * … (x_k + 1)?

Подсказка 4

Конечно, эти суммы очень напоминают формулу раскрытия скобок в выражении выше, при x_i = 2^n_i - 1. Но вот только в формуле раскрытия этого выражения участвуют как суммы с четным количеством множителей, так и с нечетным. А у нас только с четным. Как нам тогда это исправить? Что нужно сделать, чтобы у нас каким-то образом убрались, уничтожились нечетные слагаемые?

Подсказка 5

Нужно подставить в выражение уже -(2^n_i - 1). Тогда, сумма в подстановках с минусом и без, не будет содержать слагаемых с нечетным количеством множителей, так как они взаимоуничтожатся. Тогда, это значит, что нам осталось найти значения выражения в подстановке с минусом и с плюсом, и сложить их, после чего поделить на два, ведь все слагаемые с четным числом множителей будут дважды включаться в сумму. Производя эти действия, получим требуемое.

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

Искомое число наборов посчитаем, суммируя количество наборов с заданным числом $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,$ то есть