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

ЮМШ - задания по годам → .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. Подсказка 1

Перепишем требуемое так: доказать, что для r=0, r=1 и r=p-1 r-четвёрки точно нет. Каким путём хочется доказать это утверждение?

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

Конечно! Давайте пойдём от противного. Если 0-четвёрка существует, то что следует из c ≡ ra (mod p)? Но разве это не противоречит равенству из условия?) Окей... Пусть теперь 1-четвёрка существует. Попробуем аналогично случаю r=0 прийти к противоречию! Какое тогда сравнение по (mod p) можно написать?

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

Верно! Тогда p = ab + cd ≡ ab + rad = a(b+d) (mod p). Какая делимость отсюда следует? Как можно оценить a и b+d?

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

Да! Либо a, либо (b+d) делится на p. Значит либо a≥p, либо (b+d)≥p. Хмм... но по условию ab + cd = p... Осталось написать цепочки неравенств и прийти к противоречию! Абсолютно аналогично докажем и для r=p-1.

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

Опять пойдём от противного. Пусть для одного r существуют две четвёрки: (a,b,c,d) и (a`, b`, c`, d`). Воспользуемся равенством из условия и попробуем связать четвёрки между собой.

Пункт 2. Подсказка 2

Ага. Можно заметить, что ac' ≡ ara' ≡ ca' (mod p). Попробуем аналогично связать b,d и b`,d`.

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

Тогда ac`- a`c, bd`- b`d кратны р. Предположим, что эти разности одновременно не равны нулю. Попробуем тогда оценить bd`- b`d, пользуясь тем, что ac`- a`c > 0. Какое противоречие получаем?

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

Да! ac` > p > ab. Отсюда с` > b, c` > d. Не забываем, что bd`- b`d кратно р, но разве оно больше p?) С этим случаем покончено. А что, если всё-таки какая-то разность равна нулю (пусть bd`- b`d=0)? Что можно сказать про делители переменных, исходя из условия ab+cd = p = a`b`+ c`d`? Как связать это с bd`= b`d.

Пункт 2. Подсказка 5

Заметим, что из ab + cd = p = a`b` + c`d` следует, что b и d, b` и d` взаимнопросты. Тогда из bd`= b`d следует, что b=b`, d=d`. Как теперь можно преобразовать равенство ab+cd = a`b` + c`d`? Что из него следует?

Пункт 2. Подсказка 6

Конечо! (a-a`)b=(c-c`)d. Но b и d взаимнопросты. Значит (a-a`) делится на d, (c-c`) делится на b! Обозначим это так: (a-a`)=dx, c-c`)=bx. Осталось рассмотреть случай x>0 и x<0, пользуясь неравенствами между переменными и заключить, что четвёрки совпадают!

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

Пусть (a,b,c,d), (a`,b`,c`,d`) — две четвёрки, удовлетворяющие условиям с r и c r` = p − r соответственно. Давайте действовать, как в прошлом пункте. Какие тогда цепочки сравнений по mod p тогда можно написать? Какое противоречие с делимость на p получается?

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

Верно! Можно получить, что ac`+a`c, bd`+b`d кратны p. Аналогично прошлому пункту, пусть с`≥b, тогда с`>c,d. Оценим bd`+b`d>0. Какое противоречие с делимостью на p можно получить?

Пункт 3. Подсказка 3

Да, bd`+b`d = 0, но bd`+b`d >0 !? Окей, пусть c`< b. Попробуем оценить a`c+ac и b`d+bd`. Чему могут быть равны эти выражения (помним, что они краты p).

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

a`c+ac` < ab+ a`b` < 2p, аналогично b`d+bd`<2p. Тогда, т.к. они делятся на p и больше нуля, то они равны p! А что еще равно p по условию?)

Пункт 3. Подсказка 5

Да! Запишем разность ab + cd и a`c+ac`. Получаем делимость на a. Такс... чего-то не хватает. Вспомним, что четвёрки упорядоченные. Что, если а — наибольшее из всех чисел? Выполняется ли полученная делимость?)

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

Окей...Давайте искать четверки так: на плоскости рассмотрим все векторы с целыми координатами (x,y), где y≡rx (mod p). Рассмотрим вектор u=(a,c), где сумма a+c минимальная. Что тогда нужно сделать, чтобы доказать существование r-четвёрки (или (p-r)-четвёрки)?

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

Давайте на прямой с уравнением xc − ya =p (пусть a>c) искать точку (d,−b) такую, что d> 0, d< a,d <b,c<b — тогда четвёрка (a,b,c,d) и будет искомой. С какими прямыми нам теперь нужно работать, чтобы найти иском точку?

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

Да! Рассмотрим прямую y=-x. Пусть точка (x₀,y₀)∈ℓ с целыми x₀,y₀ лежит выше прямой y+x= 0, а точка v₀=(x₀− a,y₀− c) — (нестрого) ниже. Какие условия теперь надо проверить?

