Средняя сложность — Страница 2 — Задачи на Графы

Задача 032

01.01.2025 от

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

Подсказка

Назовём две непересекающиеся тройки задач запрещённой парой, если задачи, не входящие ни в одну из этих двух троек, образуют выбранную тройку.

Решение

Ответ: 56.

Решение: Пример на 56 команд получаем, выбрав 8 задач и рассмотрев все 56 составленных из них троек: они удовлетворяют всем условиям задачи. Допустим, мы выбрали больше 56 троек задач. Назовём две непересекающиеся тройки задач запрещённой парой, если задачи, не входящие ни в одну из этих двух троек, образуют выбранную тройку. Понятно, что хотя бы одна из двух троек, образующих запрещённую пару, не должна быть выбранной. Поскольку из шести задач можно выбрать три $C_{6}^{3}=20$ способами, каждая выбранная тройка порождает 10 запрещённых пар, причём, очевидно, разные тройки порождают разные запрещённые пары. При этом для каждой тройки задач существует 20 не пересекающихся с ней, то есть каждая тройка входит не больше, чем в 20 запрещённых пар. Если мы выбрали хотя бы 57 троек, у нас не меньше 570 запрещённых пар, в которые входит не менее $570 / 20>28$ различных троек задач. Но из 9 задач можно образовать лишь $C_{9}^{3}=84$ тройки, поэтому невыбранными останутся максимум 27 троек. Значит, какие-то две выбранные задачи образуют запрещённую тройку. Противоречие.

Задача 036

01.01.2025 от

В стране 100 городов и 1000 дорог; каждая дорога соединяет ровно 2 города. Известно, что из любого города можно добраться в другой (возможно, через некоторые другие города) не больше, чем за 8 ч. Мужик на желтой «Калине» хочет объехать все города и вернуться в исходный город. За какое минимальное время он гарантированно может это сделать?

Подсказка

Для построение примеры выделите одну из вершин. А часть рёбер сделайте очень длинными.

Решение

Ответ: 99.8 часов.

Решение: Оценка. Граф городов и дорог не полный, значит, кратчайший путь между какими-то двумя городами проходит через какой-то город. Пусть, например, кратчайший путь от $x_{1}$ до $x_{3}$ проходит через $x_{2}$ . Тогда, цикл $x_{1} \rightarrow x_{2} \rightarrow x_{3} \rightarrow \ldots \rightarrow x_{99} \rightarrow x_{100}$ требует не более $99 \cdot 8$ часов, так как переезд от $x_{1}$ к $x_{3}$ и все остальные переходы требуют не более 8 часов каждый.

Пример. Все города связаны с $x_{2}$ дорогами, требующими 4 часов каждая. Остальные города либо связаны дорогами, либо нет, чтобы общее число дорог равнялось 1000. Все дороги между ними требуют 8 часов. Легко видеть, что оценка достигается.

Задача 041

01.01.2025 от

На конгресс приехало 100 ученых, каждый из которых сделал доклад. В конце каждый заявил, что ему понравилось ровно 75 докладов, сделанных его коллегами на конгрессе. Докажите, что найдутся трое, каждому из которых понравились доклады двух других.

Подсказка

Рассмотрим ученого А, доклад которого понравился наибольшему количеству его коллег (их, как минимум, 75).

Решение

Будем говорить, что ученые А и В взаимны, если им понравились доклады друг друга. Рассмотрим ученого А, доклад которого понравился наибольшему количеству его коллег (их, как минимум, 75). Рассмотрим всех, кому понравился доклад A , и всех, чьи доклады понравились А. Так как тех и других не менее, чем по 75, а всего ученых, кроме А, ровно 99, то найдется хотя бы 51 человек, взаимный с А. Возьмём группу из ровно 51 такого учёного (назовем её s). Для любого ученого из s найдется как минимум $75-49=26$ ученых из s, доклады которых ему понравились. Рассмотрим в s такого ученого B , доклад которого понравился наибольшему числу его коллег из s. Таких будет не менее 26. Тогда так как B понравились не менее, чем 26 докладов из s , среди учёных из s найдется C , который взаимен с B . Тогда $\mathrm{A}, \mathrm{B}$ и C попарно взаимны, что и требовалось доказать.

Задача 042

01.01.2025 от

