ЮМШ (олимпиада Юношеской Математической Школы) —Каталог задач по Олимпиадной математике

Главная
Каталог задач
Каталог заданий по Олимпиады - Математика
ЮМШ (олимпиада Юношеской Математической Школы)

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

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

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

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

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

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

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

Отбор ЮМШ

Планиметрия на ЮМШ

Комбинаторика на ЮМШ

Теория чисел на ЮМШ

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

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

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

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

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

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

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$ и $DF C$ равнобедренные, то $∠EBD = ∠EDB$ и $∠F CD =∠F DC$ . Тогда $∠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$ . Тогда $′ ′ ∠EBD =∠AED ∕2=$ $′ ′ = ∠AFD ∕2= ∠ACD$ . Получаем, что $′ D$ лежит и на описанной окружности $ABC$ .

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

$PIC$

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

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

2) $pow(AFE)(T) =TE2 = TD2 = powD(T)$

Получаем, что $ST$ — радикальная ось наших 2 окружностей. Тогда на этой же радикальной оси лежат $X$ и $Y$ . Тогда $XA ⋅XF = XD2$ и $YA ⋅Y E = YD2$ $⇒$ $XD$ — касательная к описанной окружности $AF D$ , и $YD$ — касательная к описанной окружности $AFD$ . Тогда $∠XAD = ∠XDF$ , $∠Y AD =∠Y DE$ $⇒$ $∠XDF + ∠YDE = ∠BAC$ $⇒$ $∠XDY +∠XAY = ∠XAY + ∠XAY + 180∘− ∠DF E− ∠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 YX +∠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 )$ , поскольку инверсия сохраняет углы.

Ответ:

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

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

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

Задача 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#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$ -четверкой, что нам подходит.

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

Задача 4#76655

Сумма всех натуральных делителей числа $n$ более чем в 100 превосходит само число $n$ . Докажите, что есть сто идущих подряд чисел, каждое из которых имеет общий делитель с $n$ больший 1.

Источники: ЮМШ-2023, 11 класс, отборочный тур (см. yumsh.ru) | ЮМШ-23/24, 11 класс, 1 отборочный тур (см. yumsh.ru)

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

Сначала докажем лемму.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма.

Пусть $φ (n)$ - функция Эйлера числа $n.$ (Количество чисел от $1$ до $n$ взаимно простых с $n.$ ) Тогда для любого натурального числа $n >1$ справедливо неравенство

∑ n2 d < φ(n)- d|n

_________________________________________________________________________________________________________________________________________________________________________________

Доказательство леммы.

Запишем сумму делителей числа через произведение сумм степеней его простых делителей. Если $n =pα1pα2...pαk, 1 2 k$ то

∑ 2 α1 2 α2 2 αk d =(1+ p1+p1+ ...+ p1 )(1+ p2+ p2+ ...+ p2 )...(1+ pk +pk+ ...+ pk ) d|n

Используя формулу суммы геометрической прогрессии, получаем:

∑ d= (1+ p + p2 +...+ pα1)(1+ p +p2+ ...+ pα2)...(1+ p +p2+ ...+ pαk)= d|n 1 1 1 2 2 2 k k k

(pα11+1 − 1)(pα22+1− 1)...(pαk+1− 1) = ----(p1−-1)(p2-− 1)...(pkk− 1)--.

Функция Эйлера вычисляется по формуле $φ(n)=pα11−1(p1− 1)pα22−1(p2− 1)...pαkk− 1(pk− 1).$ Тогда чтобы получить $φ(n)$ в знаменателе, домножим числитель и знаменатель на $pα11−1pα22−1...pαkk−1$

(pα11+1−-1)(pα22+1−-1)...(pαkk+1−-1)= (p1− 1)(p2− 1)...(pk− 1)

α1−1 α2−1 αk−1 α1−1 α2−1 αk−1 = p1--p2α1−.1..pk--(pα12−1-− 1)(p2-α−k−11)...(pk---−-1)= p1 (p1− 1)p2 (p2− 1)...pk (pk− 1)

(p2α1 − pα1−1)(p2α2− pα2−1)...(p2αk− pαk−1) p2α1p2α2...p2αk n2 = --1----1-----2--φ(2n)------k----k----< -1--2φ(n)--k--= φ(n)

_________________________________________________________________________________________________________________________________________________________________________________

Решение задачи.

По условию и лемме

∑ -n2- 100n < d|nd< φ(n).

Тогда

100n< -n2-⇒ φ(n)< n-. φ(n) 100

То есть количество чисел от $1$ до $n$ взаимно простых с $n$ меньше $-n- 100.$

Рассмотрим два случая: $n$ делится на $100$ и $n$ не делится на $100.$

1. Число $n$ делится на $100.$ Тогда можно разбить числа от $1$ до $n$ на $n-- 100$ групп по $100$ идущих подряд чисел. Если количество чисел от $1$ до $n$ взаимно простых с $n$ меньше $n-- 100$ , то хотя бы в одной группе не будет числа взаимно простого с $n$

2. Число $n$ не делится на $100.$ Тогда среди чисел $2$ до $n$ можно выделить $-n- [100]$ групп по $100$ идущих подряд чисел. Если в каждой группе будет число взаимно простое с $n$ , то чисел взаимно простых с $n$ хотя бы $n [100]+ 1$ ( $1$ тоже взаимно проста с $n$ ). Это противоречит тому, что количество чисел от $1$ до $n$ взаимно простых с $n$ меньше $n 100-$

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

