Тема Графы и турниры

Считаем рёбра

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

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

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

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

Подтемы раздела графы и турниры

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

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

Задача 1#118955

На олимпийские игры приехали спортсмены из нескольких стран. Каждый участник пожал руку всем участникам из других стран (участники из одной страны друг другу руки не жали). При этом оказалось, что количество рукопожатий между спортсменами одного пола отличается от количества рукопожатий между спортсменами разного пола не более чем на $1.$ Как ни странно, число мужчин и женщин среди участников различается тоже не больше чем на $1.$ Какое наибольшее количество стран могло отправить на игры нечётное число спортсменов?

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

Оценка. Обозначим через $n$ количество стран, а через $a i$ и $b i$ — количество мужчин и женщин в $i$ -й стране соответственно. По условию

∑ | (aiaj + bibj − aibj − biaj)|≤1

Заметим, что

∑ ∑ 2 ∑ 2 ∑ 2 ∑ 2 2 (aiaj + bibj)= ( ai) + ( bi) − ai − bi

∑ ∑ ∑ ∑ 2 (aibj +biaj)= 2( ai)( bi)− 2aibi

Значит,

∑ ∑ ∑ |( ai− bi)2− (ai− bi)2|≤ 2

По условию $∑ ∑ ( ai− bi)2 ≤ 1,$ поэтому $∑ (ai− bi)2 ≤ 3.$ Заметим, что если из $i$ -й страны приехало нечётное число участников, то $(ai− bi)2 ≥ 1.$ Следовательно, стран с нечётным числом участников не более трёх.

Пример. Пусть стран всего три, из двух приехало по одному мужчине, а из третьей — одна женщина.

Ответ:

$3$

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

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

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

Задача 2#120781

В стране $101$ город. Некоторые города соединены дорогами с односторонним движением, причём в каждый город входит $40$ дорог и из каждого города выходит $40$ дорог. Докажите, что из каждого города можно добраться до любого другого, проехав не более чем по трём дорогам.

Показать доказательство

Рассмотрим произвольные города $A$ и $B.$ Разделим все города на три группы: $X$ — $40$ городов, в которые ведут дороги из $A.$ $Y$ — $40$ городов, из которых есть дороги в $B$ (не включая сам $B).$ Если $A$ лежит в $Y$ или $B$ в $X,$ то можно добраться по одной дороге. Если $A$ пересекается с $B,$ то по двум. Если они не пересекаются, то выделим оставшиеся $19$ городов в группу $Z.$ Из $X$ выходит $40⋅40$ стрелок, из них не более $40⋅39 2$ лежат полностью в $X$ и не более $19⋅40$ ведут в $Z.$ Тогда найдется хотя бы

( 39 ) 40⋅ 40− -2 − 19 = 60

стрелок ведущих из $X$ в $Y$ или $B.$

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

Задача 3#121177

Предложите эффективный алгоритм для поиска максимального потока в графе с целочисленными весами, используя теорему Форда-Фалкерсона. Обоснуйте его корректность. Будет ли ваш алгоритм работать для вещественных весов?

Показать доказательство

Алгоритм Эдмондса-Карпа с обходом в ширину

Шаги алгоритма:

1.

Инициализация: поток $f(u,v)= 0$ для всех рёбер.

2.

Пока существует путь из истока $s$ в сток $t$ в остаточной сети $Gf :$

Найти кратчайший путь $P$ из $s$ в $t$ с помощью BFS (обход в ширину).
Увеличить поток вдоль $P$ на величину остаточной пропускной способности $cf(P)= min{cf(u,v)|(u,v)∈ P}.$
Обновить остаточную сеть $Gf.$

Корректность:

Теорема Форда-Фалкерсона: Поток максимален тогда и только тогда, когда в остаточной сети нет дополняющих путей, значит, пока поток не максимален, найдется путь, по которому мы увеличим поток.
Конечность: При целочисленных пропускных способностях каждый шаг увеличивает поток на целое число. Так как максимальный поток ограничен (например, суммой пропускных способностей рёбер из истока), алгоритм завершится за $∗ O (|f|⋅(|E|+ |V |))$ шагов, где $∗ |f |$ — значение максимального потока, и на каждом шаге мы заупскаем BFS.

Пример несходящегося алгоритма: Рассмотрим сеть с источником $s,$ стоком $t,$ рёбрами $e1,e2,e3$ и пропускными способностями:

√- c(e)= 1, c(e)= r= -5-− 1, c(e) =1, 1 2 2 3

а пропускные способности остальных рёбер равны целому числу $M ≥ 2.$

$PIC$

Константа $r$ удовлетворяет условию:

2 r =1 − r.

Используем пути в остаточном графе:

p = {s,v ,v,v,v ,t}, p = {s,v ,v,v,t}, p = {s,v ,v ,v,t}. 1 4 3 2 1 2 2 3 4 3 1 2 3


Шаг	Найденный путь	Добавленный поток	$e1$	$e2$	$e3$

