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

Посчитаем количество дружб между девочками и мальчиками. Так как в каждой такой дружбе ровно один мальчик и он дружит с девочками, то общее количество таких дружб равно количество мальчиков. С другой стороны, оно же равно количество девочек. Значит девочек больше, чем мальчиков.

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

Пусть – число семиклассников, – число восьмиклассников; тогда Второе уравнение мы получим, если подсчитаем двумя способами общее количество рукопожатий. С одной стороны, число рукопожатий равно , поскольку от каждого семиклассника «исходит» 8 рукопожатий. С другой стороны, число рукопожатий равно , так как от каждого восьмиклассника «исходит» 7 рукопожатий. Следовательно, Решая полученную систему уравнений, находим: .

Минимальная возможная сумма очков, набранных командами, равна За одну игру можно набрать максимум 3 очка (в сумме у двух игравших команд). Значит, игр было не менее 5. Однако если было бы ровно 5 игр, то все игры должны были бы закончиться победой одной из команд, а тогда никакая команда не набрала бы ровно 1 очко. Значит, игр минимум

Пример результатов турнира, в котором было сыграно ровно 6 игр, зададим таблицей.

Каждый участник выбывает, потерпев ровно два поражения. В ситуации, когда остались двое “финалистов”, общее количество поражений равно 29. Если из турнира выбыло человек, то они суммарно потерпели поражений, а на счету “финалистов” могло быть или поражения. Учитывая, что и — чётные числа, приходим к уравнению , откуда , а общее количество участников равно 16.

Пусть в матчах Бразилия победит, а в матчах проиграет. Составим уравнение . Видим, что и . НОД , т.е.

а) . Тогда получим уравнение . Т.е. . Это возможно.

б) . Получим уравнение: . Откуда . Это невозможно, т.к. количество матчей уже превышает 38.

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

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

Если граф — это цикл, содержащий 101 вершину, то на любых 100 вершинах ровно 99 рёбер, так что такая компания удовлетворяет условиям задачи. Осталось показать, что не существует такой компании из 102 человек (тогда и компании из более чем 102 человек тоже быть не может). Ниже мы приведём несколько различных способов сделать это; в каждом способе мы предполагаем, от противного, что такая компания нашлась.

_________________________________________________________________________________________________________________________________________________________________________________

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Существует всего способов выбросить две вершины из 102, оставив 100. Пронумеруем эти способы числами от 1 до Пусть — количество рёбер на оставшихся 100 вершинах в -м способе; по предположению, все числа нечётны, а значит, нечётна и их сумма (поскольку число нечётно).

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

_________________________________________________________________________________________________________________________________________________________________________________

Третье решение. Назовём вершину чётной, если её степень чётна, и нечётной иначе. Рассмотрим два случая.

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

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

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

Докажем, что компании из человек быть не может. Всего способов выбросить две вершины из равно

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Докажем, что компании из человек быть не может. Назовём вершину чётной, если её степень чётна, и нечётной иначе.

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

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

что нечётно. Противоречие.

Удобно рассуждать на соответствующем графе. Шпионы – вершины графа, пары шпионов – ребра графа. Всего ребер Донос шпиона А на шпиона В – это, скажем, раскрашивание ребра (А,В). Количество всех раскрашиваний равно, по условию . Количество раскрашиваний превышает количество ребер на Это означает, что найдутся не менее 10 дважды раскрашенных ребра (ребро А,В) либо не раскрашено, либо раскрашено один раз, либо раскрашено дважды – как (А,В) и как (В,А). А это как раз то, что требовалось доказать.

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

Пусть — число игроков,

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

Сумма очков, набранных сильными во встречах между собой, равна а во встречах со слабыми — не больше

Поэтому средний результат сильного не больше Аналогично, средний результат слабого не меньше

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

Так как общее число партий равно доля правильных партий больше то есть более процентов.

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

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

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

Наконец, сложив измеренные величины и разделив сумму пополам, мы получим длину всей сети.

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

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

Оценка. Докажем индукцией по что в графе отсутствует хотя бы ребер; из этого следует, что ибо иначе ребер бы не было, и графе был бы связным. База при очевидна.

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

Оценка. Назовём доменом команды совокупность всех команд, у которых она выиграла. Команду, в домене которой не менее команд, назовём доминатором.

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

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

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

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

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

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

Действительно, все рёбра, выходящие из вершин с номерами от до делятся на два типа:

идущие в вершины с номерами от до — таких не болыше

идущие в вершины с номерами от до — таких не больше но каждое мы можем посчитать по два раза.

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

противоречие.

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

Пронумеруем олигархов и их города числами от до соответственно.

Пример.

Пусть дорога между городами и принадлежит олигарху под номером тогда и только тогда, когда Тогда количество дорог равно

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

Оценка 1.

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

Рассмотрим произвольную тройку олигархов и Докажем, что эта тройка сопоставлена не более чем одной дороге.

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Оценка 2.

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

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

База очевидна.

Переход. Пусть мы хотим удалить олигарха номер . Так как все олигархов не могут образовать корпорацию, граф на. ребрах всех цветов несвязен. Обозначим через компоненту связности, содержащую город олигарха номер , через — объединение всех остальных компонент связности, а через и — количество вершин в и соответственно. Тогда подграф содержит не более ребер -го цвета. Далее, из вершины выходит не более ребер с цветами, соответствующими вершинам из Наконец, применяя к графу индукционное предположение, получаем, что в графе имеется не более ребер, имеющих цвет или выходящих из вершины Следовательно, при удалешии вершины исчезнет не более

ребер.

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

Социальная сеть представляет собой граф, в котором люди - это вершины, а отношение “дружба” — ребра. Достаточно рассмотреть случай, когда этот граф является деревом. В требованиях условия задачи группу, в которой состоит от до членов, будем называть малой, а группу, где от до членов, — большой. Докажем утверждение задачи индукцией по числу пользователей сети. База индукции: Если в сети не более пользователей, объявим их всех малой группой. Если в сети от до пользователей, назначим малой группой любого пользователя, соответствующего висячей вершине, а всех остальных запишем в большую группу.

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

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

В турнире с 10 игроками, проходящем в 1 круг, разыгрывается очков. Поэтому найдется игрок, набравший не более очков. Значит, Петя, занявший абсолютное последнее место, набрал не более 4 очков. Аналогично, в турнире с игроками, проходящем в 1 круг, разыгрывается очков. Остальные 8 игроков набрали не менее 32 очков. Значит, найдется игрок (отличный от Пети), набравший (после пересчета) не менее очков. Поэтому Петя не мог стать абсолютным победителем турнира.