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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 2#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) Размыкаем синее рёбер в точке пересечения с красным, получаем две точки, соединим их какой-нибудь выпуклой красной кривой, поставим на ней пять точек и отметим "внутри"ещё две точки. Точки на кривой соединяем красными ребрами, а "внутрение"точки друг с другом синими. Осталось из внутренних провести два синих ребра, для этого соединим их точками с кривой.

Ответ:

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

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

Общий сюжет. Пусть $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$

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

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

Вася посмотрел на граф $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)

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

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

Нам нужно как-то оценить f. При этом в числителе мы видим сумму всех попарных произведений, а в знаменателе — сумму квадратов. Как можно связать квадраты и попарные произведения?

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

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

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

Внесём двойку под знак суммы. Получится, что числитель — это сумма всех возможных удвоенных произведений, каждое из которых не больше, чем сумма квадратов множителей. Оценим так каждое слагаемое. Сколько раз в итоговой сумме встретится квадрат каждого из чисел xᵢ?

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

Столько же, сколько каждое из чисел xᵢ встречается во всевозможных попарных произведениях! Или столько же, сколько рёбер выходит из вершины xᵢ.

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

Степень вершины равна количеству рёбер, выходящих из неё! Поэтому квадрат каждого числа в числителе встречается ровно d раз. Чему в таком случае равна вся дробь?

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

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

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

Подумаем, а что будет, если граф нельзя покрасить в [M]+1 цветов так, чтобы никакие две соседние вершины не были одноцветными?

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

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

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

Чему будет равно значение f, если в каждой вершине выбранного подграфа будет стоять единичка, а в остальных вершинах — ноль?

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

Верно, значение функции будет равно [M]+1. Постойте, а не противоречит ли это условию?

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

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

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

В задаче фигурирует клика — подмножество вершин графа, в котором любые 2 вершины соединены ребром. Будем рассматривать максимальную клику, ведь в ней как раз w вершин. Кажется, отделив вершины этой клики от остальных, гораздо проще придумать пример!

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

В вершины максимальной клики поставим 1/w, а в остальные вершины — 0. Тогда искомое значение Z действительно достигается! Ура, мы доказали, что есть такие расстановки (по крайней мере одна) при которых утверждение задачи верно! Теперь попробуем доказать, что при изменении такой расстановки утверждение остаётся верным! Не забудьте учесть, что сумма всех чисел на вершинах равна 1.

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

Обратите внимание на вершины, в которых стоит 0. Можно ли их просто убрать?

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

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

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