0	—	—	$r0 =1$	$r$	$r$
1	${s,v ,v,t} 2 3$	1	$r0$	$r1$	$r1$
2	$p1$	$r1$	$r1$	$r2$	0
3	$p2$	$r1$	$r1$	$r2$	$r1$
4	$p1$	$2 r$	$2 r$	0	$3 r$
5	$p3$	$r2$	$r2$	$r2$	$r3$

После шагов $1$ и $5$ остаточные пропускные способности рёбер $e1,e2,e3$ имеют вид $n n+1 r ,r ,0,$ где $n ∈ℕ.$
Цикл из путей $p1,p2,p1,p3$ может повторяться бесконечно. Полный поток после шага $5:$
$1+ 2(r1+ r2).$
При бесконечном выполнении поток сходится к:
$∞∑ i 1+ 2i=1r= 3+ 2r,$
но максимальный поток равен $2M + 1.$

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

Задача 4#121645

В Нонквинтляндии $n$ городов, некоторые из которых соединены дорогами. Путешественник обнаружил, что невозможно проехать по пяти разным дорогами и вернутся в исходный город. Докажите, что в стране не более $n(n−1) 3$ дорог.

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

Источники: ИТМО-2025, 11.8(см. olymp.itmo.ru)

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

Подсказка 1

Глобально нас просят доказать, что количество рёбер не превосходит 2/3 от максимально возможного.

Подсказка 2

Для доказательства этого нужно как-то использовать, что в графе нет циклов длины 5. Попробуйте, используя это, доказать задачу про какой-то маленький подграф данного графа.

Подсказка 3

Попробуйте доказать это для любого подграфа из 6 вершин. Далее с помощью небольшого комбинаторного подсчёта докажите это для данного графа.

Показать доказательство

Будем называть замкнутый маршрут из пяти дорог, существование которого запрещено условием, 5-циклом.

Докажем сначала, что если мы рассмотрим какие-либо шесть городов, между ними будет проведено не более 10 дорог из возможных 15. Предположим противное: пусть между какими-то шестью городами проведено не менее 11 дорог. Тогда среди этих шести городов и соединяющих их дорог найдём 5-цикл, существование которого запрещено условием.

Нам достаточно доказать, что мы сможем найти 5-цикл, если дорог ровно 11. Действительно, если дорог больше 11, удалим лишние и докажем, что цикл из 5-цикл среди оставшихся дорог всё равно найдётся.

Для удобства, если какие-то два города не соединены дорогой, будем говорить, что они соединены антидорогой. Таким образом, мы хотим доказать, что мы сможем найти 5-цикл, если между шестью городами проведены ровно четыре антидороги.

Какие-то две антидороги точно выходят из одного города. Исключим его и рассмотрим оставшиеся пять городов. Пронумеруем их числами от 1 до 5. Между этими городами не более двух антидорог. Опять же, достаточно найти 5-цикл в ситуации, когда этих антидорог ровно две, в противном случае он найдётся и подавно.

Есть две возможных ситуации: когда эти антидороги имеют общий конец, и когда не имеют.

В первом случае без ограничения можно считать, что антидороги соединяют город 1 с городами 2 и 3. Тогда мы можем найти следующий 5-цикл: 1-4-2-3-5-1.

Во втором случае можно считать, что наши антидороги соединяют город 1 с городом 2, а город 3 с городом 4. Тогда мы сможем найти такой 5-цикл: 1-3-5-2-4-1.

Мы доказали, что среди любых 5 городов проведено не более 10 дорог из 15, то есть максимум $23$ от всех возможных дорог. Поскольку каждая пара городов с проведённой между ними дорогой или антидорогой входит в равное число таких шестёрок, поэтому общее количество дорог также составляет не более $23$ от максимально возможного, то есть максимум

2⋅ n(n−-1)= n(n−-1) 3 2 3

Докажем это чуть более строго. В каждой шестёрке городов не более 10 дорог. Всего этих шестёрок $C6n.$ Итого получаем $10C6n$ дорог, однако, каждая из них посчитана несколько раз. А именно, к каждой паре городов можно подобрать ещё 4 города $C4n− 2$ способами, значит, именно столько раз мы посчитали каждую дорогу.

Таким образом, всего дорог не более

10C6n 10⋅ n(n−1)(n−2)(n−3)(n−4)(n−5) n(n − 1) C4-- = ----(n−2)(n−3)(72n0−4)(n−5)-----= --3---- n− 2 24

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

Задача 5#125144

(a) В классе 30 учеников, у каждого ровно по 2 друга. Докажите, что можно организовать не менее 10 дежурств так, чтобы дежурили по двое друзей, и никто не дежурил дважды.

(b) Всегда ли можно организовать 11 дежурств?

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

Подсказка 1:

Нужно грамотно интерпретировать задачу на языке графов. Давайте считать учеников вершинами, а ребро будем проводить между теми, кто дружат. Как из помощью такого графа получить график дежурств?

Подсказка 2:

Как насчёт того, чтобы выкидывать из графа ребро, соединяющее учеников, которые вместе дежурят? Также выкинем вершины, соответствующие этим ученикам и другие рёбра, выходящее из них. Почему получится найти 10 дежурств?

Подсказка 3:

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

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

(a) Рассмотрим граф, в котором дети это вершины. Будем проводить ребро, если дети дружат. По условию все вершины имеют степень 2, значит, в графе 30 рёбер. Будем выбирать произвольное ребро, выкидывать вершины на его концах и все рёбра, исходящие из этих вершин. Так мы удалим не более 3 рёбер (поскольку степени вершин не превосходят 2, а одно из рёбер у этих вершин общее). Значит, если проделать такой процесс 9 раз, останется хотя бы 3 ребра, и удастся сделать десятый шаг. Составим пары для дежурств из учеников, соответствующих концам выбранных ребер. Тогда дежурят только друзья, и никто не дежурит дважды, поскольку мы сразу же удаляем вершины. Таким образом, мы выбрали 10 пар.

(b) Пусть граф состоит из 10 треугольников: компонент связности размера 3, каждая из которых является полным графом. Тогда степень каждой вершины равна 2, при этом дежурить должны дети из одного треугольника, каждый треугольник даёт только по одному дежурству (поскольку все дежурят не более одного раза), но треугольников всего 10, значит, 11 дежурств провести не получится.

Ответ:

(b) нет

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

Задача 6#125778

Докажите, что в графе с $n$ вершинами и $k$ ребрами число треугольников не меньше

k(4k−-n2) 3n .

Показать доказательство

Первое решение. Граф $G$ называется дополнительным для графа $G,$ если $G ′$ имеет то же множество вершин, что и $G,$ а ребро между вершинами $′ G$ проводится тогда и только тогда, когда в $G$ соответствующие вершины несмежны.

Назовём антитреугольником тройку вершин, которые не образуют треугольник. Оценим число антитреугольников. Всего антирёбер

n(n− 1) --2---− k= x

Пусть путей длины 2 в дополнительном графе $l,$ а треугольников в дополнительном графе $t.$ Каждое антиребро входит в $n− 2$ антитреугольника. Покажем, что антитреугольников всего $x(n − 2)− l+ t.$ Для этого заметим, что каждый антитреугольник $T$ учтён в этой сумме 1 раз. Действительно, если в $T$ одно антиребро, то мы посчитали его только в первом слагаемом. Если в $T$ два антиребра, то они образуют один путь длины 2, тогда $T$ учитывается в слагаемом $x(n− 2)$ дважды и вычитается один раз, благодаря вычитанию $l.$ Если же в $T$ три антиребра, то они образуют три пути и один треугольник и, следовательно, $T$ трижды учитывается в первом слагаемом, три раза вычитается, благодаря вычитанию $l,$ и учитывается еще 1 раз в слагаемом $t.$ Теперь оценим $3t≤l.$ Действительно, каждый треугольник содержит в себе 3 пути, а каждый путь лежит внутри одного треугольника. Значит, число антитреугольников не более $x(n− 2)+2l∕3.$

Пусть $di$ — степень $i$ -ой вершины в дополнительном графе. Каждый путь длины 2 содержит ровно одну центральную вершину, так что

l= ∑n di(di− 1) i=1 2

По неравенству о средних оценим

n ( ) ( ) ∑ di(di−-1) ≥n 2x- 2x − 1 =2x 2x− 1 i=1 2 n n n

Тогда всего антитреугольников не более, чем

( ) (n − 2)x− 2x 2x − 1 3 n

Подставляя в оценку из условия $x$ вместо $k,$ получаем:

(n − 2)x− 2x( 2x-− 1) + k(4k−-n2)= 3 n 3n

6n(n− 2)x− 4x(2x− n)+ (n2− 2n − 4x)(n2− n− 2x) = -------------------6n--------------------=

= n(n-− 1)6(n-− 2)

Мы добавили к требуемой оценке число, которое не меньше числа антитреугольников, и получили в точности количество всех троек вершин. Значит, треугольников не меньше $k(4k3−nn2),$ что и требовалось.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Пусть $d(n)$ — степень $n$ -ой вершины графа. Рассмотрим ребро $xy,$ количество треугольников $Txy,$ в которые данное ребро входит, равно числу общих соседей вершин $x,y.$ Пусть $Mxy$ — число вершин, смежных с $x$ или $y.$ Очевидно, что $Mxy ≤ n.$ Тогда по формуле включения-исключений имеем:

Txy = d(x)+ d(y)− Mxy ≥ d(x)+ d(y)− n.

Суммируя по всем ребрам и учитывая, что каждый треугольник считается трижды, общее число треугольников $T$ не меньше

∑ T ≥ 1 (d(i)+ d(j)− n). 3ij∈E(G)

Каждый $d(i)$ появляется каждый раз, когда $i$ является концом ребра из $E(G)$ , то есть $d(i)$ раз; всего пар $k$ , значит $n$ вычитается $k$ раз. По неравенству Коши–Буняковского:

( ) ( (∑ )2 ) 1( ∑ 2 ) 1| ---i∈V(G)d(i)-- | T ≥ 3 i∈V(G)d(i) − kn ≥ 3( n − kn) .

Наконец, сумма $∑i∈V(G)d(i)= 2k.$ Следовательно,

T ≥ 1( (2k)2− kn)= 4( 4k−-n2). 3 n k 3n

Курсы

Всё необходимое для достижения цели

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

Задача 7#126072

В математическом лагере у каждого участника есть $22$ друга (если $a$ дружит с $b$ , то и $b$ с $a).$ При этом, если какие-то два участника дружат, то общих друзей у них нет, а если не дружат, то у них ровно $6$ общих друзей. Сколько человек в математическом лагере?

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

Рассмотрим граф, в котором вершины — участники лагеря, а рёбра означают дружбу.

Посчитаем число троек $(u,v,w ),$ где $u$ дружит с $v$ и с $w,$ а $v$ и $w$ не дружат.

С одной стороны, у каждого участника $2 C 22$ таких троек, всего $2 n⋅C22.$ С другой стороны, каждая пара недрузей имеет $6$ общих друзей, значит, таких троек в $6$ раз больше числа пар недрузей. Таких пар:

n(n − 1− 22) ----2-----

Имеем:

n⋅C222 =3 ⋅n(n− 1− 22) ⇔ 11 ⋅7 =n − 23⇔ n = 100.

Ответ:

100

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

Задача 8#79743

В стране $1001$ город, любые два города соединены дорогой с односторонним движением. Из каждого города выходит ровно $500$ дорог, в каждый город входит ровно $500$ дорог. От страны отделилась независимая республика, в которую вошли $668$ городов. Докажите, что из любого города этой республики можно доехать до любого другого ее города, не выезжая за пределы республики.

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

Подсказка 1

Предположим противное, то есть из города X нельзя добраться до Y по городам республики. Разбейте республику на 2 части, как-то связанные с X.

Подсказка 2

Разбейте республику на 2 множества городов. До первых можно доехать из X, а до вторых - нет(туда войдет Y). Тогда все дороги направлены из второго множества в первое. Поймите на языке алгебры, что такое невозможно.

Показать доказательство

Предположим, что утверждение неверно; скажем, из города $X$ нельзя добраться до $Y$ по городам республики.

Обозначим через $A$ множество всех городов республики, до которых можно добраться из $X$ по городам республики (включая сам город $X$ ), а через $B$ — множество всех остальных её городов (оно непусто, так как содержит $Y$ ). Тогда города республики разбились на две группы так, что все дороги между группами направлены от $B$ к $A.$

Обозначим количество городов в группах $A$ и $B$ через $a$ и $b$ соответственно, $a+ b= 668.$ Пусть в $A$ городов не меньше, чем в $B,$ то есть $a≥ 334≥ b.$ В $B$ есть город Z, из которого выходит не менее $1 b− 2$ дорог в города из $B.$ Кроме того, из $Z$ выходит $a$ дорог к городам группы $A.$ Значит, из $Z$ выходит не менее $b−1- a+(a+b)−1- a+667 1001 a + 2 = 2 = 2 ≥ 2 > 500$ дорог. Противоречие.

Случай, когда в $B$ больше городов, чем в $A,$ рассматривается аналогично.

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

Задача 9#82621

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

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

Подсказка 1

Сначала можно заметить, что 64 короля выставлено быть не может! Как доказать этот факт?

Подсказка 2

Верно! С одной стороны, если считать королей вершинами, а ребрами показывать отношение "один король бьет другого", то ребер в таком графе четное число. А как их посчитать по-другому?

Подсказка 3

Точно! Всякий раз мы добавляем нечетное число ребер в граф 63 раза, то есть их количество нечетно! Итак, всего королей не более 63. А какой пример подойдет?

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

Для начала покажем, что $64$ поставить не получится. Предположим, что мы смогли это сделать. Рассмотрим граф, в котором короли — это вершины. Рёбрами соединим королей, которые друг друга бьют. Тогда, с одной стороны, мы получили граф, в котором $36⋅8+24⋅5+4⋅3 2 = 210$ рёбер (потому что все короли бьют всех королей на всех соседних клетках). С другой же стороны, каждый раз добавляя очередного короля (кроме первого), мы добавляли в граф нечётное количество рёбер. В граф нечётное количество раз ( $63$ ) было добавлено нечётное количество рёбер. Значит, количество рёбер в графе должно быть нечётным. Пришли к противоречию.

Теперь приведём пример на $63.$ Нужно ставить королей в следующем порядке на клетки с координатами:

(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),(8,8),(1,3)

(1,2),(1,4),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8),(2,4)

(2,5),(3,5),(1,5),(2,6),(3,7),(3,6),(4,7),(4,6),(5,7)

(5,8),(6,8),(2,8),(3,8),(4,8),(2,7),(1,7),(1,6),(1,8)

(2,1),(4,2),(3,2),(5,1),(4,1),(3,1),(4,3),(5,3),(5,2)