Каждые два из 21 города соединены прямым рейсом одной из четырёх авиакомпаний. Докажите, что существует замкнутый маршрут из четырех рейсов одной авиакомпании.

Подсказка

Решение

Все маршруты образуют полный граф на 21 вершине, рёбра которого раскрашены в 4 цвета. Если искомого замкнутого маршрута нет, любые две вершины этого графа связаны не более чем одним одноцветным маршрутом длины 2. Стало быть, всего таких маршрутов не более, чем $4 C_{21}^{2}=840$ . С другой стороны, пусть из данной вершины выходит $a, b, c$ и $d$ рёбер первого, второго, третьего и четвёртого цветов соответственно. Тогда число одноцветных маршрутов длины 2 , для которых эта вершина — средняя, равно $(a(a-1)+b(b-1)+c(c- 1)+d(d-1)) / 2=\left(a^{2}+b^{2}+c^{2}+d^{2}-(a+b+c+d)\right) / 2=\left(a^{2}+b^{2}+c^{2}+d^{2}\right) / 2-10$ . По неравенству между средним арифметическим и средним квадратическим имеем: $a^{2}+b^{2}+c^{2}+d^{2} \geq(a+b+c+d)^{2} / 4=100$ . Таким образом, каждая вершина нашего графа является средней минимум для $100 / 2-10=40$ одноцветных маршрутов, причём минимум достигается только в случае, когда из вершины выходит ровно по 5 маршрутов каждого цвета. И только в этом случае сумма количеств одноцветных маршрутов длины 2 по всем вершинам равна 840, в остальных — больше. Но такой случай невозможен, потому что тогда, оставив в нашем графе только рёбра одного какого-то цвета, мы получили бы граф с нечётным числом нечётных вершин.

Задача 043

01.01.2025 от

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

Подсказка

Допустим, утверждение задачи неверно для какого-либо графа на 2008 вершинах. Будем говорить, что вершина $A$ портит вершину $B$ , если вершину $A$ можно перекрасить так, чтобы вершина $B$ , которая не была плохой, стала плохой. Заметим, что если степень вершины не равна 2 , её можно испортить не более чем одним способом.

Решение

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

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

Каждую вершину можно перекрасить двумя способами. Поэтому количество способов, которыми можно испортить вершины нашего графа, равно $2 \times 2008$ . С другой стороны, столько же должно получиться, если просуммировать по всем вершинам количество способов, которыми они могут быть испорчены. Поскольку в этой сумме все слагаемые не больше 2 , все они должны равняться 2. Это возможно только если в нашем графе степень каждой вершины равна 2 . Стало быть, он распадается на непересекающиеся циклы, причём каждую вершину каждого цикла можно испортить двумя способами. Такое возможно только если каждая вершина и те вершины, что идут в цикле через одну от неё, покрашены в три разных цвета. Нетрудно показать, что длина цикла в этом случае должна делиться на 3 . Но 2008 на 3 не делится.

Задача 044

01.01.2025 от

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

Подсказка

Всего из дерева получается нечётное число графов, в которых добавлено ещё одно ребро.

Решение

Пусть $G$ — наш граф, $\mathrm{T}(G)$ — множество всех остовных деревьев графа $G$ , а М( $G$ ) — множество всех остовных подграфов графа $G$ , имеющих ровно один цикл. Рассмотрим произвольное дерево $T \subset \mathrm{~T}(G)$ . В нем нечетное число ребер, следовательно, количество не вошедших в $T$ ребер графа $G$ также нечетно. Если к дереву $T \subset \mathrm{~T}(G)$ добавить любое не вошедшее в него ребро графа $G$ , то получится граф из $\mathrm{M}(G)$ . Всего таким образом из дерева $T$ получается нечетное число графов из $\mathrm{M}(G)$ . Наоборот, рассмотрим любой граф $H \subset \mathrm{M}(G)$ и его единственный цикл $Z$ . Граф $H$ может быть получен добавлением ребра к тем деревьям, которые получаются из $H$ удалением одного из ребер цикла $Z$ . Так как граф $G$ двудольный, то в цикле $Z$ — четное число ребер, следовательно, у графа $H$ — четное число остовных деревьев-«»предков»». Отсюда следует, что в множестве $\mathrm{T}(G)$ четное число остовных деревьев.

Задача 045

01.01.2025 от

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

Подсказка

Построим новый граф, вершинами которого будут остовные деревья нашего графа.