Задача 5#76654

Докажите, что для любого $x∈ [0;2]$ верно

x ∘ ------- 2 +1 − 10,5x+ 4≤0

Источники: ЮМШ-2023, 11 класс, отборочный тур (см. yumsh.ru) | ЮМШ-23/24, 11 класс, 1 отборочный тур (см. yumsh.ru)

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

Подсказка 1

Немного преобразуем неравенство так, чтобы нам приходилось сравнивать показательную функцию с функцией с корнем. Как они выглядит на графике? Что у них общего и чем они различаются?

Подсказка 2

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

Подсказка 3

Рассмотрите точки, в которых графики пересекаются.

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

Решение 1.

Перепишем неравенство, данное в условии:

x ∘------- 2 ≤ 10,5x+ 4− 1.

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

С графиком функции $y =√10,5x-$ наоборот: если соединить две точки, принадлежащие графику, отрезок их соединяющий лежит ниже графика. График функции $√------- 10,5x+ 4− 1$ это сдвинутый по осям абсцисс и ординат график функции $√---- y = 10,5x.$ Значит, и для графика функции $√ ------- 10,5x+ 4− 1$ верно: если соединить две точки, принадлежащие графику, отрезок их соединяющий лежит ниже графика.

Подставим значения $x =0, и x= 2$ в левую и правую части неравенства. Получаем, что графики функций $x √------- 2 и 10,5x+ 4− 1$ проходят через точки $(0;1) и (2;4).$ Тогда все значения функции $x 2$ лежат ниже отрезка, соединяющего точки $(0;1) и (2;4),$ а все значения $√------- 10,5x+ 4− 1$ выше.

То есть в каждой точке отрезка $[0;2]$ все значения функции $x 2$ не меньше чем значения $√ ------- 10,5x +4− 1.$

∘------- 2x ≤ 10,5x +4− 1

x ∘ ------- 2 +1− 10,5x +4 ≤0.

Решение 2.

Обозначим

x ∘ ------- f(x)= 2 +1− 10,5x+4.

Докажем, что на отрезке $[0;2]$ верно $f(x)≤ 0.$

Производная $f(x)$ на отрезке $[0;2]$

f′(x)= ln(2)⋅2x− -√--1---- 2 10,5x+ 4

Приравняем $′ f (x)$ к $0$ :

1 ln(2)⋅2x− 2√10,5x+-4 = 0

ln(2)⋅2x =-√--1---- 2 10,5x +4

x∘------- --1-- 2 10,5x+ 4= 2ln(2)

Функции $2x и √10,5x+-4$ – возрастающие на отрезке $[0;2].$ Тогда $2x√10,5x+-4$ тоже возрастающая. Значит производная имеет не более одного корня на отрезке $[0;2].$ То есть $f(x)$ имеет не более одной точки экстремума на отрезке $[0;2].$

На концах $f(0)= f(2)= 0.$

Тогда если на отрезке $[0;2]$ нет точек экстремума и монотонность не меняется, то $f(x)=0$ на всем отрезке. Если точка экстремума лежит на отрезке $[0;2],$ о возможны два варианта:

1. Это точка минимума. Тогда функция убывает от 0 до точки минимума, а затем возрастает до 2.

2. Это точка максимума. Тогда функция возрастает от 0 до точки максимума, а затем убывает до 2.

Отметим, что $f(1)<0$

∘ -------- ∘--- f(1)= 21+ 1− 10,5⋅1+ 4= 3− 14,5 <0

Значит, возможен только первый вариант. Тогда $f(x)≤ 0$ на всём отрезке $[0;2]$

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

Задача 6#76652

Окружности $ω 1$ и $ω 2$ пересекаются в точках $A$ и $B$ . Прямая $l 1$ , проходящая через точку $A$ , второй раз пересекла окружность $ω 1$ в точке $C$ , а $ω2$ — в точке $D$ . Прямая $l2$ , проходящая через точку $B$ , второй раз пересекла окружность $ω1$ в точке $E$ , а $ω2$ — в точке $F.$ Оказалось, что прямая $CE$ касается $ω2$ в точке $G$ (точка $E$ лежит на отрезке $CG$ ). Докажите, что $BG$ — биссектриса $∠DBE$ .

Источники: по мотивам отборочного тура ЮМШ 23/24

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

Подсказка 1

Посчитаем уголочки! Как использовать вписанность? Выразим угол FBE и подумаем, как считать углы дальше.

Подсказка 2

Угол между касательной равен вписанному углу, опирающему на хорду. Найдите угол DFC и свяжите его с DAF :) Чему равен угол FBE?

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

Поскольку четырехугольники $ABEC$ и $ADGB$ вписанные, то

∠BEG = ∠CAB = ∠BGD

Также, поскольку прямая $CE$ касется окружности $ω2$ , по теореме об угле между касательной и хордой

∠BDG = ∠BGE

Теперь рассмотрим треуугольники $△BEG$ и $△BGD.$ В них имеются две пары равных углов $(∠BEG = ∠BGD, ∠BGE = ∠BDG ),$ значит, третьи углы у них тоже равны, т.е.

∠DBG = ∠GBE

Получаем, что $BG$ — биссектриса угла $∠DBE.$

$PIC$