(5,4),(8,7),(7,5),(6,5),(8,5),(7,6),(8,6),(6,4),(7,3)

(7,4),(8,2),(8,3),(8,4),(7,2),(6,1),(7,1),(8,1),(6,2)

Ответ:

$63$

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

Задача 10#87413

В стране $400$ городов. Некоторые из них соединены авиалиниями, а некоторые нет. Известно, что для любых $200$ городов найдётся $300$ пар городов, не соединённых авиалиниями. Какое наибольшее количество авиалиний может быть в стране?

Источники: СПБГУ - 2024, 11.5 (см. olympiada.spbu.ru)

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

Подсказка 1

Переведем задачу на язык графов. Нам нужно придумать, как использовать условие на 200 городов. А что если взять какие-нибудь особенные 200 городов?

Подсказка 2

Рассмотрим подграф А из 200 вершин с наибольшим количеством рёбер и подграф В из оставшихся 200 вершин. Нам нужно как-то оценить количество ребер между А и В. Что можно сказать о степенях вершин в В? А в А?

Подсказка 3

Рассмотрим вершину из А, соединенную с наименьшим количеством вершин (в А). Пусть такая ее степень это х. Какие тогда степени могут иметь вершины из В?

Подсказка 4

Ни одна вершина в В не может быть соединена хотя бы с х+1 вершиной в А. Как тогда оценить количество рёбер между А и В? Нам надо сделать его как можно больше.

Подсказка 5

Между этим графами не более, чем 200*х рёбер. А в подграфах сколько ребер может быть максимально?

Подсказка 6

Не более, чем 2*19600. Итак, теперь нам надо оценить х. Как это можно сделать?

Подсказка 7

Если х — это наименьшая степень вершины в х, то сколько рёбер может быть в А?

Подсказка 8

Не менее, чем 100х. Осталось лишь оценить х, используя полученные оценки на подграф А ;) не забываем про пример!

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

Рассмотрим граф, в котором города — вершины, а авиалинии — рёбра. Рассмотрим подграф $A$ из $200$ вершин с наибольшим количеством рёбер и подграф $B$ из оставшихся $200$ вершин.

Пусть вершина $X$ из подграфа $A$ соединена с наименьшим количеством вершин в этом подграфе ( $x$ вершин). Предположим, что в подграфе $B$ имеется вершина $Y$ , которая соединена с хотя бы $x+ 1$ вершиной из подграфа $A$ . В таком случае вершину $Y$ можно переместить в подграф $A$ вместо вершины $X$ и в нём будет больше авиалиний, что противоречит выбору подграфа $A$ . Следовательно, любая вершина из подграфа $B$ связана не более чем с $x$ вершинами из подграфа $A$ .

Значит, между этими подграфами не более $200x$ рёбер. Внутри же каждого из этих подграфов не более $200⋅199 --2--− 300 =19600$ рёбер. Значит, всего в графе не более $2⋅19600+ 200x= 39200 +200x.$

Как известно, $x$ — это наименьшая степень вершины в подграфе $A$ . Значит, в $A$ не менее $200x --2 = 100x$ рёбер. С другой стороны, в этом подграфе не более $19600$ рёбер, откуда $x≤ 196$ . Теперь мы можем оценить количество рёбер в графе: $39200 +200x≤ 78400$ .

_________________________________________________________________________________________________________________________________________________________________________________

Приведём пример на $78400$ рёбер. Разбиваем города на $50$ групп по $8$ городов. Внутри групп между городами авиалиний нет, а между городами из разных групп — есть.

Пусть выбрано $200$ городов так, что из них $a1$ город из первой группы, $a2$ из второй, $...$ , $a50$ — из $50$ -й. Тогда количество пар, не соединённых авиалиниями, будет не менее

a (a − 1) a (a − 1) a (a − 1) (a2+ a2 +...+ a2)− (a +a + ...+ a ) (a2+ a2 +...+ a2)− 200 -1--12---+ -2-22---+ ...+ -50--502----= --1--2-------50-2-1---2-------50-= --1--2----2--50-----

по неравенству между средним квадратическим и средним арифметическим

(a21-+a22+-...+-a250)−-200-≥ 800−-200= 300 2 2

Мы показали, что для произвольного подграфа в примере выполняется условие задачи.

Ответ: 78400

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

Задача 11#88469

В клетчатом квадрате $10× 10,$ вначале пустом, Жанна закрашивает по одной клетке, вписывая в каждую только что закрашенную клетку количество граничащих с нею (по стороне) ранее закрашенных клеток. Чему будет равна сумма всех чисел в квадрате, когда будут закрашены все клетки?

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

Подсказка 1

Пусть вершины — закрашенные клетки, а ребра — общие стороны закрашенных клеток. Что происходит с графом, когда мы закрашиваем одну клетку?

Подсказка 2

Подумайте, как соотносятся количество ребер в нашем графе с суммой чисел из условия в любой момент времени?

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

