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

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

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

При хватит нашей оценки. Так как неравенство

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

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

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

Рассмотрим ориентированный граф, в котором вершины — города, ребра — дороги. Из условия, что на любых 16 вершинах есть циклический маршрут, мы понимаем, что из каждой вершины выходит не менее 13 дорог (иначе можно взять вершину и 15 городов, в которые из неё не ведут дороги, и там не найдется цикла), аналогично в каждую входит не менее 13 дорог. Итого, для каждой вершины есть максимум одна, с которой она не соединена. Рассмотрим произвольные 17 вершин. Они не могут разбиться на пары несмежных, поэтому одна из них, назовем её соединена с каждой из 16 оставшихся. Построим на них цикл Пусть ребро направлено от к (иначе в дальнейшем будем двигаться по циклу в другую сторону). Если от идет ребро к то можно проход заменить на проход и получить цикл длины 15. Значит, от идет ребро к Таким образом можно сдвигаться на 3 вершины по циклу. Так как НОД мы обойдем весь цикл и получим, что от всех идет ребро к Но тогда на вершинах …, нельзя построить цикл.

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

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

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

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

Оценим количество ребер между людьми из разных множеств и

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

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

Получаем неравенство:

откуда Это означает, что всего лжецов не менее

Пример. Как и прежде, номер человека будет означать его ответ. Возьмем два множества людей:

и

Пусть в множестве никакие двое людей не дружат друг с другом, а в множестве — любые двое дружат. Далее, пусть человек и дружат тогда и только тогда, когда Тогда у человека всего друг:

У человека будет всего друзей:

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

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

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

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

Автор задачи забыл добавить условие, что в стране нет «треугольников», то есть троек городов, попарно соединённых друг с другом. Без этого условия утверждение задачи неверно.

Рассмотрим множество из города соединим в нём все города со всеми, кроме каких-то городов и Рассмотрим ещё одно множество из города соединим в нём все города со всеми, кроме каких-то городов и

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

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

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

1) Рассмотрим красный шестиугольник и концентрический синий шестиугольник внутри него. Соединим соответственные вершины синими ребрами.

2) Без потери общности можно считать что углы между прямыми содержащими ребра расположены под углами в друг к другу. Рассмотрим произвольный цикл, он является -угольником. Рассмотрим некоторый угол этого -угольнка, если он равен или то примыкающие стороны разноцетны, если же или то ребра одноцветны. Из соображений чётности получаем, что углы и встречаются четное число раз, поэтому сумма углов делится на но с другой стороны сумма углов Получили, что чётное, значит, все циклы имеют сётную длины, а это критерий двудольности.

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

4) Размыкаем синее рёбер в точке пересечения с красным, получаем две точки, соединим их какой-нибудь выпуклой красной кривой, поставим на ней пять точек и отметим "внутри"ещё две точки. Точки на кривой соединяем красными ребрами, а "внутрение"точки друг с другом синими. Осталось из внутренних провести два синих ребра, для этого соединим их точками с кривой.

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

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

Тогда новая средняя степень станет больше

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

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

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

В каждой паре

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

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

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

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

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

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

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

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

Предположим, что из города A нельзя попасть в город B. Пусть C – какой-то из оставшихся 18 городов. Тогда по крайней мере одна их двух авиалиний A–C, B–C отсутствует. Итого из возможных авиалиний отсутствуют не менее 19 (считая линию A–B), то есть линий не больше 171. Противоречие.

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

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

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

Следовательно,

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

Складывая эти неравенства по всем неупорядоченным парам смежных вершин многогранника, получаем

По доказанному выше неравенству отсюда следует требуемая оценка.

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

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

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

1) Пусть в есть «крайняя» вершина из которой выходит ровно одно ребро В графе полученном из удалением вершины и ребра число вершин равно а рёбер – не больше выполнено предположение индукции, поэтому в можно построить красный путь длины с началом в вершине и концом в вершине Тогда ребро не соединяет вершину с одной из или проведя красное ребро из в эту вершину, получим красный путь длины в

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

База индукции - случаи графов с 3 и 4 вершинами - очевидна.

(a) Начертим граф возможных соседей. Рассмотрим три пары вершин в четырехугольниках на графе (они отмечены жирными точками), а именно: (2, 10), (1, 9) и (3, 11) — это вершины с наименьшей степенью (количеством соседей), равной 2.

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

(b) Пример перестановки: 2, 5, 10, 7, 12, 9, 4, 1, 6, 3, 8, 11. Граф (см. рисунок) помогает построить подобный пример.

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

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

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

Наконец, если предка предка не существует, то наше дерево состоит всего из 2 вершин, соединённых ребром, тогда можно взять его целиком.

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

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

Рассмотрим нарисованные окружности как плоский мультиграф (граф с кратными ребрами между вершинами): вершины – точки пересечений, ребра – дуги нарисованных окружностей, ограниченные точками пересечений. В такой интерпретации круглосторонники — это все грани этого графа, кроме «внешней» (т.е. части плоскости, лежащей вне всех окружностей).

Пусть нарисованы ровно окружностей. Согласно формуле Эйлера для плоских графов,

где — число вершин графа, — число ребер, а — – число граней (включая внешнюю).

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

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

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

Значит, число круглосторонников

Найти наименьшее такое, что — значит найти наименьшее натуральное решение неравенства

Решив, получаем, что наименьшее равно соответственно

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

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

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