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

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

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

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

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

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

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

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

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

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

Задача 1#83387Максимум баллов за задание: 7

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

Пусть $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Максимум баллов за задание: 7

Дан граф $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Максимум баллов за задание: 7

Будем называть треугольник $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

Показать, что точка лежит на пересечении двух окружностей можно, если показать принадлежность данной точки к обоим окружностям по отдельности.
Принадлежность к описанной окружности △AEF. Равнобедренные треугольники дают достаточно равных углов, а ещё точка, симметричная D относительно EF, составляет такой же угол с отрезком EF, что и сама D. А дальше Вам поможет счёт углов.

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

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

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

Что же даёт равенство углов в условии? Чем будут DF и DE для описанной окружности △AFE?
Рассмотрите D как окружность нулевого радиуса, что тогда будет радикальной осью для неё и окружности, описанной около △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). Какие ещё два аналогичных подобия можно получить?
Осталось только посмотреть, куда угол между описанными окружностями △ABC и △DEF перейдёт после инверсии и чему этот угол равен из подобия.

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

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Максимум баллов за задание: 7

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

Пункт 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$ .

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

Задача 5#139297Максимум баллов за задание: 7

Вася нашёл кубический граф (все степени вершин равны трём) и нарисовал его на плоскости без самопересечений так, что все рёбра являются отрезками, параллельными прямым $l1,$ $l2,$ $l3,$ причём рёбра, исходящие из одной вершины, параллельны разным прямым. Петя покрасил каждое ребро в красный или синий цвет так, что если три отрезка образуют «клювик», то центральное ребро одного цвета, а крайние другого, а если «треножку», то все цвета одинаковые.

$PIC$

1) Приведите пример получившейся картинки.

2) Покажите, что Васин граф — двудольный.

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

4) Вася нашёл кубический граф посложнее, и нарисовал его с некоторыми пересечениями ребер. Пете всё равно удалось раскрасить ребра требуемым образом, при этом в его раскраске пересекаются только рёбра разных цветов. Вася накрыл каждое пересечение рублёвой монеткой, под которой не оказалось точек из других рёбер. Докажите, что теперь Вася сможет перерисовать картинку только под монетками так, чтобы она снова удовлетворяла преамбуле (изменив соответствующий граф).

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

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

1) Рассмотрим красный шестиугольник и концентрический синий шестиугольник внутри него. Соединим соответственные вершины синими ребрами.

2) Без потери общности можно считать что углы между прямыми содержащими ребра расположены под углами в $∘ 60$ друг к другу. Рассмотрим произвольный цикл, он является $N$ -угольником. Рассмотрим некоторый угол этого $N$ -угольнка, если он равен $∘ 60$ или $∘ 300 ,$ то примыкающие стороны разноцетны, если же $∘ 120$ или $∘ 240 ,$ то ребра одноцветны. Из соображений чётности получаем, что углы $∘ 60$ и $∘ 300$ встречаются четное число раз, поэтому сумма углов делится на $∘ 120 ,$ но с другой стороны сумма углов $180(N − 2).$ Получили, что $N$ чётное, значит, все циклы имеют сётную длины, а это критерий двудольности.

3) Пусть в графе $n$ вершин, тогда ребер $3n -2 ,$ из формулы Эйлера граней $n 2 + 2.$ Посмотрим на грань, так как это цикл, он разноцветный, это происходит только грань содержит угол в $60∘$ , из соображений четности из предыдущего пункта, этих клювика хотя бы два. Каждый клювик содержит ровно два угла по $60∘,$ это позволяет оценит количество клювиков через число граней. Получили, что клювиков хотя бы $n2 + 2,$ а это больше половины от числа вершин.

4) Размыкаем синее рёбер в точке пересечения с красным, получаем две точки, соединим их какой-нибудь выпуклой красной кривой, поставим на ней пять точек и отметим "внутри"ещё две точки. Точки на кривой соединяем красными ребрами, а "внутрение"точки друг с другом синими. Осталось из внутренних провести два синих ребра, для этого соединим их точками с кривой.

Ответ:

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