Замечание. Если точка $G$ лежит внутри отрезка $CE,$ то чертёж меняется, но решение остаётся аналогичным. Попробуйте решить задачу и для этого расположения точек.

Курсы

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

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

Задача 7#76651

Найдите количество функций $f :{1,2,3,4,5,6} → {1,2,3,4,5,6}$ для которых верно $f(f(f(x)))=x$ для всех $x∈ {1,2,3,4,5,6}$ .

Источники: ЮМШ-2023, 11 класс, отборочный тур (см. yumsh.ru) | ЮМШ-23/24, 11 класс, 1 отборочный тур (см. yumsh.ru)

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

Возьмем какое-нибудь число $a ∈{1,2,3,4,5,6}.$ Тогда возможны два варианта:

1. Если $f(a)= a,$ то и $f(f(f(a)))= a.$

2. Предположим $f(a)= b и b⁄= a.$ Тогда $f(b)= c, где c⁄= a,c⁄= b.$ Иначе
(а) Если $f(b)= a, то f(f(f(a)))= f(f(b)) =f(a)=b ⁄=a.$
(b) Если $f(b)= b, то f(f(f(a)))= f(f(b))= f(b) =b⁄= a.$
И так как $a =f(f(f(a)))= f(f(b))= f(c),$ то $f(c)=a.$

Таким образом, для любого $a∈ {1,2,3,4,5,6}$ либо $f(a)=a,$ либо есть три различных числа таких, что $f(a)= b,f(b) =c и f(c)= a.$

При этом любая функция с таким свойством подходит. Тогда найдем число функций с необходимым свойством.

1. Нет ни одной тройки элементов, что $f(a)= b,f(b)= c, и f(c)= a.$ Значит, для всех чисел $a∈{1,2,3,4,5,6}$ верно $f(a)= a.$ Такая функция одна.

2. Есть одна тройка элементов, что $f(a)= b,f(b)= c, и f(c)=a.$ Выбрать тройку можно $C36$ способами. При этом есть два способа задать функцию в тройке. Итого $2C36$ функций.

3. Есть две тройки элементов, что $f(a)= b,f(b)= c, и f(c)= a.$ Выбрать первую тройку можно $C36$ способами, остальные три элемента образуют вторую тройку. Но варианты, в которых выбрали в первую тройку $a,b,c$ и выбрали все кроме $a,b,c$ одинаковые. То есть $C36 :2$ способов разбить элементы на две тройки. При этом в каждой тройке есть два способа задать функцию. Итого $2⋅2⋅C36 :2 =2C36$ функций.

Всего число функций равно

1 +2C36 + 2C36 = 81

Ответ: 81

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

Задача 8#76650

Квадратный трёхчлен $x2− px+ q$ с натуральными коэффициентами имеет два корня. Оказалось, что если $q$ уменьшить на $30%$ , то разность его корней увеличится в 5 раз. Найдите такой трёхчлен с наименьшей возможной суммой корней.

Источники: ЮМШ-2023, 11 класс, отборочный тур (см. yumsh.ru) | ЮМШ-23/24, 11 класс, 1 отборочный тур (см. yumsh.ru)

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

Подсказка 1

Давайте вспомним, как мы находим корни в приведённом квадратном уравнении! А как можно выразить разность корней?

Подсказка 2

Да, корни находим через обычную формулу с дискриминантом. Тогда разность корней, это просто корень из дискриминанта нашего уравнения! Остаётся составить уравнение, в котором будет отражаться условие задачи!

Подсказка 3

Верно, из условия мы получаем, что 20p² = 81q. Остаётся найти минимальные p и q

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

По формуле корней квадратного уравнения имеем: $x = p±√p2−4q. 1,2 2$ Следовательно, $x − x = ∘p2-− 4q. 2 1$ После уменьшения $q$ на $30%$ разность корней станет равна $∘ 2---(7--) p − 4 10q.$ Следовательно, при условии, что $2 p − 4q ≥ 0,$ получаем

∘ ------ ∘ ------- 5 p2− 4q = p2− 14q ⇐⇒ p2 = 81q > 4q ⇐ ⇒ 4⋅5⋅p2 = 34 ⋅q. 5 20

По теореме Виета сумма корней квадратного трёхчлена $x2− px+ q$ равна $p.$ Наименьшее натуральное $p,$ удовлетворяющее равенству $4⋅5⋅p2 = 34⋅q,$ это $32 =9,$ так как $p2$ должно делиться на $34.$ Тогда $q = 20.$

Ответ:

$x2− 9x+ 20$

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

Задача 9#69411

Общий сюжет. Пусть $f(a,b)$ — это количество способов пронумеровать клетки доски $a ×b$ номерами от 1 до $ab$ так, что каждая следующая находится в одной строке или столбце хотя бы с одной из предыдущих.

1. Найдите $f(3,2)$ .

2. Покажите, что

( ) f(a,a)≤ 100-a2! 2a

3. Докажите, что

( 2) f(a,a)≥ --a-!a 100⋅8

4. Найдите $f(a,2)$ .

Замечание. “Найти” означает выписать ответ в замкнутом виде.

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

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

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

Чтобы начать расставлять числа, нужно как-то зафиксировать хоть что-то. Попробуйте зафиксировать 1 и понять, почему так можно делать. Как расставлять дальше?

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

Для 2 у нас есть 3 варианта. У каждого из них свои ограничения на следующие клетки, которые несложно разобрать по отдельности.

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