(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

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

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

На $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, сюжет 1 (см. yumsh.ru)

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

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

Для начала попробуйте подобрать такие наборы, у нас 2 карточки, на каждой по 2 числа.

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

Убедитесь, что наборы (1; 1/4) и (3/4; 1/2) подходят. Попробуйте провести оценку. Например, обязательна ли нам единица в одной из пар?

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

Набор с единицей должен быть, поскольку нам надо мажорировать (1; 0). Какой еще набор нам надо мажорировать и какие тогда карточки должны быть?

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

Нам также надо мажорировать (1/2; 1/2). Для этого на одной из карточек должны быть числа, большие 1/2. Что будет, если рассмотренные пары чисел с карточек совпадают?

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

Тогда их сумма — 3/2. Если это разные пары, посмотрите на набор (3/4; 1/4).

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

Для того, чтобы набор (1; x) его мажорировал, x должен быть больше либо равен 1/4. Осталось понять, какой набор нужен, чтобы набор с парой чисел, больших 1/2, мажорировал, и убедиться, что указанный пример подходит.

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

Попробуйте посмотреть, как можно записать число 1 + 10⁻¹⁰⁰ в виде суммы дробей.

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

Давайте добавим, что дроби у нас будут положительные и со знаменателем 10²⁰⁰. Что можно сказать о количестве таких записей?

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

Оно будет конечно. Тогда давайте обозначим его за n и запишем на карточки все соответствующие наборы. Подойдут ли нам такие карточки?

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

Рассмотрите произвольный набор с суммой 1 и замените в нем каждое число на ближайшую сверху дробь со знаменателем 10²⁰⁰. На сколько при округлении увеличится сумма?

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

Сумма увеличится не более, чем на 10¹⁰⁰ ⋅ (1 / 10²⁰⁰) = (1 / 10¹⁰⁰). Что мы тогда получим?

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

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

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

Можем увеличить числители некоторых дробей, чтобы сумма стала равной 1 + 10⁻¹⁰⁰. Осталось сделать вывод про мажорируемость.

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

Давайте сначала придумаем какой-то пример и прикинем возможные значения a(2,4).

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

Рассмотрите наборы (21/34; 1/2; 1/3; 1/4) и (1; 13/24; 13/68; 13/102). Чему равны их суммы? А чему равен √3?

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

Сумма в каждом наборе меньше 1,71, а √3 = 1,73... . Попробуйте проверить, что эта пара наборов мажорирует все четверки.

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

Пусть у нас есть упорядоченная тройка с суммой x. Что можно сказать про её среднее и меньшее числа?

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

Среднее число будет не больше x/2, а малое — не больше x/3. Распространите это наблюдение на четвёрки. Посмотрите на наборы, которые мы привели ранее.

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

На самом деле, аналогичное верно для четвёрок. Если максимальное число в четверке больше 21/34, то второе по величине будет не больше 13/34. Продолжите оценки на числа четвёрки и докажите, что приведённые 2 набора действительно мажорируют все четвёрки.

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

Нам нужно найти разность между двумя значениями функции a. Давайте для начала попробуем посчитать a(1,k). Вспомните, что мы знаем из прошлых пунктов о числах l≤k.

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

Для каждого такого l должна быть карточка, на которой l-ое по величине число не меньше, чем 1/l. Предположим, что такая карточка одна. Что можно сказать о сумме её чисел?

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

Сумма ее чисел будет не меньше 1 + 1/2 + ... + 1/k. А подойдет ли нам такая карточка?

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

Заметим, что в наборе с единичной суммой l-ое по величине число не больше 1/l, следовательно, карточка подойдет. А чему тогда будет равно a(1,k)?

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

a(1,k) = 1 + 1/2 + ... + 1/k. Давайте теперь рассмотрим произвольную пару натуральных чисел l < k и попробуем предъявить 2 набора, которые будут зависеть от k и l и мажорировать все наборы с единичной суммой.

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

Рассмотрим произвольный набор a₁ > a₂ > ... > aₖ с единичной суммой. Заметим, что для любого i aᵢ ≤ 1/i. Какой набор тогда будет мажорировать любой набор с единичной суммой, при условии, что все числа не превосходят 1/l?

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

Можно взять такой набор: в нем l раз встретится дробь 1/l, а также будут числа 1/(l + 1), 1/(l + 2), ... , 1/k. Осталось рассмотреть случай, когда a₁ > l. Попробуйте оценить сумму остальных aᵢ.

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

Это единичный набор, следовательно, a₂ + a₃ + ... + aₗ₊ᵢ < 1 - 1/l. Оцените aₗ₊ᵢ.

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

aₗ₊ᵢ ≤ (l - 1) / (l(l + i - 1)). Как, пользуясь этим соотношением, можно задать второй набор?

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

Второй набор будет следующего вида: (1; 1/2; ... ; 1/l; (l - 1) / l²; (l - 1) / (l(l + 1)); ... ; (l - 1) / (l(k - 1)). Попробуйте доказать, что разность между a(1,k) и наибольшей суммой одного из этих наборов может быть сколь угодно большой при правильном выборе l и k.

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

Посчитайте разницу между суммой с первой карточки и a(1,k).

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

Получим 1 + 1/2 + ... + 1/(l - 1) - (l - 1)/l. Заметьте, что эта сумма больше 1/2 + ... + 1/(l - 1).

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

При достаточно больших l эта сумма будет сколь угодно большой. Осталось посмотреть на вторую карточку.

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

У Вас должно получиться, что разность между a(1,k) и суммой чисел со второй карточки больше (1/l) ⋅ (1/(l+1) + 1/(l+2) + ... + 1/(k-1)) - 1. Осталось понять, ограниченно ли это число, и сделать соответствующие выводы.

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

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. нет