Уральский Турнир Юных Математиков

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

Ответ: 148.

Решение. Пример на 148. Построим ориентированный граф, вершинами которого будут числа от 1 до 100 , а каждое из ребер связывает номер места, на котором стоит том с данным номером, с самим этим номером. Поскольку из каждой вершины этого графа выходит ровно одно ребро, и в каждую его вершину входит ровно одно ребро, все его вершины и ребра разбиваются на непересекающиеся ориентированные циклы. Цикл, в который входит красный том, назовем особым, прочие — обычными. Возьмем любой обычный цикл и добавим в него красный том (пусть его номер равен ): . Затем последовательно поменяем местами красный том со всеми остальными элементами получившегося цикла. В итоге все элементы исходного обычного цикла встанут на предписанные им места, а красный том вернется на исходное место. Проделаем описанную процедуру со всеми обычными циклами длины, не меньшей 2 , а напоследок «прокрутим» особый цикл, после чего все тома окажутся на своих местах, т.е. будут идти в порядке возрастания. При этом на приведение в порядок каждого цикла длины , кроме особого, у нас ушла перестановка, а на особый цикл — перестановка, а всего — перестановки, где — число циклов длины не меньше 2 . Поскольку циклов длины 2 и больше не более 50, мы совершили не больше 148 перестановок. Оценка. Пусть получилось 50 циклов длины 2. На приведение в порядок каждого обычного цикла нужно минимум 3 перестановки: убрать один том, поставить на его место другой и поставить на место другого первый. Еще одна перестановка нужна на особый цикл. Итого .

Если в графе знакомств есть треугольник, то из остальных 17 вершин не выходят ребра. Пусть треугольников нет.

Если в графе знакомств есть треугольник, то из остальных 17 вершин не выходят ребра. Пусть треугольников нет. Заметим, что каждая компонента связности графа знакомств содержит не более 4 вершин (иначе там есть пять вершин, связанные минимум 4 ребрами). Такие компоненты могут иметь вид одиночного ребра, цепи из двух или трех ребер и «»ежа»» из трех ребер, исходящих из одной вершины. Легко проверить, что в каждой такой компоненте можно отметить не менее половины вершин так, чтобы никакие две отмеченные вершины не были связаны ребром. Сделав это, получим не менее 10 отмеченных вершин, попарно не соединенных между собой.

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

Ответ: 27. Решение. Напомним, что через обозначается полный двудольный граф на 6 вершинах, то есть граф, три вершины которого можно покрасить в один цвет, а три — в другой так, что любые две одноцветные вершины будут соединены ребром, а любые две разноцветные — нет. В графе циклов длины 4, потому что цвета вершин в цикле чередуются, и по две вершины каждого цвета в можно выбрать способами. Отсюда получается пример на 27 циклов: достаточно взять три графа , а из двух оставшихся вершин рёбер не проводить.

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

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

Пусть в нашем графе ровно компонент связности вида . Тогда в нём вершин, входящих в «плохие» компоненты, где через каждое ребро проходит не более 3 циклов длины 4. В этих компонентах не более рёбер и, стало быть, не более циклов длины 4, а всего в графе этих циклов не больше, чем . Если же в графе 3 компоненты связности вида , то в этих компонентах 27 циклов длины 4 , а две оставшиеся вершины, не будучи связанными с остальными 18 -ю, новых циклов длины 4 добавить не могут. Итак, циклов длины 4 у нас всегда не более 27.

Отметим в нашем графе любую вершину и построим дерево поиска в глубину с корнем .

Отметим в нашем графе любую вершину и построим дерево поиска в глубину с корнем .

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

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

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

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

Пусть . Всего у 20 ребер 40 концов и легко понять, что есть не менее 12 ребер, концы которых не совпадают с другими концами наших 20 ребер. Выберем 5 таких ребер — пусть это ребра . Обозначим через множество, состоящие из вершин и произвольных 40 вершин не входящих в . Применим операцию ко всем 50 вершинам множества . Тогда на каждом из ребер образуется по 30 треугольников (со всеми вершинами, не входящими в ), а на каждом из 15 оставшихся ребер — по 50 треугольников (со всеми вершинами множества ). Итого получается треугольников.