Пусть клетки будут вершинами, а общие границы у клеток — рёбрами, соединяющими их. Изначально в графе нет вершин и мы добавляем новую вершину и записываем в неё количество рёбер, добавленных в граф. Это количество равно количеству границ между клетками, то есть $180.$

Ответ:

$180$

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

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

Задача 12#92120

План замка — многоугольник, разделенный на $10$ одинаковых комнат в форме правильного треугольника со стороной $1$ (из каждой комнаты можно попасть в любую другую). Соседние комнаты прилегают друг к другу сторонами. Каков наибольший возможный периметр замка?

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

Подсказка 1

Попробуем ввести графовую интерпретацию: треугольники-комнаты — это вершины, а ребра проводятся, если комнаты являются соседними. Какое тогда будет наименьшее число ребер в таком графе?

Подсказка 2

Конечно, 9, поскольку всего комнат 10, а граф, по условию, связен! А как можно по-другому выразить периметр замка через ребра и вершины?

Подсказка 3

Верно! Для периметра надо посчитать "внешнюю рамку" этих треугольников, а оно равно утроенному числу вершин минус удвоенному числу ребер (каждое ребро означает внутреннюю стену замка, каждая из которых учитывается по два раза, а вершины просто означают три стороны комнаты). Как теперь оценить максимальный периметр?

Подсказка 4

Конечно, теперь все просто, ведь у нас ровно 10 вершин, а ребер не менее 9, так что периметр не превосходит 3 * 10 - 2 * 9 = 12. А как должны быть расположены комнаты, чтобы достигнуть равенства 12?

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

Рассмотрим граф, вершины которого олицетворяют комнаты замка, а ребро присутствует между двумя вершинами, если соответствующие им комнаты являются соседними. Из условия о том, что из каждой комнаты можно попасть в любую другую следует, что граф связен. Тогда рёбер в нём хотя бы уменьшенное на $1$ число вершин, то есть хотя бы $9.$ Заметим, что периметр замка — утроенное число вершин (суммарное число сторон комнат) минус удвоенное число рёбер (стороны, которые не должны учитываться в периметре, но нами посчитаны соответственно для двух комнат). Эта величина максимум $10⋅3− 9 ⋅2 =12,$ равенство достигается при треугольничках в ряд (последовательно повёрнутые в разные стороны).

Ответ:

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

Задача 13#93664

В особой больнице есть главврач и много пациентов. В течение недели каждый пациент один раз в день кусал кого-нибудь (возможно и себя). В конце недели оказалось, что у всех пациентов по $2$ укуса, а у главврача — $100$ укусов. Сколько в больнице пациентов?

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

Подсказка 1

Попробуем перевести задачу на язык графов. Что можно считать ребрами, а что вершинами?

Подсказка 2

Верно! Будем считать, что вершинами являются пациенты и главврач, а ребра будем ставить ориентированные: от кусающих к укушенным. Конечно, в этом графе могут возникнуть петли и кратные ребра. А сколько новых ребер в графе прибавляется за 1 день?

Подсказка 3

Конечно! Пусть всего n пациентов. Каждый день появляется n новых укусов, поэтому каждый день получаем n новых ребер. Тогда в конце недели будет ровно 7n ребер в графе. А как еще можно посчитать число ребер?

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

Рассмотрим ориентированный граф, в котором вершины — пациенты и главврач, а ребра идут от кусающих к укушенным. Пусть всего пациентов $n.$ Тогда в этом графе каждый день в течение недели прибавлялось $n$ новых ориентированных ребер (допускаются кратные ребра и петли), поэтому, спустя $7$ дней, этих ребер стало $7n.$ С другой стороны, в конце недели каждый пациент имел $2$ укуса, а главврач — $100$ укусов, следовательно, в конце недели в графе стало $2n+ 100$ ориентированных ребер. Тогда получаем уравнение

7n =2n +100

n =20

Ответ:

$n =20$

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

Задача 14#93849

(a) Известно, что в компании каждый человек знаком более, чем с половиной присутствующих. Докажите, что можно выбрать из этой компании трёх попарно знакомых человек.

(b) Известно, что в компании каждый человек знаком не менее чем с половиной присутствующих. Докажите, что можно выбрать из компании четырех человек и рассадить за круглым столом так, что при этом каждый будет сидеть рядом со своими знакомыми.

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

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

Здесь есть смысл рассмотреть произвольного человека A и его знакомых и попытаться найти среди них нужный треугольник.

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

Стоит обратить внимание на то, что если какие-то два знакомых A знакомы, то задача решена.

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

Попробуйте рассмотреть двух произвольных людей. Если найдете у них двух общих знакомых, то дело в шляпе.

Показать доказательство

(a) Рассмотрим произвольного человека $A.$ Пусть он знаком с людьми $A1,A2,...,Ak.$ Заметим, что если какие-то $Ai$ и $Aj$ дружат, мы нашли треугольник $A1AiAj.$ Предположим, что они между собой не дружат. Пусть всего в компании $n$ человек. Тогда каждый $Ai$ человек может дружить не более чем с $1 +(n− k− 1) =n − k$ людьми. Учитывая, что $n k > 2,$ получаем противоречие.

