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

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

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

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

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

Пример. Отметим все клетки первой строки и первого столбца.

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

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

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

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

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

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

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

Предположим теперь, что задано не более, чем вопросов. Тогда в графе хотя бы 3 компоненты связности: если бы их было не более, чем две, но тогда ребер хотя бы — противоречие. Предположим, что теперь две из этих компонент четны. Теперь рассмотрим все наши компоненты связности. Среди них четное число нечетных компонент связности (по числу вершин). Пусть внутри каждой компоненты вершины раскрашены в красный и зеленый цвета. Можно считать, что в каждой нечетной компоненте зеленого цвета на 1 больше. Тогда разобьем все нечетные компоненты на пары, вершины зеленого цвета из одной компоненты объединим с красными из второй и наоборот и будем думать, что это болельщики одной команды, тогда пара (зеленые, красные) отправляется в первый автобус, а пара (красные, зеленые) во второй. Для четных компонент достаточно зеленую половину посадить в один автобус, а четную во второй.

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

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

Введем граф, вершинами которого будут города, а ребрами — дороги.

Пример. Если то треугольников с общей вершиной, если , то треугольников с общей вершиной и висячее ребро из той же вершины.

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

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

Пример. Одна вершина соединена с остальными ребрами длины

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

Рассмотрим граф состояний диаграмм Юнга с переходами в виде удаления доминошек, так как клеток конечное число, то все пути конечны, а по доказанному выше он удовлетворяет Diamond-лемме, значит, конечное состояние — единственно.

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

Для применения Diamond-леммы необходимо показать, что для пары состояний полученных операциями над вершинами из состояния найдется общее состояние

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

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

Обозначим — вершины смежные и с и с — смежные только с — только с Вес в вершине — в —

Тогда после описанных выше операций получим веса:

• в
• в
• в вес изменится на
• в вес изменится на

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

Оценка. Обозначим через количество стран, а через и — количество мужчин и женщин в -й стране соответственно. По условию

Заметим, что

Значит,

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

Пример. Пусть стран всего три, из двух приехало по одному мужчине, а из третьей — одна женщина.

Теорема Оре: Если в графе с вершинами для любых двух несмежных вершин и выполняется условие

то содержит гамильтонов цикл(проходящий по всем вершинам по разу).

Доказательство. Предположим противное: пусть граф удовлетворяет условию теоремы, но не является гамильтоновым.

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

Пусть вершины и не смежны, иначе мы бы замкнули путь в цикл. Обозначим:

Заметим, что и

Из условия теоремы:

По принципу Дирихле множества и пересекаются: существует Тогда в графе существует цикл:

Этот цикл содержит все вершины пути Если то – гамильтонов цикл, что противоречит предположению.

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

_________________________________________________________________________________________________________________________________________________________________________________

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

• Первый тур: рёбра с чётными номерами в цикле,
• Второй тур: рёбра с нечётными номерами в цикле.

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

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

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

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

откуда или 9.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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