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

Изначально в графе вершин и рёбер. Предположим, что через задержаний инструмент не разрушился. Это значит, что из изначального графа можно выкинуть какие-то рёбер и он останется связным. Следовательно, количество рёбер в нём будет не меньше (на один меньше количества вершин). Таким образом, то есть

Приведём пример на Введём систему координат так, что левая нижняя точка имеет координаты Удалим все рёбра, соединяющие вершины с координатами и — чётное.

Рассмотрим квадрат как граф. Вершинами будут клетки, а также всё внешнее пространство будем считать за одну вершину. Тогда удаление спички равносильно проведению ребра между двумя вершинами. Следовательно, нам нужно провести минимально возможное количество рёбер так, чтобы граф стал связным. Как мы знаем, в связном графе количество рёбер не меньше, чем количество вершин, уменьшенное на один. Следовательно, в графе должно быть хотя бы рёбер. То есть

Приведём пример для Введём систему координат так же, как в прошлой задаче. Удалим рёбра, соединяющие вершины и Также удалим рёбра, соединяющие вершины и

Введём граф следующим образом: камни будут вершинами, вершины соединены ребром, если соответствующие камни сравнивались. Ясно, что для выявления самого тяжёлого камня граф должен быть связным. То есть количество рёбер должно быть не меньше

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

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

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

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

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

В качестве примера на вершинах c ребрами, в котором две вершины и соединены со всеми (в том числе и друг с другом), а остальные вершины соединены только с и

Приведём алгоритм раскраски. Подвесим граф за какую-нибудь вершину. Суммарно на первом и втором уровнях не более вершины, так как степень вершины, за которую подвесили, не больше Раскрасим все вершины и уровней в разные цвета.

Далее рассмотрим какую-нибудь вершину третьего уровня. Она соединена не более чем с вершинами второго уровня, а значит мы сможем её покрасить в какой-нибудь цвет, не нарушая правильности. Покажем, что аналогично мы можем закрасить все вершины третьего уровня. Предположим, что это не так. Пусть мы дошли до некоторой вершины третьего уровня, для которой не осталось цветов. Но такого не может быть, поскольку она соединена суммарно с не более чем вершинами из третьего и второго уровней. Следовательно, третий уровень мы сможем закрасить. Аналогично закрасим остальные уровни. Что и требовалось.

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

Таким образом, мы получили три простых цикла: Их длины равны и (не умаляя общности пусть ). Но если эти числа делятся на то также делится на которое по условию больше Пришли к противоречию.

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

1.

Между любыми двумя вершинами нет ребра при Если это не так, то мы сможем выбрать цикл меньшей длины на ребрах в котором участвует ребро

2.

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

Удалим из все вершины, которые лежат в и все ребра, которые им инцидентны. Тем самым мы удалили ребро цикла, 0 ребер внутри цикла и не более ребер между вершинами и то есть суммарно не более ребер. Тем самым, в графе осталось не более вершин (потому что в цикле по условию хотя бы вершин) и хотя бы рёбер.

Повторим наш алогритм еще раза. После применения c номером мы имеем граф, в котором не более вершин и хотя бы ребер.

Наконец, перед последней итерацией, мы получим граф, в котором не более вершин и хотя бы ребер, в котором найдем последний цикл.

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

Итого: количество игр в группе по команды будет равно

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

Во время тура команд поделилось на группы. Тогда количество игр во туре — А в тур перешло команд.

Во время тура команд поделилось на группы. Тогда количество игр во туре — А в тур перешло команд.

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

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

Значит, общее кол-во игр в турнире будет равно

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

Участники, занявшие места с восьмого по двенадцатое, сыграли между собой 10 партий и набрали в сумме не менее 10 очков. Значит, игрок, занявший второе место, набрал не менее 10 очков.

Если он набрал 10,5 очков, то он выиграл 10 партий и в одной сыграл вничью. Если он сыграл вничью с победителем, то у победителя не более 10,5 очков. Противоречие.

Значит, игрок, занявший второе место, набрал ровно 10 очков. В этом случае все игроки, занявшие места с восьмого по двенадцатое, проиграли все свои партии игрокам, занявшим места с первого по седьмое.

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

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

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

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

В самом деле, рассмотрим произвольное остовное дерево этого графа и подвесим его за любую не висячую вершину. Пусть — наиболее удалённая от корня висячая вершина этого дерева, а — предок этой вершины. Обозначим потомков этого предка через Заметим, что вершины являются висячими в рассматриваемом остовном дереве. Рассмотрим несколько случаев.

Случай 1. Среди вершин есть пара вершин, соединённых ребром в исходном графе. Тогда при удалении этих двух вершин остовное дерево(а значит, и сам исходный граф) сохраняет связность.

Случай 2. Среди вершин есть пара вершин, являющихся висячими в исходном графе. Значит, в исходном графе есть хотя бы две висячие вершины.

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

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

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

Рассмотрим -оптимальную сеть с выделенными городами

и -оптимальную сеть с выделенными городами

Не умаляя общности, ни из одного нельзя добраться в сети до города Пусть — множество городов, из которых в можно добраться до а — множества дорог, выходящих из в сетях соответственно. Имеем

Рассмотрим сеть

Утверждается, что это -сеть для выделенных городов В самом деле, число дорог в ней равно

Из каждого города, кроме выходит ровно одна дорога. Выезжая из любого города вне и используя дороги сети, мы по-прежнему можем попасть в один из городов Выезжая из города в мы либо попадаем вне — и далее в один из городов — либо зацикливаемся в Но тогда содержит цикл, что невозможно.

Рассмотрим сеть

Утверждается, что это -сеть для выделенных городов В самом деле,

и, выезжая из любого города по дорогам сети мы либо попадаем в — и тогда по доезжаем до — либо ни разу не попадаем в и тогда доезжаем до одного из городов

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

Оценка. Разрыв меньше двух очков быть не может: очки А и Я отличаются как минимум на очко от любой другой команды из восьми оставшихся команд. Кроме того, результаты остальных команд находятся строго между их результатами, потому что опять же А набрала очков больше любой другой команды, Я – меньше любой другой. Тогда между их результатами (числами очков) должно быть ещё хотя бы одно число, отсюда разница не меньше .

(a) Пример. Пусть все встречи, кроме одной, закончились вничью. Тогда победитель этой одной встречи набрал на очка больше проигравшего, а остальные расположились между ними. То есть в данном случае у команды А очков, а у команды Я – .

(b) Пример. Пусть команд (все, кроме А) выиграли друг у друга по кругу (каждая победила один раз и проиграла один раз), А победила Я, а остальные встречи закончились вничью. Тогда у А очков, у Я — очков, а у остальных — по .

В первом и третьем матче «Метеор» забросил в сумме не более шайб. Но эта сумма в раза больше числа шайб, заброшенных в первом матче, значит, она делится на . Поэтому сумма не больше . Но во втором и четвёртом матче сумма на меньше, чем в первом и третьем, так что в первом и третьем сумма хотя бы .

Итак, сумма может быть равна только . Тогда во втором и четвёртом матчах «Метеор» забросил шайб, значит, он эти матчи выиграть не мог. А первый и третий он мог выиграть, например, со счётом и соответственно.

Если всего участников и победитель выиграл у всех, то он набрал очко. Всего разыграно очков. Отсюда

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

Тогда разделим на и получим

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

Предположим, что такое могло случиться.

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

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

Значит, такое невозможно.

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

Разделим ребра на два типа: те, что соединяют две клетки из одной вертикали и те, что соединяют две клетки из одной горизонтали.

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

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