(b) Рассмотрим двух незнакомых людей $A$ и $B$ (если таких нет, то все всех знают, то есть условие выполнено). Предположим, что у них нет двух общих знакомых, тогда они суммарно знакомы не более чем с $n − 1$ людьми, что неверно, потому что по условию они знакомы с хотя бы $n$ людьми. Значит, у них есть двое общих знакомых. Их и возьмём вместе с $A$ и $B.$

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

Задача 15#93852

В Джиннистане живут маги. Каждый маг дружит ровно с $10$ другими магами; для любых $10$ магов найдется маг, который дружит с каждым из этих $10.$ Сколько магов может быть в Джиннистане?

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

Подсказка 1

Подумайте, а сколько вообще может быть магов. Ясно, что их хотя бы 11. Может ли быть ровно 11? А больше 11?

Подсказка 2

Вероятно вы придумали пример на 11 и теперь думаете насчёт того, может ли быть больше 11. Попробуйте обратиться внимание на то, что каждой десятке магов сопоставлен какой-то маг, притом один маг не может быть сопоставлен двум разным десяткам.

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

Пусть всего магов $n.$ Очевидно, $n ≥11.$ Случай $n =11$ реализуется, когда все маги дружат между собой. Докажем, что случай $n> 11$ невозможен. По условию задачи каждой десятке магов сопоставлен маг, который дружит со всеми магами этой десятки. Разным десяткам сопоставлены разные маги, так как каждый маг дружит ровно с $10$ другими магами. Значит, разных десяток магов не более $n.$ Но это очевидно не так: расставив магов по кругу и для каждого мага рассмотрев десятку, состоящую из него и следующих девяти по часовой стрелке, мы получим $n$ десяток. При этом есть десятка, не вошедшая в эти $n$ — например, если считать по кругу, первые пять и с седьмого по одиннадцатого.

Ответ:

$11$ магов

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

Задача 16#118949

В графе $300$ вершин, и никакие две вершины одинаковой степени не соединены ребром. Какое наибольшее количество рёбер может быть в этом графе?

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

Оценка. Зафиксируем натуральное число $k.$ Рассмотрим в графе все вершины степени $k.$ Они не соединены между собой, поэтому оставшихся вершин хотя бы $k.$ Тогда вершин степени $k$ не больше, чем $300− k.$ Значит, всего рёбер в графе не более, чем

1 2(299+ 298⋅2+297⋅3+ ...+ 276⋅24)= 42550.

Пример. Разобьём $300$ вершин на группы. В первой группе $1$ вершина, во второй — $2$ вершины, $...,$ в последней — $24$ вершины. Пусть любые две вершины из разных групп будут соединены ребром, а вершины из одной группы — нет. Тогда в первой группе будет одна вершина степени $299,$ во второй — $2$ вершины степени $298,$ $...,$ $24$ вершины степени $276.$ Получается, что суммарное количество рёбер вычисляется по формуле из оценки, то есть равно $42550.$

Ответ:

$42250$

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

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

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

Задача 17#67680

В выпуклом многограннике обозначим через В, Р и Т соответственно число вершин, рёбер и максимальное число треугольных граней, которые имеют общую вершину. Докажите, что

√ ----- В Р+ Т≥ 2Р

Например, для тетраэдра ( $В= 4,Р= 6,Т = 3)$ выполняется равенство, а для треугольной призмы ( $В =6,Р= 9,Т= 1)$ или куба ( $В= 8,Р= 12,Т = 0)$ имеет место строгое неравенство.

Источники: ММО-2023, 11.5 (см. mmo.mccme.ru)

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

Подсказка 1

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

Подсказка 2

Эта сумма m_1+...+m_k не больше Р+Т, потому что мы могли максимум Т рёбер посчитать дважды.

Подсказка 3

Но нам нужен корень из Р+Т, его можно получить с помощью неравенства о средних. Как его применить?

Подсказка 4

Применим неравенство между средним квадратическим и средним арифметическим для набора sqrt(m_1), ..., sqrt(m_k).

Подсказка 5

Итак, мы получили неравенство, которое удобно переписать в виде sqrt(m_1/k)+...+sqrt(m_k/k)<=sqrt(Р+Т). Теперь давайте рассмотрим все пары вершин. Пусть степени некоторых двух равны x и y. Тогда sqrt(x/y)+sqrt(y/x)>=2. Теперь осталось...

Подсказка 6

Сложить данные неравенства по всем парам вершин, использовать неравенство, которое мы получили выше, и мы получим требуемую оценку.

Показать доказательство

Степенью вершины многогранника называется количество исходящих из неё рёбер этого многогранника. Вершины называются смежными, если они соединены ребром. Пусть $A$ - произвольная вершина многогранника, $k$ - её степень, $mj$ - степени всех смежных с ней вершин ( $j = 1,2,...,k),$ занумерованных в произвольном порядке. Тогда $m1 +m2 +...+mk$ - это количество всех рёбер, исходящих из смежных с $A$ вершин, учтенных один или два раза, причём дважды учтены те и только те рёбра, которые лежат против вершины $A$ в некоторой треугольной грани многогранника. Значит, $m1 +m2 +...+mk ≤ P + T.$ Отсюда, используя известное неравенство между средним арифметическим и средним квадратическим, получаем

