Гуляем по графу

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

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

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

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

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

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

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

Покажем, что не является максимальным по включению.

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

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

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

на шаге данного алгоритма. Поскольку количество общих ребер увеличивается на число большее, чем количество ребер в перестраиваемом пути

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

1.

имеют общий конец с каким-то путем из

2.

не имеют общих вершин с любым путем из

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

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

1.

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

2.

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

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

Повторим наш алогритм еще раза. После применения c номером мы имеем граф, в котором не более вершин и хотя бы ребер.

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

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

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

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

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

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

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

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

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

Итак, мы доказали, что в кратчайшем маршруте “обратно” нет вершины Следовательно, весь маршрут содержит менее вершин и менее стрелок.

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

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

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

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

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

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

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

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

(а) Тогда проведем перестройку в графе (это возможно, так как ) и получим граф с По предположению, можно получить из перестройками, значит, можно получить и

(b) . Тогда — чередующийся цикл, меньший чем противоречие.

(c) Тогда проведем перестройку в графе (это возможно, так как и получим граф с По предположению, можно получить из перестройками, значит, можно получить и

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

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

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

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

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

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

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

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

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

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

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

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

Cнова переведём самого “дружелюбного” и самого “нелюдимого” в другой класс и т. д. Повторяя эти рассуждения раз, мы переведём в другой класс пар школьников, в каждой из которых ровно один Петин друг. Итак, друзей у Пети