Попробуем расставлять числа по возрастанию, тогда будет проще рассуждать. Если мы поставим 1 в нижний левый угол, то какова доля клеток, куда мы можем поставить 2? А 3? Как выглядит общий случай?

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

Доля мест, куда мы можем поставить 2, не больше чем 2/а(почему?). Подумаем о том, как будет меняться такая доля с каждый новым числом.

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

С каждым новым числом общее коколичество свободных мест уменьшается на 1, а количество подходящих увеличивается максимум на (а-1). С помощью неравенства можно понять, до какого числа мы можем считать долю как (i+1)/a. Теперь у нас есть количество вариантов для каждого числа, каким тогда будет общее мест?

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

Произведение количества вариантов для каждого числа! Осталось лишь доказать, что такое число не больше 100 * (a^2)!/(2^a).

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

Отлично, количество вариантов уже посчитано в предыдущем пункте. Теперь нужно доказать, что это число больше того, что нас просят в этот раз. Попробуем доказать по индукции по а!

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

Базу проверить несложно. Теперь попробуем доказать, что (a+1)^(a-1) <= a^(a-2)*8a. Для этого попробуем преобразовать неравенство, тогда у нас получится найти связь с числом e!

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

1. Заметим, что при перестановке столбцов и строк в расстановке чисел она всё ещё будет удовлетворять условию. Значит, можно посчитать число способов с $1$ в нижнем левом угле и затем умножить его на $6$ . Разберём возможные позиции для двойки:

2

1

$=⇒ 4!$ (остальные числа можем поставить как угодно)



1	2

$=⇒ 3⋅3!$ (нам нельзя ставить $3$ в верхний правый угол. выбираем для неё одно из трёх других мест и расставляем остальные как угодно)



1		2

$=⇒ 3⋅3!$ (симметричен предыдущему случаю)

Тогда $f(3,2)= 6(4!+ 2⋅3⋅3!)= 360.$

2. Будем расставлять числа по возрастанию. Переставим столбцы и строки так, чтобы $1$ находилась в левом нижнем углу. Рассмотрим долю мест, на которые мы можем поставить $2$ . Эта доля $= 2(aa−2−1)1 ≤ 2a$ . Для $3$ эта доля будет $(a−1)+(aa−21−)2+(a−2)≤ 3a$ . И в общем случае: с каждым новым числом общее количество свободных мест уменьшается на 1, а количество подходящих увеличивается максимум на $(a− 1)$ . Сравним:

(i+-1)(a+-1)≤ i+1- a2− i a

что при $i≤ a$ верно.

Тогда общее количество мест

2 (a−-1)! (a)!aa−2

Докажем, что

2 (a−-1)! (a2)! (a )!aa−2 ≤ 100 2a

что равносильно

a a−2 2 ⋅(a− 1)!≤ 100a

По неравенству о средних:

a2 x(a− x)≤ 4

Тогда

2a⋅(a− 1)!≤ 8⋅1⋅(a − 1)⋅aa− 1 ≤ 100aa−2

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

3. Докажем, что

( 2) (a2)!(a−a−12)!-≥--a-!a a 100⋅8

что равносильно

a a−2 (a − 1)!⋅100⋅8 ≥ a

Базу $a= 2$ легко проверить

100⋅64≥ 1

По предположению индукции

----aa−2----≤ 1, (a− 1)!⋅100⋅8a

а для перехода надо доказать

-(a+-1)a−1-- (a)!⋅100⋅8a+1 ≤ 1

Тогда докажем

a−1 a−2 -(a+-1)-a+1 ≤----a------a, (a)!⋅100⋅8 (a− 1)!⋅100⋅8

что равносильно

(a+ 1)a−1 ≤ aa−2⋅8a ⇐⇒ (a-+1)a−1 ≤ 8 a

1a−1 (1+ a) ≤ 8

а это уже известное неравенство (можно оценить даже не числом 8, а числом Эйлера - числом $e$ ), которое тоже легко проверить по индукции для любого натурального $a.$

4. Будем расставлять числа по возрастанию. Пусть мы начали с какой-то из двух строк. Нам интересен первый момент, когда мы “перескочим” на другую, так как после этого остальные числа можно расставить как угодно.

			…	k	…

1	2	3	…		…

Пусть мы “перескочили” на числе $k +1$ . Посчитаем количество таких расстановок: мы выбираем одну из двух строк начальной, затем расставляем числа от $1$ до $k$ в этой строке, затем выбираем, куда поставить $k+ 1$ — для этого есть только $k$ способов, так как мы должны поставить его в один столбец с любым из $k$ чисел. Все остальные числа можем расставить как угодно:

2⋅a⋅(a− 1)⋅...⋅(a− k+ 1)⋅k ⋅(2a− (k +1))!

Таким образом,

∑a f(a,2)= 2⋅a⋅(a− 1)⋅...⋅(a− k+ 1)⋅k ⋅(2a− (k+ 1))!= k=1

∑a --a!-- =k=12⋅(a− k)! ⋅k⋅(2a− (k+ 1))!

Что делать с такой суммой не очень понятно, хочется выразить её через $Cnm$ — с ними мы умеем работать, то есть мы хотим получить выражение вида $(nn+!mm!)!$ :

f(a,2)= ∑a 2⋅--a!--⋅k⋅(2a− (k+ 1))!= k=1 (a− k)!

