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

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

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

Рассмотрим граф , в котором вершины — это города, а рёбра — дороги. Степени всех вершин этого графа равны 100. Начнем ходить из произвольной вершины графа. Будем ходить по ранее не пройденным ребрам, пока можем. Если мы в какой-то момент не сможем выйти из вершины, то мы прошли все 100 ребер, выходящих из нее. Предположим, что эта вершина, отличная от стартовой. Тогда число входов в вершину на 1 больше числа выходов, следовательно мы посетили нечетное число ребер, выходящих из вершины (каждый вход и выход добавляет одно ребро). То есть мы зациклились. Выкинем все ребра этого цикла. У каждой вершины степень по-прежнему четна. Опять найдем цикл, выкинем все его ребра и так далее.

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

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

Теперь нарисуем вершины по кругу, оставив одну вершину, ни с чем не соединенную, в центре, и соединим вершины ребрами. Обратите внимание на порядок вершин.

Вот одна из возможных картинок. Мы уменьшаем верхнюю грань и “схлопываем” ее с нижней.

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

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

По условию, изначально кони стоят в углах, то есть в вершинах и Пусть не умаляя общности белые кони стоят в вершинах и а черные — в и

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

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

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

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

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

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

В итоге путь имеет длину не больше трёх.

Если команда набрала очка за игры, то либо она выиграла одну игру и проиграла две, либо же сыграла три игры вничью. Первый вариант невозможен, так как иначе было ещё две команды, которые набрали хотя бы по три очка (победив «Катрапс»), то есть «чистое» второе место мы бы не заняли. Значит было сыграно три игры вничью. Среди оставшихся трёх команд только одна могла побеждать, иначе бы опять хотя бы у двух команд было больше трёх очков. Более того, у команды на первом месте должно быть хотя бы очка, а значит одна победа у неё точно была. Итак, у команды на первом месте есть хотя бы очка, у «Катрапса» — , у -го и -го места по одному очку и осталась одна игра между победетилем и третьим или четвёртым место и игра между третьим и четвёртым местом. Игра между третьим и четвёртым местом не могла закончиться чьей-то победой, поэтому там точно была ничья, то есть у последних мест есть хотя бы по очка у каждой команды. Если же победитель сыграет с кем-то из оставшихся в ничью, то появится команда, у которой будет очка, что противоречит условие. Значит, последняя игра закончилась победой текущего первого места. В итоге команды набрали , , и очка.

ЛПЛП

Рассмотрим ориентированный граф, вершинам которого соответствуют депутаты, а рёбра идут от критикующего депутата к критикуемому.

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

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

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

Всего за турнир было сыграно игр. В каждой игре разыгрывалось либо 5 очков (в случае победы-поражения), либо 4 очка (в случае ничьей). Если бы все игры были сыграны вничью, то суммарное количество очков у всех участников равнялось бы что на 70 меньше, чем реальная сумма очков всех участников. В случае не ничейной игры два её участника суммарно получают на 1 очко больше, чем в случае ничейной игры. Это означает, что ровно 70 игр завершились победой одного из участников, а остальные 50 игр закончились вничью.

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

Нетрудно описать пример для 5 участников. Зафиксируем 11 участников, они сыграли между собой игр. Выберем любые 50 из этих игр, пусть они были сыграны вничью (ясно тогда, что каждый из зафиксированных 11 участников хотя бы раз сыграет вничью), а все остальные игры турнира закончились победой любого из участников. Следовательно, человек ни разу не сыграли вничью. Ясно, что все условия задачи выполняются.

Каждый участник выбывает, потерпев ровно два поражения. В ситуации, когда остались двое “финалистов”, общее количество поражений равно .

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

Учитывая, что и — чётные числа, уравнения и не имеют решений.

Приходим к уравнению , откуда , а общее количество участников равно

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

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

Допустим, что и Тогда то есть город соединён либо с либо с Но соединён с и а — с и

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

Пусть — искомое число помещении в зависимости от количества участников турнира. Сначала докажем индукцией по , что База для и очевидна.

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

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

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

Лемма: в ориентированном графе без циклов есть вершина, из которой не выходит ни одного ребра(только входят).

_________________________________________________________________________________________________________________________________________________________________________________

Доказательство.

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

_________________________________________________________________________________________________________________________________________________________________________________

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

База при одной вершине очевидна.

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

Докажем индукцией по . Для такой граф существует: две вершины, соединённые ребром.

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

Индукция по количеству городов:

База для одного города: сделаем лжеца мэром города, тогда он ответит удовлетворительно, потому что у него вообще нет соседей.

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

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

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

Таким образом, при имеем не более диагоналей.

(a) 

Оценка. Занесём 2 в числитель и оценим каждое слагаемое следующим образом

Получим

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

Пример. Поставим во все вершины получим

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

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

Пример. Найдём в графе максимальную клику, в его вершины поставим а в остальные

Оценка.

Рассмотрим расстановку, на которой достигается Если там есть вершина с 0, удалим её. По предположение

если максимальная антиклика не уменьшилась, и

если максимальная антиклика уменьшилась. Таким образом сделаем все числа ненулевыми.

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

Рассмотрим антиграф, проверим два случая:

1) Если он связен. Значит, для любых вершин и обозначим это число за Следовательно по предположению

Рассмотрим вершину максимальной антиклики.

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

2) Антиграф не связен.