Тема ЮМШ (олимпиада Юношеской Математической Школы)

ЮМШ - задания по годам → .06 ЮМШ 2024

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

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

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

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

Подтемы раздела юмш (олимпиада юношеской математической школы)

Разделы подтемы ЮМШ - задания по годам

ЮМШ до 2020

ЮМШ 2020

ЮМШ 2021

ЮМШ 2022

ЮМШ 2023

ЮМШ 2024

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

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

Задача 1#83387

Цель этого сюжета — доказательство следующего утверждения:

Пусть $p$ — нечётное простое чисто. Докажите, что существует ровно $(p− 3)∕2$ упорядоченных четвёрок $(a,b,c,d)$ натуральных чисел, для которых $ab+ cd =p$ и $max(c,d)<min(a,b)$ .

Если $r$ — остаток по модулю $p$ , то назовём четвёрку ( $a,b,c,d$ ), удовлетворяющую условиям выше, $r$ -четверкой, если $c ≡ra$ (mod $p$ ).

1. Докажите, что если $r$ -четвёрка существует, то $r∈{2,3,...,p− 2}$ .

2. Докажите, что для данного $r$ существует не более одной $r$ -четвёрки.

3. Докажите, что если $r$ -четверка существует, то $(p − r)$ -четвёрки не существует.

4. Докажите, что для всякого $r∈{2,3,...,p− 2}$ существует либо $r$ -четвёрка, либо $(p − r)$ -четвёрка.

Источники: ЮМШ - 2024, сюжет 1 (см. yumsh.ru)

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

1. Пусть существует $r$ -четверка $(a,b,c,d)$ при $r= 1$ . Тогда $p=ab+ cd≡$ $≡ ab+ rad= a(b+d)$ (mod $p$ ). Получаем, что $. a(b+ d)..p$ . Тогда либо $a$ , либо $b+ d$ делится на $p$ . Тогда либо $a ≥p$ , $b+ d≥ p$ . В первом случаем получаем, что $ab+ cd≥ p+cd> 1$ . Во втором же $ab+cd≥ 2b+d ≥p +1$ . Получаем, что $1$ -четверки не существует.

Пусть существует $r$ -четверка $(a,b,c,d)$ при $r= p− 1$ . Тогда $p= ab+cd≡$ $≡ab+ rad =a(b− d)$ (mod $p$ ). Получаем, что $. a(b− d)..p$ . Тогда либо $a$ , либо $b− d$ делится на $p$ . Тогда либо $a≥ p$ , $b+ d≥ p$ ( $b− d ⁄=0$ , поскольку $b> d$ ). В первом случаем получаем, что $ab+ cd≥p +cd> 1$ . Во втором же $ab+cd≥ b+ d> b− d ≥p$ . Получаем, что $(p− 1)$ -четверки тоже не существует.

2. Пусть $(a,b,c,d)$ , $(a′,b′,c′,d′)$ — две четверки, удовлетворяющие условиям с одним и тем же $r$ . Тогда $ac′ ≡ara′ ≡ ca′$ (mod $p$ ), аналогично $bd′ ≡− rdd′ ≡ b′d$ (mod $p$ ). Т.е. $ac′− a′c$ , $bd′− b′d$ кратны $p$ .

Предположим, что эти разности одновременно не равны нулю. Пусть не умаляя общности $ac′− a′c> 0$ , тогда $ac′ >p >ab$ , т.е. $c′ > b$ и тем более $c′ > d$ . Отсюда получаем, что $|bd′− b′d|< max(bd′,b′d) <max(c′d′,b′c′)= b′c′ < a′b′ < p$ откуда (т.к. $|b′d− b′d|$ кратно $p$ ) получаем $bd′− b′d= 0$ — противоречие.

Пусть теперь одна из исходных разностей равна нулю (не умаляя общности $bd′− b′d$ ). Отметим, что из равенств $ab+ cd =p =a′b′+ c′d′$ следует взаимная простота $b$ и $d$ , $b′$ и $d′$ . Поэтому из равенства $bd′ = b′d$ следует, что $b= b′$ и $d =d′$ , а из него — $(a− a′)b= (c′− c)d$ . В силу взаимной простоты $b$ и $d$ имеем $a− a′ =dx$ , $c′− c =bx$ . При $x> 0$ это противоречит условию $c′ < b′ = b$ , при $x< 0$ — условию $c< b$ . Значит $x =0$ , $a =a′$ , $c= c′$ — четверки полностью совпадают.

