Дистанционная олимпиада 11кл. закончилась

Аватар пользователя
Ian
Сообщений: 686
Зарегистрирован: 18 янв 2016, 19:42

Дистанционная олимпиада 11кл. закончилась

Сообщение Ian » 15 мар 2021, 09:28

o.png
o.png (252.78 KiB) 1045 просмотра

Я не знаю только задачу 3. Возможно , и есть n, при котором раскладывается?

zykov
Сообщений: 1005
Зарегистрирован: 06 янв 2016, 17:41

Дистанционная олимпиада 11кл. закончилась

Сообщение zykov » 15 мар 2021, 18:08

Ian писал(а):Source of the post Я не знаю только задачу 3.

Поискал, какие есть критерии. Нашел Perron's irreducibility criterion.
Там же есть простое доказательство в три строчки.
Здесь он выполняется, т.к. $5 > 1+3$.

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

zykov
Сообщений: 1005
Зарегистрирован: 06 янв 2016, 17:41

Дистанционная олимпиада 11кл. закончилась

Сообщение zykov » 15 мар 2021, 18:12

Задача "2" смешная. :)

Аватар пользователя
Ian
Сообщений: 686
Зарегистрирован: 18 янв 2016, 19:42

Дистанционная олимпиада 11кл. закончилась

Сообщение Ian » 16 мар 2021, 08:15

zykov писал(а):Там же есть простое доказательство в три строчки.
Не так. В три строчки оно выводится из теоремы ТФКП о количестве нулей полинома в круге на комплексной плоскости (как его можно оценить по его коэффициентам, в россии обычно идут как безымянные следствия из теоремы Руше), она сложная и ей школьникам точно нельзя пользоваться, там доказательство совсем неэлементарно.
Но спасибо, хотя бы ответ знаем

zykov
Сообщений: 1005
Зарегистрирован: 06 янв 2016, 17:41

Дистанционная олимпиада 11кл. закончилась

Сообщение zykov » 16 мар 2021, 14:52

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

Может у них конечно вообще какой-то другой способо доказательства.
Или у них вообще ощибка (есть элементарное доказательство, но не верное).

zykov
Сообщений: 1005
Зарегистрирован: 06 янв 2016, 17:41

Дистанционная олимпиада 11кл. закончилась

Сообщение zykov » 16 мар 2021, 21:57

Ian писал(а):Source of the post оно выводится из теоремы ТФКП о количестве нулей полинома в круге на комплексной плоскости (как его можно оценить по его коэффициентам, в россии обычно идут как безымянные следствия из теоремы Руше)

Ну теорема Руше - для произвольных голоморфных функций, это конечно уже глубокий ТФКП - не для школьников. А следствие для многочленов, мне кажется, что это попроще и можно сделать элементарными средствами. (Обычно никто не делает, т.к. из общей теоремы всё легко видно.)

Для данной задачи, мне кажется, можно сделать элементарными методами (если ничего не напутал), но в том же ключе.
Правда получается несколько муторно и как-то не очень олимпиадно. Уж не знаю, это они имели ввиду или у них есть какое-то другое простое олимпиадное решение.


Сначала заметим, что этот многочлен для любого $n$ имеет действительный корень в диапазоне от -6 до -4 (с ростом $n$ стремится к -5).
Т.к. $f(-5)=3$, при чётных $n$ будет $f(-4)=3-4^{n-1} < 0$, при нечётных $n$ будет $f(-6)=3-6^{n-1} < 0$. Значит при чётных $n$ будет корень в $(-5,-4)$, при нечётных $n$ будет корень в $(-6,-5)$. Обозначим этот корень $a$ (зависит от $n$).
Тогда многочлен можно записать как
$$x^n+5 x^{n-1}+3 = x^n+5 x^{n-1}-a^n-5 a^{n-1} = (x-a)(x^{n-1}+(a+5)\frac{x^{n-1}-a^{n-1}}{x-a}) =$$
$$= (x-a)\left(x^{n-1}+(a+5)(x^{n-2}+x^{n-3}a+...+x a^{n-3}+a^{n-2})\right)$$

Нужно показать, что для комплексных $|x| \geq 1$ будет $|(a+5)(x^{n-2}+x^{n-3}a+...+x a^{n-3}+a^{n-2})| < |x^{n-1}|$.
Заметим что
$$|(a+5)(x^{n-2}+x^{n-3}a+...+x a^{n-3}+a^{n-2})| \leq |a+5|(|x|^{n-2}+|x|^{n-3}|a|+...+|x|\cdot |a|^{n-3}+|a|^{n-2})$$
Сначала докажем неравенство для $|x| = 1$, как трудный случай. Потом из этого докажем для любого $|x| > 1$.
Вторая часть довольно простая.
Если $k_i \geq 0$ и $k_1+k_2+...+k_n < 1$, то очевидно при $t > 1$ будет $k_1+k_2 t+k_3 t^2+...+k_n t^{n-1} < t^n$, т.к. каждая из этих степеней меньше $t^n$, а значит и их взвешенная сумма меньше, учитывая что сумма весов меньше 1.

Для первой части нужно доказать неравенство
$$|a+5|(1+|a|+...+|a|^{n-3}+|a|^{n-2}) = |a+5|\frac{|a|^{n-1}-1}{|a|-1} < 1$$
или, что тоже самое, $|a|-1 - |a+5|(|a|^{n-1}-1) > 0$.

