Графы и турниры

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

Возможны всего три случая: закрыли прямую дорогу на пути закрыли дорогу на пути закрыли дорогу

Разберём первый случай: закрыли прямую дорогу В графе после удаления ребра найдется путь между и пусть это дорога

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

Разберёмся со вторым случаем: на закрыли дорогу В графе после удаления ребра есть какая-то дорога от до пусть это дорога

В исходном графе был путь из в Заметим, что этот путь не мог проходить через удаленное ребро, ведь это ребро не может быть ни первым в пути, ни последним, а ребер всего два. Тогда можно пройти из в а потом по этому пути.

Третий случай: на закрыли дорогу В графе после удаления ребра есть какая-то дорога от до пусть это дорога

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

Рассмотрим граф, в котором вершины — города, а ребра — авиалинии. Каждое ребро раскрасим в один из двух цветов: первый соответствует авиалинии первой компании, а второй — авиалинии второй компании. Удалим рёбра первого цвета. Предположим, что граф распался на несколько компонент связности. Тогда все пары вершин из разных компонент соединены ребром первого цвета. Давайте вернём рёбра первого цвета, а рёбра второго цвета удалим. Покажем, что граф связен. Во-первых, понятно, что две вершины, которые раньше были в разных компонентах, соединены ребром. Во-вторых, от любой вершины до любой вершины из её компоненты можно добраться через вершину из другой компоненты. Получили требуемое.

Рассмотрим человека Он дружит с хотя бы другими. Рассмотрим его друга Учеников, которые не дружат с не более 5 и учеников, которые не дружат с не более 5. Убрав из 20 не более 10 учеников, которые не дружат с или а также самих и получим, что у и хотя бы 8 общих друзей. Теперь среди общих друзей и рассмотрим некоторого друга Рассуждая подобно тому, как мы сделали для и получаем, что у и хотя бы 2 общих друга. Обозначим этих общих друзей и Значит, четвёрки и подходят.

Ясно, что задачу можно переформулировать в терминах графов: вершины — города, а ребра — дороги. Из условия известно, что граф — дерево, а каждая область — это дерево какого-то подграфа. Рассмотрим произвольный лист дерева. Если его удаление не нарушает условие пересечения выбранных областей, удалим его и повторим процедуру. Так как количество вершин в графе конечно, процесс обязательно закончится. Пусть при удалении листа условие пересечения нарушается для поддеревьев и Рассмотрим смежную с вершину (если её нет, то осталась одна вершина — общая для всех). Тогда, поскольку нарушение наблюдается, хотя бы одно из поддеревьев, скажем не содержит Это возможно если состоит только из Так как все области пересекаются с содержится во всех поддеревьях, как и требовалось доказать.

Подвесим граф за вершину Для каждой вершины определим её глубину — наименьшую длину пути до этой вершины из Пусть смежна с Тогда пусть, кроме вершина соединена с

Тогда покажем, что все вершины образуют независимое множество. Пусть это не так и смежно с Тогда

образуют цикл длины 5, что противоречит условию. Остаётся заметить, что вершин хотя бы что и требовалось доказать.

Пусть граф двудольный. Тогда в каждом цикле доли чередуются, причём начинаем и заканчиваем мы в одной и той же доле. Значит, цикл имеют чётную длину.

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

Связный граф, в котором нет циклов, — это дерево. Покажем по индукции, что в дереве с вершиной рёбра можно разбить на пары способом из условия. База очевидна. Теперь пусть любое дерево на вершине можно так разбить. Покажем, что и дерево на вершине тоже можно разбить. Подвесим граф за вершину Для каждой вершины определим её глубину — наименьшую длину пути до этой вершины из Пусть — вершина наибольшей глубины. Тогда — висячая вершина, поскольку иначе мы можем пойти ещё ниже. Пусть соединена с Допустим, из вниз идёт ещё какое-то ребро в вершину Заметим, что также вершина наибольшей глубины, поэтому она также висячая. Давайте удалим вершины и , а как пару рёбер возьмём и Тогда граф остался связным, и можно применить предположение индукции. Если же из вниз ребро идёт только в то удалим вершины и а в качестве ребёр возьмём рёбра из Граф снова останется связным, по индукции искомое разбиение существует, что и требовалось доказать.