3. Пусть $(a,b,c,d)$ , $(a′,b′,c′,d′)$ — две четверки, удовлетворяющие условиям с $r$ и c $r′ = p− r$ соответственно. Тогда $ac′ ≡− ara′ ≡ −ca′$ (mod $p$ ), аналогично $bd′ ≡ −rdd′ ≡−b′d$ (mod $p$ ). Т.е. $ac′+a′c$ , $bd′+b′d$ кратны $p$ .

Пусть $c′ ≥ b$ , а значит $c′ > c,d$ , тогда, аналогично прошлому пункту, $bd′+b′d< c′d′+b′c′ < c′d′+b′a′ = p$ — противоречие с делимостью на $p$ . Значит $c′ < b$ и, аналогично $c< b′$ , $d′ < a$ , $d< a′$ . Тогда $a′c+ac′ <ab+ a′b′ < 2p$ , поэтому из делимости $ac′+a′c= p$ и аналогично $b′d+bd′ = p$ .

Предположим теперь, не умаляя общности, что $a$ — наибольшее из чисел. Вычитая из $ab+cd$ равное ему $ac′+ ca′$ , получаем $a(b− c′)=c(a′− d)$ , откуда из взаимной простоты $a$ и $c$ получаем, что $a′− d$ делится на $a$ — противоречие с тем, что $a< a′$ , $a′− d> 0$ .

4. Рассмотрим на плоскости множество всех векторов $(x,y)$ с целыми координатами $x,y$ такими, что $y ≡ rx$ (mod $p$ ) или $y ≡(p− r)x$ . Отметим, что это множество вместе с каждым вектором $(x,y)$ содержит также и $(±x,±y)$ . Рассмотрим в нашем множестве вектор с минимальной суммой координат. В силу замечания выше можно считать, что вектор $u:= (a,c)$ , где $a,c>0$ , $a ⁄=c$ (на осях координат и на биссектрисах углов между ними такой вектор лежать не может, поскольку $2≤ r≤p − 1$ ), если $c ≡(p− r)a$ (mod $p$ ), то переобозначим $r$ и $p− r$ . Предположим пока, что $a> c$ . Рассмотрим прямую $ℓ$ с уравнением $xc− ya= p$ . Будем искать точку $(d,−b)$ на этой прямой такую, что $d> 0,d <a,d< b,c <b$ — тогда четверка $(a,b,c,d)$ и будет искомой. Заметим, что если $(x,y)∈ℓ$ , то $(x− a,y − c)∈ℓ$ .

Прямая $ℓ$ где-то пересекает прямую $y+ x= 0$ . Пусть точка $(x0,y0)∈ ℓ$ с целыми $x0,y0$ лежит выше прямой $y+ x= 0$ , а точка $v0 :=(x0− a,y0− c)$ — (нестрого) ниже.

Во-первых, проверим, что $x0− a >0$ . В самом деле, в противном случае $x0 ≤ a$ . Из выбора вектора $u$ имеем $a+ c≤ |x0− a|+|y0− c|= a− x0 +|y0 +c|$ . Если $c≥y0$ , то $a− x0+ |y0− c|= a+ c− x0− y0 < a+ c$ — противоречие. Если же $y0 >c$ , то $p =x0c− y0a <ac− ac= 0$ — снова противоречие.

Итак, $x0− a> 0$ . Поскольку $(x0− a)+ (y0− c)≤ 0$ , имеем $y0 − c< 0$ . Если $y0 ≥ 0$ , то $0< x0− a ≤c− y0 ≤ c$ и обе координаты вектора $v0$ по модулю не больше, чем $c$ — это опять противоречит выбору $u$ . Значит, $y0 < 0$ и $c− y0 > c$ . Теперь выберем наибольшее целое неотрицательное $m$ , при котором $x0− a− ma≥ 0$ . Ясно, что это неотрицательное значение строго меньше, чем $a$ . Тогда вектор $v0− mu =(x0− a− ma, y0− c− mc)$ и есть искомый вектор. Действительно, все нужные неравенства уже установлены, осталось только исключить случай $x0 − a− ma =0$ , но в таком случае из уравнения прямой $ℓ$ получаем $xc− ya= p$ , $− (y0− c− mc)a =p$ , что невозможно в силу того, что $a> c> 0$ , $− y0+c +mc ≥1 +c+ mc≥ 2$ .

Наконец обратимся к случаю $c> a$ . В этом случае обозначим $a′ =c$ , $c′ = a$ и построим точно так же четверку $(a′,b′,c′,d′)$ со всеми нужными свойствами, но такую, что, наоборот $a′ ≡rc′$ (mod $p$ ). В этом случае, очевидно, $(b′,a′,d′,c′)$ будет $p − r$ -четверкой, что нам подходит.

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

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

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