a a =2⋅a!(a− 1)!∑ -k(2a−-k−-1)! =2 ⋅a!(a − 1)!∑ kCa−1 k=1(a− 1)!(a− k)! k=1 2a−k−1

Осталось посчитать эту сумму. Распишем её:

a ∑ kCa−1 = Ca−1 +2Ca−1 + 3Ca−1 + ...+ aCa−1 k=1 2a−k−1 2a−2 2a−3 2a−4 a− 1

Пусть у нас есть $2a− 1$ игроков, которые упорядочены по убыванию своей силы. мы выбираем среди них команду из $a$ игроков и капитана, который должен быть сильнее всех игроков. С одной стороны, мы можем просто набрать команду из $a+ 1$ игроков и назначить капитаном самого сильного из них. Это же число способов можно посчитать по-другому: выберем самого сильного после капитана участника команды. Пусть он имеет номер $k+ 1$ (то есть сильнее него ровно $k$ человек). Тогда у нас есть $k$ способов выбрать капитана, и потом нам нужно набрать команду из $a− 1$ человека из $2a− k− 2$ . Получается, что

a ∑ kCa2−a1−k−1 = Ca2+a1 k=1

Ответ:

1. $360$

2. что и требовалось доказать

3. что и требовалось доказать

4. $a+1 C2a$

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

Задача 10#69410

Общий сюжет. Дан остроугольный неравнобедренный треугольник $ABC$ . На меньшей дуге $BC$ его описанной окружности выбирается переменная точка $D$ . Точка $′ D$ симметрична точке $D$ относительно прямой $BC$ . Луч $′ CD$ пересекает отрезок $AB$ в точке $E$ . Луч $′ BD$ пересекает отрезок $AC$ в точке $F$ .

1. Докажите, что окружность $ω$ , описанная около треугольника $D ′EF$ , проходит через фиксированную точку.

2. Известно, что в положении $D = D1$ центр окружности $ω$ лежит на отрезке $AB$ , а в положении $D = D2$ — на стороне $AC$ . Отрезки $BD2$ и $CD1$ пересекаются в точке $X$ . Докажите, что прямые $AX$ и $BC$ перпендикулярны.

3. Окружность $ω$ вторично пересекает окружность $ABC$ в точке $G$ . Докажите, что прямая $′ D G$ проходит через фиксированную точку.

4. Докажите, что если $∠A =60∘$ , то расстояние от вершины $A$ до точки Торричелли треугольника $ABC$ не превосходит диаметра окружности $ω$ (при любом положении точки $D$ ). Напомним, что точкой Торричелли треугольника $ABC$ называется такая точка $T$ , что $∠AT B =∠BT C =$ $∠CT A =120∘$ .

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

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

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

Чтобы найти фиксированную четвертую точку на окружности, попробуем посчитать углы, чтобы найти вписанный четырехугольник! Точка D лежит на окружности, ее отражают, поэтому посчитать угол FD’E не составит труда! Какой угол может дополнять его до 180?

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

Если центр окружности лежит на AB или AC, то несложно найти точное расположение центра, т.к. отрезки на указанных прямых являются хордами окружностей. Хочется подробнее рассмотреть D1’ и D2’, а точнее углы, которые на них опираются. Найти их не сложно в силу того, что они лежат на окружности.

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

Углы CD1’A и BD2’A будут прямыми(почему?). Итак, два перпендикуляра к пересекающимся отрезкам пересекаются на рисунке, а нам хочется найти другую перпендикулярность. На какой объект это может намекать?

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

На ортоцентр! Сделаем так, чтобы точка пересечения BD2’ и CD1’ стала ортоцентром нового треугольника! Мы найден прямую, к которой перпендикулярен отрезок, одной из вершин которого является А - теперь мы ближе к тому, что нам нужно доказать! Осталось лишь доказать, что этот отрезок лежит на прямой AX, а третья сторона треугольника, в котором мы нашли ортоцентр, параллельна BC!

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

Тут хочется угадать ту самую фиксированную точку…очень часто на олимпиадах помогает сделать красивые и точные чертежи, чтобы попробовать хотя бы интуитивно узнать точку. Докажем, что все прямые будут проходить через середину BC.

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

Мы понимаем, что через точку М проходит прямая D’G, где G - точка пересечения окружностей. Доказывать вписанность там, где много окружностей и симметрии должно быть проще, чем доказывать, что прямая проходит через середину отрезка. Поэтому попробуем доказать, что точка пересечения MD’ с малой окружностью лежит на окружности ABC. Итак, чем же мы можем пользоваться? Вписанностью D’FAGE, а также тем, что M - середина, т.е. может помочь в симметрии. На правильные действия и на полезный подсчет углов может намекать и то, что точка D лежит на окружность ABC и симметрична D’ относительно BC.

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

Интересно, что благодаря точке Торричелли у нас появляется угол, который с углом A в сумме дает 180. Благодаря пункту 1) задачи мы понимаем, на какой окружности лежит точка Торричелли. Попробуем рассмотреть точку T’, изогонально сопряженную с точкой Торричелли. Что можно о ней сказать?

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

Она тоже лежит на окружности BD’C! Раз уж у нас есть окружностью, отметим ее центр N. Понятно, что он лежит на дуге BC. Не совсем понятно, как работать с самой точкой Торричелли, поэтому попробуем найти другой отрезок, равный AT. В этом нам могут помочь равные треугольники. Какие треугольники очень похожи на равные между собой?

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

