Тема СПБГУ

Графы, турниры и игры на СПБГУ

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

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

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

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

Подтемы раздела спбгу

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

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

Задача 1#87413

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

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

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

Подсказка 1

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

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

Рассмотрим граф, в котором города — вершины, а авиалинии — рёбра. Рассмотрим подграф $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

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

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

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

Задача 2#80506

В однокруговом турнире по настольному теннису приняло участие 35 человек. По итогам турнира оказалось, что нет такой четверки игроков $A,B,C,D$ , что $A$ выиграл у $B,B$ — у $C,C$ — у $D$ , а $D$ — у $A.$ Каково наибольшее количество троек участников, одержавших во всех трех встречах между собой ровно по одной победе? Ничьих в теннисе не бывает.

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

Пусть есть 2 тройки, которые пересекаются по ребру. Назовем их $A,B,C$ и $A,B,D$ . Тогда нуо $A$ выиграл у $B$ и $C$ выиграл у $D$ , то $B$ выиграл у $C$ и $D$ , а $A$ проиграл $C$ и $D$ . Тогда $A$ выиграл у $B$ , $B$ выиграл у $C$ , $C$ выиграл у $D$ , а $D$ выиграл у $A$ ?!

Пусть есть 2 тройки, которые пересекаются по вершине. Назовем их $A,B,C$ и $C,D,E$ . Тогда без ограничения общности $C$ выиграл у $A$ и $D$ и $D$ выиграл у $A$ , то $A$ выиграл у $B$ , $B$ выиграл у $C$ , $D$ выиграл у $E$ и $E$ выиграл у $C$ . Тогда $A$ выиграл у $B$ , $B$ выиграл у $C$ , $C$ выиграл у $D$ , а $D$ выиграл у $A$ ?!

Значит, тройки не пересекаются и из не более 11. Осталось показать, что 11 троек может быть. Давайте выделим 11 непересекающихся троек и еще двойку и пронумеруем их от 1 до 14. В каждой тройке у нас будет цикл, в двойке победа будет у любого, а между группами $i$ и $j$ (где $i⁄= j$ ) победа будет у группы с большим номером. Тогда если появится запретная четверка, то заметим, что если обходить ее по кругу от проигравшего к победителю, то номер группы может только расти или не изменяться. Раз мы вернемся в конце в начальную вершину, то номер группы должен все время не изменяться, и значит, все 4 вершины лежат в одной группе?! Значит, запретных четверок в таком турнире не будет.

Ответ: 11

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

Задача 3#39876

По краю круглого стола стоят $n$ пустых стаканов $(n≥ 3).$ Петя и Вася по очереди (начиная с Пети) наливают в них квас. Петя в свой ход наливает квас в выбранный им пустой стакан, у которого оба соседних с ним стакана либо пустые, либо полные. Вася в свой ход наливает квас в выбранный им пустой стакан, у которого один соседний с ним стакан пустой, другой — полный. Проигрывает игрок, не имеющий хода. При каких $n$ Петя выигрывает вне зависимости от действий Васи?

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

Подсказка 0!

Проанализируем и формализуем происходящее, чтобы было проще разбираться!

Подсказка 1!

Попробуем для наглядности задачи рассмотреть простые примеры. Вот если n=3, 4, то что получится? Отлично, с примерами разобрались, пусть n больше 4..

Подсказка 2!

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

Подсказка 3!

Петя выиграет, если останутся на столе только полоски, идущие с промежутком в один стакан! (Тогда Вася не сможет сделать ход). Так, игру мы проанализировали, осталось придумать Пете подходящую стратегию, чтобы игра свелась к такой ситуации!

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

Если стакана $3,$ то побеждает Петя за один ход. Если $4,$ то Вася ставит стакан рядом с Петей и сам побеждает за один ход, пусть далее $n >4.$

Назовём “закваской” набор из подряд идущих заполненных стаканов. Тогда Вася может увеличить размер закваски, но не может добавить новую. В то же время Петя может либо объединить две закваски, либо создать новую из одной кружки. Первым ходом Петя заполняет произвольную кружку, получая одну закваску. Назовём “застольем” набор идущих подряд по кругу заквасок. Далее пусть каждым своим ходом Петя добавляет новую закваску, пропуская один стакан после текущего конца застолья, то есть после последней закваски в нём. Пусть Петя спустя $k$ добавленных Петей заквасок не может сделать ход. Тогда всего на столе $2k$ полных стаканов и не более $k+ 1$ пустых (по одному между заквасками и максимум два после конца застолья). То есть $3k +1≥ n> 4 =⇒ k≥ 2.$ То есть найдётся хотя бы одно междузаквасье длиной один, где Петя может заполнить стакан, а Вася нет (заквасок хотя бы $2$ ). Если после застолья идёт один пустой стакан, то Вася не может сделать ход и уже проиграл (если $0,$ аналогично), иначе их два. Вася заполнит один из них и второй следующим ходом сможет заполнить Петя, то есть у него есть уже два дополнительных хода, а у Васи их не осталось, потому на следующем ходу он проиграет.

Ответ:

при $n = 3$ и при $n≥ 5$

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

Задача 4#36855

В стране Альфия $150$ городов, некоторые из которых соединены железнодорожными экспрессами, не останавливающимися на промежуточных станциях. Известно, что любые четыре города можно разбить на две пары так, что между городами каждой пары курсирует экспресс. Какое наименьшее число пар городов соединено экспрессами?

Источники: СПБГУ-15, 11.5 (см. rsr-olymp.ru)

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

Подсказка 1!

1) Какое-то странное условие про пары, как бы его использовать. Давайте попробуем придумать четверку вершин, для которых это условие выполнялось бы с трудом.. Может быть, для какой-то четверки не выполняется вообще... Здорово было бы получить из этого условия какое-то ограничение для наших вершин.

Подсказка 2!

Например, возьмем вершину, которая с тремя из всех не соединена. Выполнится ли условие в таком случае? Так, смотрите, мы получим оценку на степени вершины! Где-то я про это уже слышала, что-то про степени вершины в графе, да.....

Подсказка 3!

3) В точку! Какая-то популярная эта лемма. А теперь важно не забыть аккуратно построить пример для нашей чудесной оценки!

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

Оценка.

Если нашлась вершина (город) степени не больше $146,$ то она не соединена хотя бы с тремя городами. Возьмём эти три города и саму вершину, получим, что она не может быть в паре ни с одним из них, откуда степень каждой вершины хотя бы $147.$ Тогда по лемме о рукопожатиях рёбер в графе не меньше $147⋅150 2 = 11025.$

Пример.

Теперь расположим их все в вершинах правильного $150$ -угольника(!). Проведём все рёбра графа, кроме сторон самого многоугольника (то есть выкинем $150$ рёбер из полного графа). Легко проверить, что степень каждой вершины стала равна $147.$ Выберем произвольную четвёрку городов и покажем, что она удовлетворяет условию задачи. Нам требуется найти их разбиение на две пары несоседних вершин — тогда внутри пар есть рёбра по построению. Но для этого достаточно соединить их через одну в том порядке, в котором они расположены в $150$ -угольнике, тогда вершины в паре разделяет ещё хотя бы одна и соседними они быть не могут.