Задача 2#83388

Дан граф $G =(V,E)$ на $n$ вершинах: сопоставим каждой вершине $v$ переменную $x v$ . Пусть $T$ — множество остовных деревьев графа $G$ (то есть поддеревьев, содержащих все вершины). Рассмотрим остовный многочлен от $n$ переменных $x1,...,xn$

∑ ∏ deg v−1 PG(x1,x2,...,xn)= xv S . S∈Tv∈V

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

1. Найдите $PK4(1,2,3,4)$ , где $K4$ — полный граф на 4 вершинах.

2. Докажите, что цикл на пяти вершинах является плохим графом.

3. Пусть $G$ — хороший граф, $U$ — некоторое подмножество его вершин. Граф $H$ состоит из всех вершин, лежащих в $U$ , и всех ребер графа $G$ , соединяющих эти вершины. Докажите, что граф $H$ тоже хороший.

4. Назовём раздвоением вершины $v$ операцию, добавляющую в граф вершину $v′$ , соединенную ровно с теми же вершинами, что и $v$ . Докажите, что граф, получающийся из одной вершины операциями добавления висячей вершины, раздвоения вершины с добавлением ребра $′ vv$ и раздвоения вершины без добавления ребра $′ vv$ , является хорошим.

Источники: ЮМШ - 2024, сюжет 2 (см. yumsh.ru)

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

1. В полном графе на четырех вершинах есть только 2 вида остовных деревьев: 1) цепь длины 4; 2) три вершины, "висящие"на четвертой.

Каждое дерево первого вида даст в остовный многочлен одночлен $xixj$ , $i⁄= j$ , причем каждый одночлен будет представлен 2 раза.

Каждое дерево второго вида даст в остовный многочлен одночлен $x2i$ , где $i$ — "вершина"остова.

В итоге получим многочлен:

$pict$

2. Распишем $PC = x1x2x3+ x2x3x4+ x3x4x5+ x4x5x1+ x5x1x2 5$ . Поскольку многочлен $PC 5$ линеен по каждой переменной, получаем, что каждая из переменных живет только в одной из скобок. Тогда переменные вынуждены разбиться на скобки 2-2-1 или 3-1-1, что дает нам не более четырех мономчиков, противоречие.

3. Давайте сначала заметим, что можно последовательно выкидывать вершины по одной с сохранением связности, если $U$ связно. (Если несвязно, то просто 0 получится и все).

Для этого нужно подвесить за $U$ и поочередно удалять вершины с самого нижнего уровня. Теперь нужно понять, что при удалении только одной вершины $v$ граф остается хорошим. Для этого подставим 0 в $xv$ . Получим, что все слагаемые, в которые $xv$ входило в хотя бы первой степени, обнулились, а значит остались в точности те, где $v$ — висячая вершина. А все такие деревья устроены так: выбрано дерево в графе $G∖v$ , и потом одна из вершин из окрестности $v$ соединена с $v$ . Тогда многочлен после подстановки нуля равен $∑ PG∖v(x1,...,xn)⋅( u∈N(v)xu)$ . Подстановка нуля сохраняет раскладываемость на множители, значит $PG∖v$ тоже раскладываемый, значит, при удалении вершины $v$ граф останется хорошим.

4. Сначала докажем вспомогательный факт про такой тип графов.

Лемма о раздвоении без добавления ребра. Пусть дан граф $G$ на $n$ вершинах. Рассмотрим граф $G1$ , полученный из $G$ добавлением вершины $vn+1$ и соединением ее со всеми вершинами из $NG(vn)$ , но не самой $vn$ . Тогда

( ∑ ) PG1(x1,x2,...,xn+1)= PG(x1,...,xn+ xn+1)( xv). v∈NG(vn)

Доказательство. Давайте заметим, что любое дерево в графе $G$ устройство следующим образом — на всех вершинах, кроме $v n$ , берется некоторый лес, такой, что в каждой компоненте есть хотя бы одна вершина из $N (v ) G n$ , и потом вершина $v n$ соединяется с ровно одной вершиной из каждой компоненты. Обозначим за $L$ множество всех таких лесов, за $t(K)$ — число компонент связности в лесу $K$ , и назовем $A1,A2,...At$ пересечения множеств $NG (v)$ с компонентами связности леса $K$ . Тогда из рассуждений выше

∑ ( ∏ t(∏K)( ∑ ) ) PG(x1,x2,...,xn) = ( xdvegK(v)−1 ( xv) xtn(K)−1). K ∈L v∈V|v⁄=vn i=1 v∈Ai

