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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 3#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$ . Противоречие, следовательно, такое невозможно.