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

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

Оценка.

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

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

Пример.

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

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

где (степень вершин изначально была равна ). Легко видеть, что делится самое большее на первую степень числа 5, поэтому делится на 25. Пусть Тогда . Значит, число делится на 5, т.е. либо , либо , т.е. либо , либо , что невозможно при целых значениях . Отсюда вытекает, что наше предположение неверно, значит, утверждение задачи справедливо.

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

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

Аналогично, после второго тура останутся борцы с номерами и , после третьего: и , после седьмого: и Значит, в последнем, финальном, бою встретятся борцы с номерами и . Противоречие с предположением, что борец с номером может победить.

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

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

Допустим, что среди туристов имеется (или более) «богачей». Нарисуем граф: вершины — это города, из каждого города проведем самый дорогой выходящий путь. Тогда этот граф представляет собой лес, в каждом дереве которого все ребра направлены к корню, за исключением единственного ребра, выходящего из корня, — это ребро в дереве как бы двустороннее. Возьмем богача, который расположен ближе всего к корню своего дерева. Этот богач будет в течение ходов самым близким к корню. Значит, он проедет по городам, в которых еще не было других богачей. Это может быть только если граф — это путь из вершин, богачи занимают первые вершин этого пути (т. е. половину) и гуськом движутся по этому пути в сторону второй половины. Отсюда следует, что богачей не может быть больше а также что количество переездов тоже не превосходит

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

Обозначим города Допустим, что путь

составлен из самых дорогих авиалиний, для определенности пусть цена перелета равна рублей. А «бедный путь» пусть сначала проходит по городам с большими четными номерами, потом — по городам с большими нечетными, а далее — с малыми: сначала с четными, потом с нечетными:

Цены этих авиалинии пусть убывают от до рубля при движении вдоль этого пути. Цены остальных авиалиний назначим произвольно в диапазоне от до рублей.

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

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

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

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

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

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

Теперь возьмём две команды и из второй группы. Если выиграла то у 0 очков, у 6 очков, а у — 3, что опять же противоречит условию. Таким образом, между любыми двумя командами из второй группы ничья.

Наконец, возьмём две команды и из третьей группы. Если выиграла то у 2 очка, у 4 очка, а у — 1, что невозможно по условию. Получается, между любыми двумя командами из третьей группы ничья.

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

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

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

Оценка.

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

Пример.

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

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

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

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

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

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

то существует набор чисел, в сумме дающих единицу, таких, что каждое больше соответствующей дроби. Любой такой набор подходит.

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

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

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

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

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

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

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

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

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

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