Рассмотрим граф, в котором вершинами будут города, а ребрами — дороги. Подвесим граф за вершину Для каждой вершины определим её глубину — наименьшую длину пути до этой вершины из Назовём уровнем множество вершин одной глубины. Заметим, что вершина глубины может быть соединена ребром только с вершинами глубин или так что если глубины вершин отличаются хотя бы на 3, то у них нет общих соседей. Предположим, что есть вершина глубины более чем 63. Тогда рассмотрим вершины

где глубина будет Каждая из этих вершин имеет степень хотя бы 93, причём их соседи не пересекаются, так что всего вершин хотя бы противоречие. Значит, из до любой другой вершины можно добраться с не более чем 62 пересадками. Из независимости выбора получаем требуемое в условии.

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

Оценка. Докажем оценку Условие гласит, что в нашем полном графе есть как шестёрки вершин, сумма на рёбрах между которыми положительна, так и шестёрки, сумма на рёбрах между которыми отрицательна. Тогда найдутся две шестёрки, отличающиеся заменой только одной вершины, такие, что у одной из них сумма положительна, у другой отрицательна. В самом деле, возьмём шестёрку с положительной суммой, и будем превращать её в шестёрку с отрицательной суммой, меняя вершины по одной, — на каком-то шаге произошло изменение знака, шестёрки, которые были до и после этого шага – искомая пара.

Далее работаем с полным подграфом на множестве из семи вершин – объединении вышеописанной пары шестёрок. Рассмотрим все семь шестёрок, которые можно получить выбрасыванием одной вершины из Пусть среди них с отрицательными суммами — получающиеся выбрасыванием вершин будем называть эти вершины -вершинами, а соответствующие шестёрки – -шестёрками), и с положительными суммами — получающиеся выбрасыванием вершин (будем называть эти вершины -вершинами, а соответствующие шестёрки – -шестёрками). Рёбра между двумя -вершинами будем называть -рёбрами, между двумя -вершинами — -рёбрами, а рёбра, соединяющие -вершину с -вершиной — -рёбрами.

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

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Подграф с новыми числами на рёбрах удовлетворяет условию с той же константой

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

_________________________________________________________________________________________________________________________________________________________________________________

Далее изучаем новую расстановку. Рассмотрим случаи.

Случай Иными словами, есть ровно одна -шестёрка, на которой пятнадцать -рёбер, и шесть -шестёрок, на каждой из которых десять -рёбер и пять -рёбер. Имеем систему неравенств:

Умножим первое на сложим со вторым, умноженным на 3, получим откуда

Случай Теперь у нас две -вершины и пять -вершин, то есть на -шестёрке есть десять -рёбер и пять -рёбер, а на -шестёрке – шесть -рёбер, восемь -рёбер и одно -ребро. Имеем

Исключая получаем

значит,

Случай Аналогично предыдущему, имеем

Избавляясь на этот раз от получаем откуда

Случаи сводятся к рассмотренным умножением всех чисел на что ведёт к замене Итак, оценка доказана.

Пример. Любое число вершин от двух до 999995 объявим вершинами типа остальные – вершинами типа На всех рёбрах между двумя вершинами типа напишем число на всех остальных – число 1. Тогда, если в шестёрке вершин хотя бы пять -вершин, то сумма в ней не больше а иначе – не меньше

Заметим, что условие равносильно тому, что

или же Рассмотрим граф, вершины которого — записанные на доску числа, а ребро проводится между двумя числами, которые отличаются на Согласно условию задачи, в таком графе ровно 760 рёбер. Каждая компонента связности этого графа представляет собой путь и состоит из вершин-чисел вида …, Предположим, что в этом графе компонент связности. Тогда в нём рёбер, поэтому Поскольку то в какой-то компоненте связности хотя бы 46 вершин, поэтому какие-то две из этих вершин — это числа и Тогда

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

что и требовалось.

Рассмотрим произвольного рыцаря пусть его друзья — это Пусть тогда если — один из врагов то враг для (по условию), то есть у хотя бы врага — противоречие.

Значит у каждого рыцаря не более друзей, а также у каждого рыцаря ровно врага, значит,

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

Разберём случаи:

1.