Если треугольники ATN и AT’N равны, то AT=AT’. Пока не совсем понятно, что делать дальше, поэтому просто попробуем изобразить то, что узнали в предыдущем пункте задачи: точку M, G, через которую проходят прямые MD’(помним, что D’ лежит на той же окружности, где и T, T’. Отметим точку пересечения AM и окружностей BTC и ABC(K’ и K). Пока что видим только много симметрий, имеет смысл записать степень точки M и цепочку равенств. К какому выводу можно прийти?

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

Понимаем, что AGD’K вписанный. Теперь мы можем сравнивать AT’ и диаметр окружностей AGD’K. Значит, нам нужен диаметр. Точки T, T’, K - все лежат на одной окружности. Быть может, попробовать доказать, что какие-то из них совпадают?

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

Точка T’ на самом деле совпадает с точкой K! Осталось лишь осознать, почему AK не больше диаметра, который нам нужен)

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

$PIC$

1. Пусть $∠A = α$ . Тогда $∠BDA = 180∘ − α$ . Из симметрии $∠BD ′A= ∠BDA$ , но тогда $∠A+ ∠ED ′F = 180∘$ , то есть $AED ′F$ - вписанный, то есть для любого выбора точки $D$ окружность $ω$ проходит через фиксированную точку $A$ .

$PIC$

2. Если центр $ω$ лежит на отрезке $AB$ , то $AE$ - диаметр, а $∠AFE$ - прямой. Тогда углы $′ AD2B$ и $′ AD 1C$ - прямые. Рассмотрим точку $′ X$ , симметричную точке $X$ относительно $BC$ . Заметим, что если $′ AX$ перпендикулярно $BC$ , то и $AX$ будет перпендикулярно $BC$ . Продлим $′ AD 2$ до пересечения с $′ BD 2$ в точке $L$ и $′ AD 1$ до пересечения с $′ BD 2$ в точке $M$ . Тогда $′ MD 2$ и $′ LD1$ - высоты в треугольнике $AML$ , $X$ - его ортоцентр, $AX$ - третья высота. Докажем, что $ML||BC$ : Действительно, из вписанности $′ ′ ′ ′ BD 1D2C∠LCB = ∠BD 2D 1$ . $′ ′ MLD 2D1$ - вписанный ( $′ ′ ∘ ∠LD2M = ∠MD 1L= 90$ ), откуда $′ ′ ′ ∠BD2D 1 = ∠D1LM =⇒ ML ||BC =⇒ AX$ перпендикулярно $BC$

3. Докажем, что все прямые будут проходить через точку $M$ - середину $BC$ . Будем доказывать с конца - проведём через точки $M$ и $D ′$ прямую, и докажем, что она пересекает окружность $ABC$ в нужной нам точке. Пусть это точка $G′$ . Отразим $D′$ относительно точки $M$ , получим точку $U$ . $∠BUC = ∠BD ′C = ∠BDC$ , поэтому $U$ попадёт на описанную окружность $ABC$ . Посчитаем углы: $∠BD ′U = ∠D′UC$ так как $BDCD ′$ - параллелограмм, $∠G′UC =∠G ′AC$ как вписанные, $∠G ′D ′F =∠BD ′M$ как вертикальные, откуда $∠G ′D′F =∠G ′AF$ , то есть $G′ADF$ - вписанный, что и требовалось доказать.

$PIC$ $PIC$