Пункт 4. Подсказка 4

Конечно! Проверим нужные нам неравенства, которы мы писали выше! Проверьте эти условия, пользуясь выбором вектора (сумма координат минимальна).

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

Теперь выберем наибольшее целое неотрицательное m, при котором x₀−a−ma≥0. Тогда вектор v₀−mu = (x₀−a−ma, y₀−c−mc) — искомый. Какой случай осталось проверить, прежде чем разобраться со случаем с>a?

Пункт 4. Подсказка 6

Осталось только исключить случай x−a−ma =0! Разберём теперь c>a аналогично, просто по сути переобозначив переменные, закончив решение задачи!

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

1. Требуется исключить варианты $r=0,1,p− 1.$ Если существует $r$ -четверка $(a,b,c,d)$ при $r= 0,$ то $c$ натуральное кратное $p,$ и тогда $ab+cd> p$ — противоречие.

Пусть существует $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> p.$ Во втором же $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> p.$ Во втором же $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 + bd< cd + bc< cd + ba =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 (mod p).$ Отметим, что это множество вместе с каждым вектором $(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$ и обе координаты вектора $v 0$ по модулю не больше, чем $c$ — это опять противоречит выбору $u.$ Значит, $y < 0 0$ и $c− y > c. 0$ Теперь выберем наибольшее целое неотрицательное $m,$ при котором $x0− a− ma≥ 0.$ Ясно, что это неотрицательное значение строго меньше, чем $a.$ Тогда вектор

v0− mu = (x0 − a− ma,y0− c− mc)

и есть искомый вектор. Действительно, все нужные неравенства уже установлены, осталось только исключить случай $x − a− ma =0, 0$ но в таком случае из уравнения прямой $ℓ$ получаем $xc− ya= p,$ $− (y − c− mc )a =p, 0$ что невозможно в силу того, что $a> c> 0,$ $− y + c+mc ≥ 1+c +mc ≥2. 0$

Наконец обратимся к случаю $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, подсказка 1

Нас просят найти значения многочлена для графа К₄. Может, стоит подумать о его остовных деревьях?

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

В К₄ бывает только 2 вида остовных деревьев. Это либо цепь длины 4, либо три вершины, "висящие" на четвертой. А что нам дадут данные деревья в основный многочлен?

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

Остовные деревья первого вида дадут xᵢxⱼ, а второго - (xᵢ)², где i - вершина остова. Осталось только аккуратно записать искомый многочлен.

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

Для начала, как и в прошлом пункте, рассматриваем остовные деревья и записываем многочлен.

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

Проверьте, у Вас должен был получиться такой многочлен: x₁x₂x₃ + x₂x₃x₄ + x₃x₄x₅ + x₄x₅x₁ + x₅x₁x₂. Вспомните, какой граф мы называем "плохим"?

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

Заметим, что наш многочлен линеен по каждой переменной. Попробуйте показать, что у нас каждая переменная будет "жить" лишь в одной из скобок.

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

Убедитесь, что переменные разбиваются только на скобки вида 2-2-1 и 3-1-1. Что из этого следует?

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

Давайте подумаем, как связность U будет влиять на остовный многочлен?

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

Если U несвязно, то в качестве многочлена мы получим 0. А можем ли мы при связном U выкидывать по одной вершины с сохранением связности?

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

Давайте "подвесим" граф за множество U и будем удалять вершины, начиная с самого нижнего уровня. Что тогда получится?

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

Удалим вершину v. Это равносильно подстановке 0 в xᵥ. Какой вывод можно получить?

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

У нас получится, что все слагаемые c xᵥ обнуляются, следовательно, останутся лишь те, где v - висячая вершина. Как устроены такие деревья?

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

Мы выбираем дерево в графе G\{v}, а потом одна из вершин окрестности v соединяется с v. Какой вид у нас примет тогда остовный многочлен?

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

Докажите, что многочлен останется раскладываемым на множители.

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

Пусть G₁ - граф, получаемый из G на n вершинах добавлением вершины vₙ₊₁, как в операции раздвоения вершины. Давайте для начала подумаем про остовный многочлен графа G. Надо понять, как устроены деревья этого графа.

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

Возьмем лес на всех вершинах, кроме vₙ. Что обязательно должно быть в каждой его компоненте?

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

В каждой компоненте должна быть хотя бы одна вершина из окрестности vₙ в графе G. Как должна быть связана вершина vₙ с этим множеством?

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

vₙ будет соединена ровно с одной такой вершиной из каждой компоненты. Как тогда может быть представлен наш остовный многочлен?

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

Обозначьте за L множество таких лесов, за t(K) - число компонент связности в лесу K, за A₁, A₂, ... , Aₜ - множества пересечений окрестности вершины v в графе G с компонентами связности леса K. Запишите многочлен, пользуясь этими обозначениями.

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

Теперь посмотрим на деревья в графе G₁. Какой лес мы возьмем там?

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

Мы вновь возьмем лес, содержащий все вершины, кроме vₙ, но теперь еще не будем брать вершину vₙ₊₁. Снова подумаем, что должно быть в каждой его компоненте.

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

Как и ранее, в каждой компоненте должна быть хотя бы одна вершина из окрестности vₙ в графе G, после чего одна из долей будет соединена с вершинами vₙ и vₙ₊₁, а все остальные доли - лишь с одной из них. Теперь запишите и преобразуйте остовный многочлен графа G₁, используя те же обозначения, что и для графа G.

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

У Вас должно получиться, что для графа G₁ остовный многочлен от (x₁, x₂, ..., xₙ₊₁) равен остовному многочлену для графа G от (x₁, x₂, ..., xₙ + xₙ₊₁), умноженному на сумму вершин из окрестности vₙ в графе G.

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

Давайте теперь рассмотрим граф G₂, получаемый из G₁ соединением вершин vₙ и vₙ₊₁. Может быть, леса G₁ и G₂ похожи?

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

Мы снова рассмотрим лес, как с графом G₁, но теперь либо не будем проводить ребро между vₙ и vₙ₊₁, либо проведем и соединим каждую из долей ровно с одной из вершин. Какие выводы можно сделать из этих построений?

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

В первом случае мы получим такое же слагаемое, как в G₁. Тогда что нам дает сумма таких слагаемых?

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

Эти слагаемые дадут нам остовный многочлен графа G₁. Осталось только разобраться с суммой вторых слагаемых. Это можно сделать при помощи тех же обозначений, что и для графа G.

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

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$ устройство следующим образом — на всех вершинах, кроме $vn$ , берется некоторый лес, такой, что в каждой компоненте есть хотя бы одна вершина из $NG(vn)$ , и потом вершина $vn$ соединяется с ровно одной вершиной из каждой компоненты. Обозначим за $L$ множество всех таких лесов, за $t(K)$ — число компонент связности в лесу $K$ , и назовем $A1,A2,...At$ пересечения множеств $NG (v)$ с компонентами связности леса $K$ . Тогда из рассуждений выше

( ( ) ) ∑ ( ∏ degK(v)−1t(∏K)( ∑ ) t(K)−1) PG(x1,x2,...,xn) =K ∈L v∈V|v⁄=vnxv i=1 v∈Aixv xn .

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

$pict$

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

Лемма 2 (Лемма о раздвоении с добавлением ребра). Пусть дан граф $G,|G|= n$ . Рассмотрим граф $G2$ , получаемый из $G$ добавлением вершины $vn+1$ и соединением её со всеми вершинами из $NG(vn)$ , а также с самой $vn$ . Тогда

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

Доказательство. Пусть $G1$ — граф из леммы $1.$ Мы в лемме $1$ уже выяснили как устроены деревья в графе $G,$ поэтому нужно разобраться с тем, как они устроены в $G2$ . Заметим, что они устроены так: мы снова берем лес с такими же условиями, а дальше делаем одно из двух — либо не проводим ребро между $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, подсказка 1

Пусть G — вторая точка пересечения описанных окружностей △AEF и △ABD. Тогда чтобы показать, что G, E и D лежат на одной прямой, можно, например, показать равенство ∠AGE и∠AGD. Ведь нам дан факт про параллельность, которая как раз связана с углами.

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

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

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

Принадлежность к описанной окружности △ABD. Теперь стоит воспользоваться, что равнобедренные треугольники дают ещё достаточно равных отрезков, а также равные отрезки есть из симметричность. Тогда что можно сказать о окружности с центром в E и радиусом EB? Аналогично для точки F. Но как же воспользоваться этим фактом? Углы AED’ и AFD’ центральные, какие же равенства для них можно составить?

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

Что же даёт равенство углов в условии? Чем будут DF и DE для описанной окружности △AFE?

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

Конечно, XY — радикальная ось. Тогда можно посчитать степени точек для X и для Y. Из равенства для X, что можно сказать о 😆 и окружности, описанной около △AFD? 😆 — касается данной окружности, отсюда можно получить равенство для углов. Останется проделать аналогичные рассуждения для Y и проверить, чему равна сумма противолежащих углов XAYD.

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

Окружность описанная около △DEF повторно пересекает стороны BC, AC, AB в точках D', E', F' соответственно. Окружность △XYZ повторно пересекает стороны EF, DF, DE в точках X', Y', Z' соответственно. Что можно сказать о пересечение описанных окружностей △EX'Z', △FX'Y' и △DY'Z'. Они пересекаются в одной точки, пусть М. Выясните, каким ещё окружностям принадлежит точка М?

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

Очень много окружностей пересекающихся в М. Давайте сделаем инверсию φ в этой точке с произвольным радиусом. Какие подобные треугольнике теперь можно увидеть? Например, △AE'F' ~ △φ(X') φ(E) φ(F). Какие ещё два аналогичных подобия можно получить?

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

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, подсказка 1

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

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

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

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$ .

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