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

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

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

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

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

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

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

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

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

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