Решение

Пусть $G$ — наш граф, обозначим через $2 k$ количество его вершин. Построим новый граф $H$ , вершинами которого будут остовные деревья графа $G$ . Вершины, соответствующие деревьям $T_{1}$ и $T_{2}$ соединим ребром тогда и только тогда, когда в деревьях $T_{1}$ и $T_{2}$ совпадают $2 k-2$ ребра (то есть одно дерево получается из другого заменой одного ребра). Рассмотрим любое остовное дерево $T$ графа $G$ и рассмотрим любое его ребро $e$ . Уберем ребро $e$ , вершины дерева $T$ распадутся на две компоненты связности $V$ и $U$ . Так как степень каждой вершины графа $G$ четна, то в графе $G$ четное число ребер с одним концом в $V$ и другим концом в $V$ . Заменив ребро $e$ на любое другое ребро между $V$ и $U$ , мы получим все остовные деревья, получающиеся из $T$ заменой ребра $e$ на какое-то другое ребро. Количество таких деревьев нечетно. То же самое верно для любого ребра дерева $T$ . Так как в $T$ нечетное число ребер, то из соответствующей дереву $T$ вершины графа $H$ выходит нечетное число ребер. Это означает, что количество вершин графа $H$ (то есть, остовных деревьев графа $G$ ) четно.

Задача 049

01.01.2025 от

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

Подсказка

Зафиксируем десятерых, любые двое из которых знакомы. Назовём их синими, а остальных десятерых — зелёными.

Решение

Пусть каждые двое знакомых совершат рукопожатие. Зафиксируем десятерых, любые двое из которых знакомы. Назовём их синими, а остальных десятерых — зелёными. Каждый из синих знаком с девятью синими и, стало быть, с пятью зелёными. Значит, всего зелёные совершили с синими 50 рукопожатий. Поскольку в сумме у зелёных должно быть $14 \cdot 10=140$ рукопожатий, 90 из них приходятся на рукопожатия зелёных между собой. Так как каждый из зелёных мог пожать руки только 9 зелёным, отсюда следует, что между зелёными были совершены все возможные рукопожатия, то есть каждый из зелёных дружит с каждым, что и завершает доказательство.

Задача 050

01.01.2025 от

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

Подсказка

Решение

Пусть $M_{1} D_{1}, \ldots, M_{2015} D_{2015}$ — наши пары. Каждую девочку $D_{i}$ соединим с другой девочкой, знакомой с $M_{i}$ . В результате получится граф на вершинах $D_{1}$ , $\ldots, D_{2015}$ с 2015 рёбрами. Нам нужно покрасить этот граф правильным образом в три цвета, это и будет искомая покраска девочек. Рассмотрим компоненту связности построенного графа, пусть в ней $n$ вершин, тогда и рёбер в ней тоже $n$ (Мы провели по одному ребру из каждой вершины этой компоненты связности, из вершин вне компоненты рёбра в нее не входят). Если есть вершина степени 1 , удалим ее, эту вершину можно будет легко докрасить после покраски остальных вершин компоненты. После серии таких операций наша компонента связности будет иметь минимальную степень вершины 2 , а значит, это будет простой цикл, который мы легко покрасим в три цвета.

Задача 052

01.01.2025 от

Дано натуральное число п. В Ёжгороде имеется центральная площадь и п периферийных площадей, а также п улиц, соединяющих центральную площадь с периферийными. Мэр хочет создать Реестр городских объектов, записав в строчку названия всех улии, и площадей. Регламент требует, чтобы название каждой улицы стояло в Реестре правее названий обеих площадей, которые она соединяет. Сколькими способами мэр может составить Реестр?

Подсказка

Докажите индукцией по n

Решение

Ответ: $2^{n} \cdot(n!)^{2}$ последовательностей. Решение. Докажем это индукцией по $n$ . База $n=1$ очевидна.

Индукционный переход $n \rightarrow(n+1)$ . Последняя запись в реестре города с ( $n+1$ ) улицей — это название некоторой улицы. Уберем эту запись, а периферийную площадь этой улицы, упомянутую в реестре ранее, выделим красным цветом. Красная запись может находиться в любом месте оставшегося реестра. При ее удалении получается реестр города с $n$ улицами. Значит, для составления реестра в городе $\mathrm{c}(n+1)$ улицей можно