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

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

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

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

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

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

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

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

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

Задача 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$ в нижнем левом угле и затем умножить его на $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) Предположим, что это не так, то есть граф так покрасить нельзя. Тогда по теореме Брукса найдётся подграф, в котором степени вершин хотя бы $[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),$ то можно заметить $(xa,xb)$ на $(0,xa+ xb).$ Общая сумма не измениться, а $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$ максимальной антиклики.

1 S(A)> 1− w-

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

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

Ответ:

(a) d

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

Задача 4#108600

На $n$ карточках написали по $k$ чисел, сумма на каждой карточке равна $m$ . Оказалось, что любой набор из $k$ неотрицательных чисел с суммой 1 можно получить, уменьшив некоторые числа на одной из карточек (наборы неупорядоченные). Пусть $a(n,k)$ — наименьшее $m$ , при котором это возможно.

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

2. Докажите, что найдется $n$ такое, что $a(n,10100) ≤1+ 10−100$ .

3. Докажите, что $a(2,4)<√3-$ .

4. Ограничена ли последовательность $a(2,k)− a(1,k)$ ?

Источники: Изумруд - 2020, 11.3 (см. izumrud.urfu.ru)

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

1. Пример: наборы ( $1;14$ ) и ( $34;12$ ).

Оценка. Ясно, что должен быть набор, содержащий 1, чтобы мажорировать ( $1;0$ ), и набор, в котором оба числа больше $12$ , чтобы мажорировать $( ) 12;12$ . Если это одна и та же пара, то сумма уже $32$ . Если разные, то посмотрим на набор $( ) 34;14$ : чтобы набор $(1;x)$ мажорировал его, должно быть $x ≥ 14$ , а чтобы набор с парой чисел, больших $12$ мажорировал — это должен быть набор, как минимум $( ) 34;12$ . Легко видеть также, что указанный набор подходит.

_________________________________________________________________________________________________________________________________________________________________________________

2. Рассмотрим все возможные способы записать число $1+ 10− 100$ в виде суммы положительных рациональных дробей со знаменателем $10200$ (не обязательно несократимых). Очевидно, что это количество конечно, его и обозначим за $n$ — записав все соответствующие наборы на карточки, убедимся, что такой набор карточек подходит. Действительно, рассмотрим любой набор с единичной суммой. Заменим в нём каждое число на ближайшую сверху дробь со знаменателем $10200$ . При таком округлении сумма увеличится не более, чем на $10100⋅--1200 = 1∕10100 10$ , значит получится один из наших наборов или аналогичный набор с меньшей суммой. Произвольно увеличив числители некоторых дробей так, чтобы сумма стала равной $1+10−100$ , мы превратим набор в числа на одной из карточек, которая, таким образом, мажорирует исходный набор с единичной суммой.

_________________________________________________________________________________________________________________________________________________________________________________

3. Рассмотрим, например, следующую пару наборов:

( ) ( ) 2314,12,13,14 и 1,1334,1638, 11032 .

Сумма в каждом равна $324704-$ , это даже меньше,чем 1,71 , а $√3-= 1,73...$ . Проверим, что эта пара наборов мажорирует все нужные четвёрки. Ясно (*), что в упорядоченной тройке с суммой $x$ среднее число - не больше, чем $x2$ , а малое - не больше, чем $x3$ ; аналогичное верно для четвёрок. Действительно, если максимальное число в четвёрке больше $2314$ , то второе по величине - не больше,чем $1334$ , третье не больше $1638$ а самое маленькое не больше $11302$ , значит такая четверка мажорируется вторым набором. Аналогично, если максимальное число не больше, чем $21 34$ , то оно мажорируется первым набором.

_________________________________________________________________________________________________________________________________________________________________________________

4. Вычислим $a(1,k)$ . Как уже отмечалось, для всякого $l≤ k$ должна быть карточка, в которой $l$ -ое по величине число не меньше, чем $1 l$ . Если карточка всего одна, то сумма на этой карточке, таким образом, не меньше $1 1 1+ 2 + ...+ k$ . С другой стороны, карточка $( 1 1) 1,2,...,k$ , очевидно, подходит, т.к. в наборе с единичной суммой $l$ -ое по величине число не больше $1 -l$ , так что $1 1 a(1,k)=1 +2 +...+k$ . Теперь рассмотрим произвольную пару натуральных чисел $l<k$ , соотношение между которыми мы уточним позднее, и предъявим два набора, вдвоём мажорирующих все наборы с единичной суммой: а именно

1 1 1 --1- -1---1-- 1 (◟l,l,.◝◜..,l◞,l+ 1,l+2,l+ 3,...,k) lраз

( 1 1 1 l− 1 l− 1 l− 1 l− 1 ) 1,2,3,...,l,-l2-,l(l+1),l(l+2),...,l(k−-1)

Действительно, рассмотрим любой упорядоченный по убыванию набор ( $a1 ≥ a2 ≥ ...≥ ak$ ) с единичной суммой. Ясно, что $ai ≤1∕i$ при любом $i$ и поэтому первая карточка мажорирует любой набор с единичной суммой, в котором все числа не превосходят $1∕l$ .

Пусть, напротив, $a1 > 1l$ . Тогда для любого $i$ имеем

a2+ a3+ ...+al+i < 1− 1, откуда al+i ≤--l−-1--. l l(l+ i− 1)

Поэтому любой набор с $1 a1 > l$ мажорируется второй из наших карточек.

Осталось убедиться, что разность между $a(1,k)$ и максимумом из сумм в этих двух наборах может быть сделана (при подходящем выборе $l$ и $k$ ) сколь угодно большой. Действительно, сумма на первой карточке отличается от $a(1,k)$ на

1 1 l− 1 1 1 1+ 2 +...+l−-1 −--l-> 2 + ...+ l−-1

и эта величина при достаточно больших $l$ может быть сделана, как известно, сколь угодно большой. Теперь зафиксируем произвольное $l$ и посмотрим на вторую карточку: сумма чисел на ней меньше, чем $a(1,k)= 1+ 12 + ...+ 1k$ , на

( ) --1-+ -1--+⋅⋅⋅+ 1− l− 1 1 +--1-+ ...+ -1-- = l+ 1( l+2 k l l) l+ 1 k−( 1 ) = 1 -1--+ -1--+⋅⋅⋅+--1- + 1− l−21> 1 -1--+--1-+ ...+ -1-- − 1 l l+ 1 l+2 k − 1 k l l l+1 l+ 2 k− 1

Поскольку выражение в скобках при фиксированном $l$ и неограниченном $k$ может быть сделано сколь угодно большим, то можно выбрать $k$ так, что эта разность будет больше разности между $a(1,k)$ и первой суммой, которая одним лишь выбором $l$ может быть сделана сколь угодно большой для произвольного $k> l$ . Утверждение доказано, последовательность из условия не ограничена.

Ответ:

1. $5 4$

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

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

4. нет