4. Пусть $T$ - точка Торичелли треугольника $ABC$ . Заметим, что она лежит на дуге $′ BD C$ (так как $∘ ∘ ∠BTC = 120 = 180 − ∠A$ Рассмотрим точку $′ T$ , изогонально сопряжённую точке $T$ . Заметим, что $∘ α +β +γ+ δ = 120$ , и $∘ β+ γ = 60$ , откуда $′ ∘ ∘ ∘ ∠BT C = 180 − 60 = 120$ , и точка $′ T$ лежит на дуге $′ BD C$ . Также заметим, что $∘ x +y =y +δ = 60$ , откуда $y =δ$ , то есть $′ ∘AT B$ касается $CB$ в точке $B$ . Тогда мы можем определить точку $T ′$ как точку пересечения двух окружностей, которые проходят через $A$ и касаются $BC$ в точках $B$ и $C$ соответственно.

$PIC$

Пусть $N$ - середина малой дуги $BC$ . Докажем, что $N$ - центр окружности $T′CB$ . Рассмотрим точку пересечения биссектрис $I$ . Тогда $∠BIC = 90∘+ ∠A2-= 120∘$ , то есть $I$ также лежит на дуге $BD′C$ , а по лемме о Трезубце мы знаем, что $NI = NB = NC$

$PIC$

Заметим, что (по определению изогонального сопряжения) $AT$ и $AT ′$ будут симметричны относительно биссектрисы $AI$ . Тогда в треугольниках $ATN$ и $AT′N$ : $AN$ - общая, $∠TAN = ∠T′AN$ , $TN = T′N$ . Тогда возможны две ситуации:

$PIC$

Треугольникии либо равны, либо сумма двух их углов равна $180∘$ Предположим, что вторая ситуация возможна. Тогда $∠NT A +∠NT ′A =$ $=180∘$ , но $∠NT A> ∠NBA$ , $∠NT ′A > ∠NCA$ , откуда $∠NT A +∠NT ′A> ∠NBA + ∠NCA = 180∘$ . Противоречие, следовательно треугольники $ATN$ и $AT′N$ равны, и $AT =AT ′$

$PIC$

Пусть $M$ - середина $BC$ . Проведём луч $AM$ , который пересечёт дугу $BD ′C$ в некоторой точке $K$ и дугу $BDC$ в некоторой точке $K ′$ . Тогда из симметрии $MK = MK ′$ . Через точку $M$ и произвольную точку $D′$ на дуге проведем прямую, которая пересечёт окружность $∘ABC$ в точке $G$ . (По доказанному ранее $ω =∘GAD ′$ ). Отразим $D ′$ относительно $M$ , получим точку $D′1$ Распишем степень точки:

$MB ⋅MC = MK ′⋅MA$	$(∘ABC,M )$
$′ MK ⋅MA =MK ⋅MA$	$′ (MK = MK )$
$MB ⋅MC = MD ′1⋅MG$	$(∘ABC,M )$
$MD ′⋅MG = MD ′1⋅MG$	$(MD ′ =MD ′1)$

Откуда $MD ′⋅MG = MK ⋅MA$ , то есть любая окружность $ω$ проходит через точку $K$ .

$PIC$

Достроим $BKC$ до параллелограмма. Тогда

∠T′CB = ∠CBK ′ =∠K ′AC

∠T′BC = ∠BCK ′ =∠K ′AB

Это свойство выполнено и для точки $K$ , и для точки $T′$ . Но такая точка всего одна, следовательно, они совпадают, а хорда окружности всегда меньше или равна диаметру окружности!

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

Задача 11#83912

$P$ — некий полином с целыми коэффициентами, $A$ и $M$ — целые числа. Построим последовательность $a n$ , где $a = A 1$ , и $a =P (a) n+1 n$ и пусть $rn$ — остаток от деления $an$ на $M$ .

1. Пусть $P(x)= x2+ x+ 1,A = 1,M = 32022$ . Докажите, что период последовательности $rn$ (то есть, такое наименьшее $t$ , что $rn+t = rn$ при достаточно больших $n$ ) равен 2.

2. Найдите длину предпериода той же последовательности (то есть такое наибольшее $n$ , что $an+t ⁄= an$ , где $t$ — период).

3. Назовем полином стабильным по модулю $M$ , если существует $B$ , такое что для любого $A$ найдется $k$ , для которого $rk = B$ . Докажите, что полином $3 2 f = x − x − 2$ нестабилен по модулю $M$ , если $M$ является квадратом нечётного числа.

4. Докажите, что многочлен $P (x)= x2− 3x +12$ стабилен для бесконечного числа натуральных $M$ .

Источники: ЮМШ-2022, 11 класс, 3 сюжет (см. yumsh.ru)

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

1. Легко видеть, что остатки $an$ от деления на 3 чередуются с периодом 2 (1, 0, 1, 0, . . .) поэтому период остатков по модулю $M = 32022$ тем более не равен 1.
Покажем что он равен 2.
Заметим, что $an+2 − an =a2n+1− a2n−1+an+1− an−1 = (an+1− an−1)(an+1+ an−1 +1)$
Отсюда следует, что если $an+1 − an−1$ делится на $3k$ , то тем же свойством обладает и $an+2− an$ , а если вдобавок $an+1$ , $an−1$ дают остаток от 1 деления на 3, то $an+2 − an$ делится на $3k+1$ .
Учитывая, что такая ситуация имеет место при каждом четном $n$ , получаем, что соответствующее $k$ может неограниченно увеличиваться, в частности, $an+2− an$ делится на $32022$ при некотором $n= n0$ (а значит и при всех $n >n0$ ). Поэтому период $rn$ равен двум.

2. Выпишем остатки от деления $an$ на 9 и на 27: легко убедиться, что это 2-периодические последовательности $1,3,4,3,4,...$ и $1,3,13,21,13,21,...$ соответственно.
Поэтому число $(an+1+ an−1+ 1)$ не делится на 3 при нечетных $n$ , делится на 3, но не на 9 при $n= 2$ и делится на 9, но не на 27 при четных $n >2$ .
То есть если $v n$ — степень вхождения 3 в число $a − a n+1 n−1$ , то $v = 1 2$ , $v =2 3$ а дальше $v =v + 2 2k+1 2k$ и $v = v 2k+2 2k+1$ .
Отсюда легко видеть, что наибольшее $s$ такое, что $v <2022 s$ равно 2022, то есть $a − a 2023 2021$ — последняя среди разностей вида $an+2− an$ не кратная $M$ .

3. Пусть $M =Q2$ , тогда $Q$ - нечетное число.
Заметим, что $f(2)= 23− 22− 2= 2$ ,значит, достаточно показать, что существует число, проделывая операцию из условия над которым мы не получим 2.
Рассмотрим числа вида $t= 2+ kQ$ , где НОД $(k;Q)= 1$
$f(t)= (2+ kQ)3 − (2+ kQ )2 − 2= Q3k3+ 5Q2k2+8Qk +2$
Нетрудно заметить, что $f(t)≡ 8Qk + 2(mod M )$
То есть числа вида $t= 2+ kQ$ , где НОД $(k;Q)= 1$ переходят в себя, но число 2 не имеет такого вида, поэтому полином $f = x3− x2 − 2$ нестабилен по модулю $M$ , если $M$ является квадратом нечётного числа.

4. Индукцией по $k$ докажем, что для $M = 7k$ многочлен $x2− 3x+ 12$ стабилен.
Обозначим через $a → b$ , то что $P(a)≡b(modM )$
База $k =1$

0→ 5→ 1 → 31 → 3→ 5→ 12 → 3→ 5→ 13→ 5 → 1→ 34→ 2→ 3→ 5→ 15→ 1 → 36 → 5→ 1→ 3

Таким образом, имеем цикл длины 3 везде одинаковый.
Переход $k→ k+ 1$
Пусть по модулю $M = 7k$ многочлен стабилизируется так, что всегда встретится $r$
Тогда по модулю $M = 7k+1$ остаток $r$ будет $7km+ r= r1$
$P (r1)≡r2− 3r+ 12 +7kn(2r− 3)(Mod 7k+1)$ , что не зависит от $n$ , при $0≡ 2r− 3(Mod 7)$
$0 ≡2r− 3(Mod 7)⇔ 5 ≡r(Mod 7)$ , что бывает по базе индукции, поэтому многочлен стабилизируется и по модулю $7k+1$ .

Ответ:

1. что и требовалось доказать

2. 2021

3. что и требовалось доказать

4. что и требовалось доказать

Интенсивы

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

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

Задача 12#79619

Вася посмотрел на граф $G$ на $n$ вершинах и поставил на каждую вершину $v$ переменную $x . v$ После чего рассмотрел выражение

∑ xixj f (x1,...,xn)=2⋅(i,j)−-ребро--- n∑ x2i i=1

Пусть $m$ и $M$ — минимум и максимум $f.$

(a) Пусть степень каждой вершины в графе равна $d.$ Найдите $M.$

(b) Докажите, что вершины графа $G$ можно покрасить в $[M ]+1$ цвет, так что любые две соседние вершины получат разные цвета.

( ) Z = 1 1 −-1 , 2 w

где $w$ — максимальный размер множества вершин графа $G,$ попарно соединенных ребрами.

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

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

(a)

Оценка. Занесём 2 в числитель и оценим каждое слагаемое следующим образом

2 2 2xixj ≤ xi +xj

Получим

∑ 2xixj ∑ (x2 +x2) (i,j)−-ребро---- ≤ (i,j)−-ребро-i---j- n∑ x2 ∑nx2 i=1 i i=1 i

Так как у каждой вершины степень у каждой вершины в графе равны $d,$ то каждая $2 xi$ в числителе встретиться ровно $d$ раз, следовательно

∑ 2 2 n∑ 2 ∑n 2 (i,j)− ребро(xi +xj) i=1dxi di=1xi -----∑n-2------= -n∑--2-= -n∑--2-= d i=1xi i=1xi i=1xi

Пример. Поставим во все вершины $1,$ получим

dn f(1,...,1)= n = d

(b) Будем доказывать от противного.

Если граф нельзя покрасить в $k$ цветов, то в графе есть вершина степени меньше чем $k,$ то удалим с рёбрами. Полученный граф также нельзя будет покрасить в $k$ цветов, иначе покрасим его, а потом докрасим удалённую вершину. Продолжим этот процесс, он конечный, так как в графе конечное число вершин.

Значит, найдётся подграф, в котором степени вершин хотя бы $[M ]+1.$ Поставим в вершины этого подграфа $1,$ а во все остальные вершины графа $0.$ Тогда значение выражения $f$ станет равным $[M]+ 1> M,$ а это противоречит тому, что $M$ — максимум выражения $f.$

(c) Кликой графа называется подмножество его вершин, любые две из которых соединены ребром. Аналогично определяется антиклика

Пример. Найдём в графе максимальную клику, в его вершины поставим $1 w,$ а в остальные $0.$

Оценка.

( ) Z ≤ 1 1− 1- 2 w

Рассмотрим расстановку, на которой достигается $Z.$ Если там есть вершина с 0, удалим её. По предположение

Z ≤ 1(1− -1), 2 w

если максимальная антиклика не уменьшилась, и

1( 1 ) 1 ( 1) Z ≤ 2 1− w−-1 <2 1− w- ,

если максимальная антиклика уменьшилась. Таким образом сделаем все числа ненулевыми.

Обозначим $S(v)$ — сумму чисел в смежных с $v$ вершинах. Заметим, что если $a$ и $b$ — несмежные вершины и $S(a)< S(b),$ то можно заметить $(x ,x) a b$ на $(0,x + x). a b$ Общая сумма не измениться, а $Z$ увеличиться, противоречие. Следовательно, если $a$ и $b$ — несмежные вершины, то $S(a)=S (b).$

Рассмотрим антиграф, проверим два случая:

1) Если он связен. Значит, для любых вершин $a$ и $b$ $S(a)= S(b),$ обозначим это число за $S.$ Следовательно по предположению

1 1 1 1 Z = 2S > 2(1− w)⇒ S > 1− w

Рассмотрим вершину $A$ максимальной антиклики.

S(A)> 1− 1w-

Следовательно, число в $A$ плюс в вершинах, не смешных с $A,$ меньше $1w-.$ Просуммируем по врем вершинам максимальной антиклики. Мы посчитали каждое число неменее 1 раза, значит сумма всех меньше, чем $w⋅ 1-= 1 w$ . Противоречие, следовательно, такое невозможно.

2) Антиграф не связен.

Ответ:

(a) d

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

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