Берём две группы по рыцаря. Подграф на каждой из подгрупп — полный синий. Граф без учёта рёбер в группах — полный двудольный красный.

2.

Полный красный граф на вершинах.

3.

Но у каждого рыцаря по врага. Значит, не подходит.

Введем обозначения: — число команд из Ленинградской области, — число очков, набранных каждой из команд из Ленинградской области. Тогда число очков, набранных всеми командами, равно Оно равно числу спортивных соревнований, так как за одно соревнование дают одно очко.

Число проводимых спортивных соревнований найдем по формуле сочетаний без повторов:

Тогда получим:

Следовательно, Так как это могут быть только делители числа то есть значения: Следовательно, наибольшее значение

Пример

Рассмотрим набор точек, изображенных на иллюстрации. Для простоты восприятия проведем только красные отрезки.

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

Вершина соединена со всеми вершинами среднего уровня, а значит, не может быть вершиной синего треугольника. Аналогично, вершина соединена со всеми вершинами внешнего уровня, а значит, не может быть вершиной синего треугольника. Тогда вершина соединена со всеми вершинами среднего уровня, кроме и не может быть вершиной синего треугольника. Значит, ни одна вершина внутреннего уровня не является вершиной треугольника с синими сторонами, а значит, такого треугольника не найдется.

_________________________________________________________________________________________________________________________________________________________________________________

Пример

Возьмем два графа с красными ребрами. Тогда синие отрезки образуют граф то есть двудольный граф, в котором могут быть только циклы четной длины, а треугольник — это цикл нечётной длины, следовательно треугольников нет.

_________________________________________________________________________________________________________________________________________________________________________________

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

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

Если бы Дима играл в первой партии, то он бы сыграл минимум 4 раза (так как в худшем случае он бы играл еще в третьей, пятой и седьмой партиях). Если он начал играть со второй партии, то для выполнения условий задачи он должен был проиграть все свои партии, иначе у него были бы игры подряд, и получилось бы больше трех игр. Значит, Дима играл во 2, 4 и 6 партиях и проиграл каждую из них, а значит, Дима проиграл и вторую игру. Обозначим имена начальными буквами и покажем, как могла складываться игра.

Наименьшее число игр с другими ребятами будет, когда число игр между Машей и Петей наибольшее. Всего в условии говорится про игр, но игры, в которых Маша и Петя играли между собой, посчитаны два раза. Так как Маша не проиграла ни в одной игре, в играх между Машей и Петей либо была ничья, либо Маша выиграла. Маша выиграла 2 партии, а Петя проиграл 3. Значит, они могли сыграть 2 партии между собой, а одну игру Петя проиграл кому-то еще. Кроме того, у каждого из них была ничья, эта игра тоже могла быть между ними. Итак, самое большое число игр между Машей и Петей равно 3. Тогда общее число игр, сыгранных Машей и Петей, равно Из этих 8 игр 3 игры между Машей и Петей, а остальные игр с другими ребятами.

Рассмотрим граф дружбы для учеников. Будем называть галочкой с центром в тройку вершин такую, что рёбра и проведены. Найдём общее число галочек. Степень каждой вершины хотя бы 5, поэтому каждая вершина является центральной хотя бы в галочках. При этом по лемме о рукопожатиях найдётся вершина чётной степени, она даст хотя бы галочек. Таким образом, всего галочек хотя бы Заметим, что всего пар вершин Тогда по принципу Дирихле найдутся две галочки, которые смотрят на одну и ту же пару вершин, что и требовалось доказать.

Рассмотрим момент перед поражением одного из игроков при правильной игре. Легко видеть, что граф должен состоять из двух компонент связности, каждая из которых представляет собой полный граф (иначе можно проводить ребра так, чтобы граф не стал связным). Пусть в одной из этих компонент вершин, тогда во второй Тогда ребер в этом графе

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

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

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

откуда или 9.

В обоих случаях число несостоявшихся партий нечётно. Ещё из условия следует, что у выбывших осталось не сыграно по одинаковому числу партий. Сумма этих чисел чётна, значит, не равна общему числу несостоявшихся партий. Такое возможно в единственном случае: когда партия между выбывшими учитывается в сумме дважды. Значит, выбывшие не играли между собой.

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

равносильно равенству