Тема СПБГУ

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

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

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

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

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

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

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

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

Задача 1#87413

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

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

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

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

В школе $2019$ учеников. В один прекрасный день некоторые из них поздоровались друг с другом за руку, причем из любой тройки учеников хотя бы двое не здоровались. При каком наибольшем $k$ могло оказаться так, что для любого $n,$ не превосходящего $k,$ найдется школьник, поздоровавшийся ровно с $n$ учениками?

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

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

Предположим, что школьник $A$ поздоровался с учениками $B ,...,B . 1 k$ По условию ни при каких $i$ и $j$ школьники $B i$ и $B j$ не здоровались друг с другом. Рассмотрим всех учеников, которые поздоровались менее $k$ раз, и выберем среди них того, кто здоровался не меньше других. Будем для определенности считать, что это $B1$ и что он поздоровался $m$ раз. Тогда кроме $A$ школьник $B1$ поздоровался еще с некоторыми учениками $C1,C2,...,Cm −1$ . Значит, в школе не менее $(k+ 1)+(m − 1)= k+ m$ учеников.

С другой стороны, по условию есть ученики, поздоровавшиеся ровно с

m + 1,m + 2,...,k− 1

школьниками, и они не находятся среди $A,B1,...,Bk.$ Поэтому учеников в школе не меньше, чем

(k+1)+ (k− 1 − m )=2k− m.

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

2019 ≥k +m, 2019 ≥2k− m.

Складывая их, мы получим

4038- 4038≥(k+ m)+ (2k − m )= 3k =⇒ k≤ 3 = 1346

Покажем теперь, что $k= 1346$ реализуется. Разобьём всех учеников на две групшы: $A1,...,A673$ и $B1,...,B1346.$ Пусть $Ai$ поздоровался с $Bj$ при $i≤ j,$ а остальные пары школьников не здоровались друт с другом. Проверим, что такой пример нам подходит.

Первое условие задачи выполнено, поскольку в любой тройке учеников найдутся двое из одной группы, а они между собой не здоровались. Возьмем $n ∈{1,...,1346}$ . Если $n> 673,$ то число $i= 1347− n$ не превосходит $673.$ Тогда ученик $Ai$ поздоровался ровно с $1346− i+1= n$ школьниками. Если же $n≤ 673,$ то ученик $Bn$ поздоровался со школьниками $A1,...,An,$ которых ровно $n.$ Таким образом, и второе условие задачи выполнено.

Ответ:

$k =1346$

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

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

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

Задача 4#39876

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

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

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

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

Ответ:

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

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

Задача 5#36855

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

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

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

Оценка.

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

Пример.

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

Ответ:

$11025$