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

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

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

откуда или 9.

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

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

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

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

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

Обозначим количество городов в группах и через и соответственно, Пусть в городов не меньше, чем в то есть В есть город Z, из которого выходит не менее дорог в города из Кроме того, из выходит дорог к городам группы Значит, из выходит не менее дорог. Противоречие.

Случай, когда в больше городов, чем в рассматривается аналогично.

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

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

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

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

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

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

Будем говорить, что вершина влияет на вершину если данные вершины являются соседями и идол сильнее идола при этом не имеет соседа с более сильным идолом, отличным от

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

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

Сначала покажем, что последовательностей не хватит.

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Пример на последовательностей опишем пример в терминах графа.

Разделим чисел на две равные группы: например, и .

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

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

Теперь поясним, почему после "склейки"полученные последовательностей будут удовлетворять условию. Какие бы числа , мы ни взяли, либо два из них будут среди чисел от до , либо среди чисел от до . Тогда два числа из одно группы соединены ребром, то есть являются соседями в одной из последовательностей. Этого мы и добивались.

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

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

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

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

Лемма. В сильно связном турнире существует гамильтонов цикл.

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

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

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

Если количество вершин в равно или то почти транзитивен.

Далее Рассмотрим два случая. Будем говорить, что если в ребро между и направлено к

1. Для каждого выполняется

Тогда пусть состоит из всех вершин с нечётными номерами, — из и всех вершин с чётными номерами. Нетрудно видеть, что а индуцированные турниры и — сильно связные.

2. Существует диагональ

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

Итак, при и мы имеем Осталось разобраться, как направлены стрелки, инцидентные Если существует такое что то множества

таковы, что турниры и сильно связны и В этом случае утверждение доказано.

Остаётся случай, когда для некоторого в нашем графе стрелки ориентированы таким образом:

При турнир почти транзитивен (с порядком ). При турнир почти транзитивен (с порядком ). Если же то Следовательно, множества и таковы, что и сильно связны и

Переформулируем условие задачи на язык графов. Пусть 30 учеников — это 30 вершин, а когда два человека дежурили вдвоём, то соединим их ребром. Тогда давайте рассмотрим получившиеся компоненты связности(она может быть и одна). Мы утверждаем, что среди них есть дерево. Действительно, если это не так, то, просуммировав по всем компонентам, мы получим хотя бы 30 рёбер. Но по условию дежурств, то есть рёбер, всего 29. Значит, дерево есть, и в нём как раз, чередуя оценки 3 и 5, выставим их всем ученикам. А остальным поставим четвёрки.

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

Теперь приведём пример на Нужно ставить королей в следующем порядке на клетки с координатами:

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

Допустим теперь, что и находятся на разных дугах. В этом случае наш цикл распадается на два:

Теперь рассмотрим случай, когда мы меняем местами людей из разных циклов. В этом случае оба цикла "склеиваются"в один:

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

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

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

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

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

Первое решение. Индукцией покажем, что для городов База очевидна.

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Рассмотрим вершину Она соединена с тремя вершинами и Получается, что все остальные вершины должны быть соединены с какой-то из вершин иначе между ними и не будет пути длиной не более Вершины могут быть соединены суммарно не более чем с вершинами помимо Значит, всего не более вершин. Пример на вершин представлен ниже:

1. В полном графе на четырех вершинах есть только 2 вида остовных деревьев: 1) цепь длины 4; 2) три вершины, "висящие"на четвертой.

Каждое дерево первого вида даст в остовный многочлен одночлен , , причем каждый одночлен будет представлен 2 раза.

Каждое дерево второго вида даст в остовный многочлен одночлен , где — "вершина"остова.

В итоге получим многочлен:

2. Распишем . Поскольку многочлен линеен по каждой переменной, получаем, что каждая из переменных живет только в одной из скобок. Тогда переменные вынуждены разбиться на скобки 2-2-1 или 3-1-1, что дает нам не более четырех мономчиков, противоречие.

3. Давайте сначала заметим, что можно последовательно выкидывать вершины по одной с сохранением связности, если связно. (Если несвязно, то просто 0 получится и все).

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

4. Сначала докажем вспомогательный факт про такой тип графов.

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

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

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

Теперь очевидно, что второй сомножитель равен , и лемма доказана. ________________________

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

Тогда получается, что

доказали требуемое.

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