Теперь давайте поймём, как устроены деревья в $G1$ . Там мы тоже берём лес, который содержит все вершины, кроме $vn$ , $vn+1$ , и такой, что каждая его компонента содержит хотя бы одну вершину из $NG(vn)$ , после чего одна из долей соединяется с обеими вершинами из $vn$ и $vn+1$ , а каждая из остальных $t(K)− 1$ долей — с ровно одной из этих вершин. Тогда в тех же обозначениях получается, что

$pict$

Теперь очевидно, что второй сомножитель равен $PG(x1,x2,...,xn+ xn+1)$ , и лемма доказана. ________________________

Пусть $G 1$ - граф из леммы 1. Мы в лемме 1 уже выяснили как устроены деревья в графе $G$ , поэтому нужно разобраться с тем, как они устроены в $G 2$ . Заметим, что они устроены так: мы снова берем лес с такими же условиями, а дальше делаем одно из двух - либо не проводим ребро между $vn$ и $vn+1$ , и это слагаемое такое же как в $G1$ , либо проводим, и тогда каждую из долей соединяем с ровно одной из этих вершин. Стало быть, сумма всех первых слагаемых даст нам $PG1$ , а сумма вторых равна

$pict$

Тогда получается, что

$pict$

доказали требуемое.

Ответ:

1. $(x1+ x2 +x3+ x4)2$

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

Задача 3#83389

Будем называть треугольник $DEF$ вписанным в треугольник $ABC$ , если точки $D$ , $E$ , $F$ находятся на сторонах $BC$ , $AC$ , $AB$ соответственно.

1. Докажите, что если отрезок $EF$ параллелен отрезку $BC$ , то описанные окружности треугольников $AEF$ и $ABD$ пересекаются на прямой $DE$ .

2. Оказалось, что $CE = DE$ , $BF =DF$ . Докажите, что точка, симметричная $D$ относительно $EF$ , лежит на пересечении описанных окружностей треугольников $ABC$ и $AEF$ .

3. Пусть $∠BAC =∠DEF = ∠DFE$ . Средняя линия треугольника $DEF$ , параллельная $EF$ , пересекает $AB$ и $AC$ в точках $X$ и $Y$ соответственно. Докажите, что точка $A$ , $D$ , $X$ , $Y$ лежат на одной окружности.

4. В треугольник $DEF$ вписан треугольник $XY Z$ , гомотетичный треугольнику $ABC$ . Докажите, что описанная окружность треугольника $DEF$ касается описанной окружности $ABC$ тогда и только тогда, когда касается описанной окружности $XY Z$ .

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

1. Пусть $G$ — вторая точка пересечения описанных окружностей $AEF$ и $ABD$ . Поскольку четырехугольник $AFEG$ описанный, то $∠AF E =$ $= 180∘− ∠AGE$ . Четырехугольник $ABDE$ также описанный, значит $∠ABD = 180∘− ∠AGD$ .

$PIC$

Поскольку $EF ∥BC$ , то $∠AF E = ∠ABD$ .

Получаем, что $∠AGE = ∠AGD$ . Тогда $G$ , $E$ , $D$ лежат на одной прямой.

2. Поскольку треугольники $BED$ и $DFC$ равнобедренные, то $∠EBD =∠EDB$ и $∠FCD = ∠FDC$ . Тогда

∠EDF = 180∘− ∠BDE − ∠FDC =180∘− ∠B − ∠C =∠BAC

Также из определения $D′$ (точка, симметричная $D$ относительно $EF$ ) следует, что

′ ∠ED F =∠EDF =∠BAC

Получается, что $D ′$ лежит на описанной окружности $AEF$ .

$PIC$

Из определения $′ D$ как симметричной точки:

ED = ED′ = EB и D′F = FD = FC

Значит, $B,D$ и $D′$ лежат на одной окружности с центром в $E,$ а $C,D$ и $D ′$ с центром в $F.$ Тогда выполнены следующие равенства для вписанных и центральных углов:

′ 1 ′ 1 ′ ′ ∠EBD = 2∠AED = 2∠AFD =∠ACD

Получаем, что $′ D$ лежит и на описанной окружности $ABC$ .

3. Обозначим за $S$ и $T$ середины $DF$ и $DE$ соответственно. Т.к. $∠SFE = ∠FAE = ∠FET$ , то $SF$ и $TE$ — касательные к окружности, описанной около $AF E$ .

$PIC$

Рассмотрим пару окружностей: описанная окружность треугольника $AFE$ и окружность нулевого радиуса с центром в точке $D$ . Рассмотрим степени точек $S$ и $T$ относительно данных окружностей:

pow(AFE )(S)= SF2 = SD2 =powD(S)

2 2 pow(AFE)(T)= TE = TD = powD (T)

Получаем, что $ST$ — радикальная ось наших 2 окружностей. Тогда на этой же радикальной оси лежат $X$ и $Y$ . Тогда $2 XA ⋅XF = XD$ и $2 YA⋅Y E = YD .$ Следовательно, $XD$ — касательная к описанной окружности $AFD$ , и $YD$ — касательная к описанной окружности $AFD$ . Тогда

∠XAD = ∠XDF, ∠YAD = ∠YDE

∠XDF + ∠YDE =∠BAC

∘ ∘ ∠XDY + ∠XAY =∠XAY +∠XAY +180 − ∠DFE − ∠DEF = 180

В итоге $XAY D$ — вписанный.

4. Окружность $(DEF )$ повторно пересекает стороны $BC$ , $AC$ , $AB$ в точках $′ D$ , $′ E$ , $′ F$ соответственно. Окружность $(XY Z)$ повторно пересекает стороны $EF$ , $DF$ , $DE$ в точках $′ X$ , $′ Y$ , $′ Z$ соответственно.

Окружности $′ ′ (EX Z )$ и $′ ′ (F X Y)$ повторно пересекаются в точке $M$ . Заметим, что

∠Y′MZ ′ = ∠DEF + ∠DFE = π− ∠EDF,

поэтому $M$ лежит на окружности $′′ (DY Z )$ . Также

∠EMF = ∠FMX ′+ ∠EMX ′= ∠F Y′X ′+∠EZ ′X ′ =∠F XY + ∠EXZ = π− ∠A,

поэтому $M$ лежит на окружности $(AEF )$ . Аналогично $M$ лежит на окружностях $(BFD)$ , $(CED )$ .

Пусть $Φ$ — инверсия с центром в точке $M$ и произвольным радиусом. Тогда

$pict$

Также

∠ Φ(X ′)Φ(E)Φ(F )=∠F MX ′ = ∠FY′X′ = ∠FXY = ∠AF E = ∠AE ′F ′.

Аналогично $∠Φ(X′)Φ (F)Φ(E)= ∠AF′E′$ . Следовательно, треугольники $AE ′F ′$ и $Φ(X ′)Φ(E )Φ (F)$ подобны. Проделывая аналогичные рассуждения для двух других сторон мы получаем

△ABC ∪ △D ′E ′F′ ∼ △Φ (X ′)Φ(Y′)Φ(Z′)∪△Φ (D )Φ(E)Φ(F).

Следовательно, угол между окружностями $′ ′ ′ Φ((X Y Z))$ и $Φ((DEF ))$ равен углу между окружностями $(ABC )$ и $(DEF )$ по подобию, с другой стороны, равен углу между окружностями $′ ′′ (X Y Z )$ и $(DEF )$ , поскольку инверсия сохраняет углы.

Ответ:

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

Задача 4#100664

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

1. Пусть $G$ — вторая точка пересечения описанных окружностей $AEF$ и $ABD$ . Поскольку четырехугольник $AFEG$ описанный, то $∠AF E =180∘− ∠AGE$ . Четырехугольник $ABDG$ также описанный, значит $∠ABD = 180∘− ∠AGD$ .

$PIC$

Поскольку $EF ∥BC$ , то $∠AF E = ∠ABD$ .

Получаем, что $∠AGE = ∠AGD$ . Тогда $G$ , $E$ , $D$ лежат на одной прямой.

2. Поскольку треугольники $BFD$ и $DEC$ равнобедренные, то $∠F BD =∠F DB$ и $∠ECD = ∠EDC$ . Тогда

∠EDF = 180∘− ∠BDF − ∠EDC =180∘− ∠B − ∠C =∠BAC

Также из определения $D′$ (точка, симметричная $D$ относительно $EF$ ) следует, что

′ ∠ED F =∠EDF =∠BAC

Получается, что $D ′$ лежит на описанной окружности $AEF$ .

$PIC$

Из определения $′ D$ как симметричной точки:

FD = FD′ = FB и D ′E = ED = EC

Значит, $B,D$ и $D′$ лежат на одной окружности с центром в $F,$ а $C,D$ и $D ′$ — с центром в $E.$ Тогда выполнены следующие равенства для вписанных и центральных углов:

′ 1 ′ 1 ′ ′ ∠FBD = 2∠AF D = 2∠AED =∠ACD

Получаем, что $′ D$ лежит и на описанной окружности $ABC$ .

Предыдущая подтема