√m--+√m--+ ...+ √m-- √m--+-m-+-...+-m- √P +-T --1-----2k-------k-≤ ---1---2k-------k ≤ -√k---

Следовательно,

∘ --- ∘ --- ∘--- m1-+ m2-+ ...+ mk-≤ √P-+-T k k k

Обозначим сумму в левой части последнего неравенства за $S(A).$ Пусть $A i$ - все вершины многогранника, занумерованные в произвольном порядке, а $n i$ - их соответственные степени $(i= 1,2,...,B).$ Для любой пары смежных вершин $A i$ и $A j$ по неравенству между средним арифметическим и средним геометрическим выполнено неравенство

∘ ni- ∘ nj- nj + ni ≥ 2

Складывая эти неравенства по всем неупорядоченным парам ${Ai,Aj}$ смежных вершин многогранника, получаем

∑B S(Ai)≥ 2P i=1

По доказанному выше неравенству $S(A)≤ √P-+T-$ отсюда следует требуемая оценка.

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

Задача 18#68521

На конференцию приехали $100$ учёных. Оказалось, что у любых двоих как минимум двое общих знакомых. Докажите, что у кого-то из них хотя бы $15$ знакомых.

Источники: ИТМО - 2023, 10.7

Показать доказательство

Предположим противное. Рассмотрим граф, вершинами которого будут являться учёные, две вершины будем соединять ребром, если соответствующие учёные знакомы. Из нашего предположения степень каждой вершины не превосходит $14$ . Посчитаем двумя способами количество растопырок, то есть конфигураций из $3$ вершин, одна из которых (будем называть её главной) соединена с двумя другими). С одной стороны для каждой пары вершин к ним в растопырку можно выбрать хотя бы $2$ главные. Итого растопырок не меньше, чем $100⋅99⋅2 ---2----=9900$ . С другой стороны для каждой вершины количество растопырок, в которых она является главной, не превосходит $14⋅13= 91 2$ . То есть всего растопырок не больше $100⋅91= 9100 <9900$ , откуда получаем противоречие.

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

Задача 19#73174

В стране есть 100 городов и несколько дорог, каждая из которых соединяет два города. Путешественник заметил, что каким бы способом ни разделить города страны на две части, между этими двумя частями будет не более $400$ дорог. Докажите, что существует 7 городов, никакие два из которых не соединены напрямую дорогой.

Источники: 60 УТЮМ

Показать доказательство

Рассмотрим граф, в котором вершины — ребра, города — дороги. Выделим в нем максимальную антиклику $A 1$ . Если она размера 7 или более, то нам повезло. Иначе отделим эти вершины, а в оставшемся графе снова выберем максимальную антиклику $A2$ . Наберем таким образом 8 непересекающихся антиклик. Теперь в одну часть отнесем все вершины этих восьми антиклик (их будет не более $6 ⋅8$ ), а во вторую часть — все оставшиеся вершины. Заметим, что любая оставшаяся вершина имеет хотя бы по одной смежной в каждой антиклике, иначе на очередном шаге эту вершину можно было бы присоединить к этой антиклике. Следовательно, из каждой вершины второй части, которых хотя бы 52, выходит не менее 8 ребер в первую часть. Итого, не менее 416 ребер между частями. Противоречие.

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

Задача 20#73298

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

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

Подсказка 1

Задача легко решилась бы, если бы у каких-то 10 друзей одного человека нашелся общий друг. Может ли его не быть?

Подсказка 2

Попробуем доказать, что у каких-то двух друзей человека А есть общий друг. Этот общий друг может оказаться либо среди друзей A, либо среди других людей. Если он среди друзей А, то все просто, поэтому будем полагать, что среди друзей А ни у кого других общих друзей нет. Для этого рассмотрим граф, в котором вершины — люди, а ребра — дружбы. Можно ли оценить, сколько ребер выходит от вершин-друзей А к другим вершинам?

Подсказка 3

Верно, не менее 80 ребер! А можно ли оценить сверху число людей, не являющихся друзьями А или А?

Показать доказательство

Рассмотрим произвольного человека $A$ и его $10$ друзей. Если среди этих друзей есть друг $B,$ который знаком с двумя другими друзьями $A,$ то $A$ может пригласить $B$ и их двух общих друзей.

В противном случае каждый из друзей $A$ дружит не более чем с одним другом $A.$ Следовательно, каждый из них дружит хотя бы с $8$ людьми, отличными от $A$ и его друзей (хотя бы $80$ дружб). Но кроме $A$ и его друзей есть не более $79$ человек, следовательно у каких-то двух друзей $A$ есть общий друг. Тогда $A$ может пригласить этих двух друзей и их общего друга.