При чётных $n$ будет $-a-1-(a+5)(-a^{n-1}-1)=a^n+5 a^{n-1}+4=1 > 0$.
При нечётных $n$ будет $-a-1+(a+5)(a^{n-1}-1)=a^n+5 a^{n-1}-2a-6=$
$=-2a-9>(-2)(-5)-9=1>0$.

Аватар пользователя
Ian
Сообщений: 686
Зарегистрирован: 18 янв 2016, 19:42

Дистанционная олимпиада 11кл. закончилась

Сообщение Ian » 18 мар 2021, 12:48

Здесь в олимпиаде есть и еще длинные решения, например 4-я
4o_copy.pdf
(65.25 KiB) Загружено 34 раз

zykov
Сообщений: 1005
Зарегистрирован: 06 янв 2016, 17:41

Дистанционная олимпиада 11кл. закончилась

Сообщение zykov » 18 мар 2021, 18:26

Ну оно не очень длинное.
Концептуально, тут сразу видно, что $$\frac{A}{B+C}+\frac{B}{A+C}+\frac{C}{B+A} \geq \frac32$$ для положительных чисел и равенство только когда все три равны. Это правда надо строго доказать. У них несколько длинно, может можно и покороче сделать (как-то через выпуклость).
(Вообще тут аналогично, что сумма квадратов экстремальна при всех числах равных друг другу, если сумма положительных чисел зафиксирована.)

zykov
Сообщений: 1005
Зарегистрирован: 06 янв 2016, 17:41

Дистанционная олимпиада 11кл. закончилась

Сообщение zykov » 18 мар 2021, 18:42

А солюшена для #3 там нет?
А то это решение для школьника как-то не очень. Не зная ТФКП трудно догадатся, что дело в том, то все корни кроме одного внутри единичного круга. А потом ещё нужно соорудить технически непростое решение.
Кроме того в моём решении используется Основная теорема алгебры.
Вроде школьники её знают, правда без доказательства (школьными методами там не доказать).

Аватар пользователя
Ian
Сообщений: 686
Зарегистрирован: 18 янв 2016, 19:42

Дистанционная олимпиада 11кл. закончилась

Сообщение Ian » 18 мар 2021, 21:31

zykov писал(а):Концептуально, тут сразу видно, что $$\frac{A}{B+C}+\frac{B}{A+C}+\frac{C}{B+A} \geq \frac32$$ для положительных чисел и равенство только когда все три равны. Это правда надо строго доказать. У них несколько длинно, может можно и покороче сделать (как-то через выпуклость).
(Вообще тут аналогично, что сумма квадратов экстремальна при всех числах равных друг другу, если сумма положительных чисел зафиксирована.)
Про выпуклость. Пусть [math] выпуклая функция на (0,M). Тогда
[math]. Но это никак к школьной программе не привязать.
Более элементарно [math], тогда остается доказать [math] а это очевидно из неравенства Коши.Но это уже которое по счету введение новых букв, рука не поднялась (и буквы кончились)

peregoudov
Сообщений: 523
Зарегистрирован: 29 дек 2015, 13:17

Дистанционная олимпиада 11кл. закончилась

Сообщение peregoudov » 19 мар 2021, 20:01

А нельзя в третьей задаче совсем в другую сторону подумать: рассмотреть значения функции в целых точках и что-то с разложением на множители или с признаками делимости использовать?

zykov
Сообщений: 1005
Зарегистрирован: 06 янв 2016, 17:41

Дистанционная олимпиада 11кл. закончилась

Сообщение zykov » 19 мар 2021, 20:22

peregoudov писал(а):Source of the post рассмотреть значения функции в целых точках и что-то с разложением на множители или с признаками делимости использовать

Если можно, то было бы любопытно взглянуть.

Вообще там есть разные критерии.
В частности утверждаетя:
The irreducibility of a polynomial over the integers $\mathbb {Z}$ is related to that over the field $\mathbb {F} _{p}$ of $p$ elements (for a prime $p$). In particular, if a univariate polynomial $f$ over $\mathbb {Z}$ is irreducible over $\mathbb {F} _{p}$ for some prime $p$ that does not divide the leading coefficient of $f$ (the coefficient of the highest power of the variable), then $f$ is irreducible over $\mathbb {Z}$.

Как применить к этой задаче - не знаю...

Аватар пользователя
Ian
Сообщений: 686
Зарегистрирован: 18 янв 2016, 19:42

Дистанционная олимпиада 11кл. закончилась

Сообщение Ian » 20 мар 2021, 08:05

Установление неприводимости многочлена над конечным полем [math] , p-простое, является сложной задачей, трудами поколений составлены таблицы таких неприводимых многочленов. Интересно, что для любого n и простого p существует хоть один неприводимый многочлен степени n над [math]. Но нам -то надо для каждого n указать p, что многочлен такого вида неприводим.
Если бы я сам придумывал школьникам задачу об этом, то что-нибудь типа для n=13 существует удачное разложение, а для меньших n нет. Простейшая задача такого класса про многочлен [math](при n кратном 4 -раскладывается)


Вернуться в «Математика»

Кто сейчас на форуме

Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 8 гостей