Все задачи — Страница 2 — Задачи на Графы

Задача 011

01.01.2025 от

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

Подсказка

Обозначьте число городов в республике за х.

Решение

Ответ: 67.

Решение: Пусть в отделившейся республике $x$ городов. Тогда количество дорог, соединяющих ее города, равно $x(x-1) / 2$ (из каждого из $x$ городов выходит по $x-1$ дороге, и каждая дорога при этом считается дважды), а количество дорог, ведущих из республики в остальные города страны, равно $x(100-x)$ . По условию $x(x-1) / 2=x(100-x)$ . Сократив на $x$ и решив получившееся уравнение, находим ответ.

Задача 012

01.01.2025 от

Существует ли такая компания из 125 человек, в которой каждый человек имеет ровно 50 знакомых и любые двое людей имеют общего знакомого тогда и только тогда, когда они сами незнакомы?

Подсказка

Разбейте 125 человек на 5 групп.

Решение

Ответ. Существует.
Решение: Разобьём 125 человек на 5 групп по 25 человек, расставим группы по кругу, и пусть каждый дружит со всеми пятьюдесятью из двух соседних групп. Легко проверить, что все условия задачи при этом выполнены.

Задача 013

01.01.2025 от

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

Подсказка

Попробуйте доказать лемму. Если в связном ориентированном графе $k$ вершин и хотя бы $2 k-1$ ребро (причем некоторые пары вершин могут быть соединены ребрами в обоих направлениях), то одно из ребер можно удалить без потери связности.

Решение

Ответ. 197.
Решение: Построим ориентированный граф, вершины которого соответствуют городам, а ребра — дорогам (направление ребра будет соответствовать направлению дороги). Любые две вершины соединены не более, чем одним ориентированным ребром. Полученный граф будет связным (из любой вершины можно попасть в любую другую), но при удалении любого ребра связность теряется.

Построим пример такого графа со 197 ребрами. Он будет состоять из вершин $A, B, \mathrm{C}_{1}, \ldots, \mathrm{C}_{98}$ , и ребер $A \rightarrow C$ , а также $C \rightarrow B_{i}$ и $B_{i} \rightarrow A$ для всех $i$ . Нетрудно проверить, что этот граф подходит.

Докажем лемму: если в связном ориентированном графе $k$ вершин и хотя бы $2 k-1$ ребро (причем некоторые пары вершин могут быть соединены ребрами в обоих направлениях), то одно из ребер можно удалить без потери связности.

Доказательство: Рассмотрим в нашем графе произвольную вершину $A$ . Нетрудно понять, что достаточно отметить в графе $k-1$ ребро, чтобы только по отмеченным вершинам можно было бы добраться из $A$ до любой другой вершины. Аналогично, можно отметить в графе еще $k-1$ ребро так, чтобы по отмеченным вершинам можно было бы добраться из любой другой вершины до $A$ . В графе должны остаться неотмеченные ребра — любое из них можно удалить без потери связности. Лемма доказана.

Перейдем к доказательству утверждения задачи. Из связности графа следует, что в нем есть (ориентированный) цикл $C_{1} \rightarrow C_{2} \rightarrow \ldots \rightarrow C_{m} \rightarrow C_{1}$ . Понятно, что $m \geq 3$ и нет никаких ребер между входящими в цикл вершинами, кроме ребер самого цикла (иначе такое ребро можно удалить без потери связности). Также отметим, что из любой не входящей в цикл вершины А существует не более одного ребра, выходящего к вершинам цикла (если таких ребер хотя бы два, то одно из них можно удалить без потери связности). Аналогично, существует не более одного ребра, выходящего из вершин цикла в А.

Заменим все вершины цикла на одну вершину $C$ и для любой другой вершины $A$ проведем ребро $A \rightarrow C$ , если существует одно из ребер $A \rightarrow C_{i}$ и ребро $C \rightarrow A$ , если существует одно из ребер $C_{i} \rightarrow \mathrm{~A}$ . Получится новый связный ориентированный графG’, в котором ровно на $m$ ребер меньше, чем в исходном графе и удаление любого ребра нарушает связность. (Однако, в этом графе возможно наличие двух ребер разного направления между двумя вершинами.) В графе G’ ровно $100-m+1$ вершина и, по доказанному выше утверждению, не более $2(100-m+1)-2=200-2 m$ ребер. Следовательно, в исходном графе было не более, чем $200-m \leq 200-3=197$ ребер.

Задача 014

01.01.2025 от

На Луне п городов, некоторые из которых соединены платными дорогами так, что из любого города можно добраться до любого другого. Стоимость проезда по пути, проходящему через несколько городов, определяется как цена проезда по самой дорогостоящей дороге этого пути, а стоимость турпоездки из города $A$ в город $B$ — как стоимость проезда из А в В по самому дешевому пути. Докажите, что в прайс-листе лунного турагентства не более $n-1$ различных цен.

Подсказка

Предположите, что в графе есть цикл. Все ли рёбра цикла используются?

Решение

Если граф дорог — дерево, у него $n-1$ ребро, и утверждение задачи очевидно. Если же нет, выбросим самую дорогую из дорог, входящих в циклы. Поскольку можно считать, что эта дорога не используется (обходной путь по циклу не дороже), стоимости проезда между городами эта процедура не изменит. Будем повторять ее, пока не останется дерево.

Задача 015

01.01.2025 от

В классе 29 детей. Каждый из детей послал новогодние подарки 9 своим одноклассникам. Всегда ли найдутся трое детей, ни один из которых не посылал подарки никому из двух других?

Подсказка

Постройте пример. Поставьте детей по кругу.

Решение

Ответ: Нет.

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

Задача 016

01.01.2025 от

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

Подсказка

Разделите числа на 10 групп.

Решение

Разобьём числа на десять десятков: $1-10,11-20, \ldots, 91-100$ , и числа из одного десятка будем соединять синей стрелкой, а из разных десятков — красной. Понятно, что по синим стрелкам мы не выйдем за пределы десятка, и потому пройдем не больше 9 стрелок, а идя по красным стрелкам, мы каждый раз будем попадать в новый десяток и также пройдем не больше 9 стрелок.

Задача 017

01.01.2025 от

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

Подсказка

Попробуйте доказать индукцией по количеству сенаторов.

Решение

Докажем индукцией по числу сенаторов. База. Для трех сенаторов есть только два круговых порядка. Они получаются друг из друга пересадкой двух соседей, которые не в ссоре. Шаг индукции. Найдется сенатор А, который в ссоре не более чем с одним сенатором (иначе часть сенаторов можно будет рассадить по кругу так, что у каждого соседями будут враги). Пусть Б в ссоре с А (а если А дружит со всеми, то Б — любой другой). По предположению индукции, если А уйдет из-за стола, то есть способ рассадить оставшихся в нужном круговом порядке. Однако это можно сделать и при наличии А. Придвинем А к Б (это можно сделать) и попросим А и Б взяться за руки. Считая эту пару сенатором Б, рассадим всех в нужном порядке вышеуказанным способом. Теперь можно А посадить на нужное место, последовательно «отодвигая» его от Б.

Задача 018

01.01.2025 от

На танцах было $2 n$ мальчиков и $2 n$ девочек. Боря танцевал со всеми девочками, Аня танцевала со всеми мальчиками, и для любых двух девочек есть ровно n мальчиков, танцевавших ровно с одной из них. Докажите, что каждый мальчик, кроме Бори, танцевал ровно с $n$ девочками.

Подсказка

Рассмотрите вместе с Аней ещё одну (любую) девочку. Что следует их условия?

Решение

Возьмём Аню и любую другую девочку Д. По условию, ровно с одной девочкой из этих двух танцевало ровно $n$ мальчиков. Так как с Аней танцевали все мальчики, то эти $n$ мальчиков танцевали именно с ней, а остальные $n$ мальчиков танцевали и с ней, и с Д. Итак, с каждой девочкой, кроме Ани, танцевали ровно $n$ мальчиков. Возьмём любых двух таких девочек. Пусть с обеими танцевали $m$ мальчиков. Тогда ровно с одной танцевали $n=2(n-m)$ мальчиков, откуда $m=n / 2$ .

Забудем про Аню и Борю. Тогда каждая из девочек танцевала с $n-1$ мальчиком, а с каждыми двумя девочками танцевали $n / 2-1$ мальчиков. Занумеруем мальчиков и пусть $i$ -ый мальчик танцевал с $d_{i}$ девочками. Тогда троек, состоящих из мальчика и двух девочек, с которыми он танцевал, будет $d_{1}\left(d_{1}-1\right) / 2+\ldots+d_{2 k-1}\left(d_{2 k-1}-1\right) / 2$ . С другой стороны, число таких троек равно $n / 2-1$ , умноженному на количество пар девочек, то есть $(n / 2-1)(2 n-1)(n-1)$ .
Заметим, что

$d_{1}\left(d_{1}-1\right) / 2+\ldots+d_{2 k-1}\left(d_{2 k-1}-1\right) / 2=\left(d_{1}^{2}+\ldots+d_{2 n-1}^{2}\right) / 2-\left(d_{1}+\ldots+d_{2 n-1}\right) / 2 \text {. }$

Так как $d_{1}+\ldots+d_{2 k-1}=(n-1)(2 n-1)$ (считаем ту же сумму «со стороны девочек»), то получаем, что

$d_{1}^{2}+\ldots+d_{2 n-1}^{2}=2(n / 2-1)(2 n-1)(n-1)+(n-1)(2 n-1)=(n-1)^{2}(2 n-1) .$

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

$d_{1}^{2}+\ldots+d_{2 n-1}^{2} \geq\left(d_{1}+\ldots+d_{2 n-1}\right)^{2} /(2 n-1)=(n-1)^{2}(2 n-1)$

причём равенство достигается только при $d_{1}=\ldots=d_{2 k-1}$ . Итак, все $d_{i}$ равны между собой, откуда $d_{i}=n-1$ , что и (вспомним про Аню!) требовалось доказать.

Задача 019

01.01.2025 от

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

Подсказка

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

Решение

Будем доказывать индукцией по числу $n$ вершин. База для $n=3$ и $n=4$ проверяется без труда. Пусть для всех графов с менее чем $n$ вершинами условие выполнено, а в графе $G$ с $n$ вершинами и исходящими степенями 3 не нашлось двух непересекающихся циклов.

Предположим, что в $G$ есть встречные ребра между вершинами $v$ и $w$ . Тогда в $G$ есть цикл $v w$ , и в $G-\{v, w\}$ есть цикл, так как в нем из каждой вершины выходит хотя бы одно ребро. Следовательно, в $G$ нет встречных ребер.

Предположим, что в $G$ есть ребро $u v$ такое, что ни из какой вершины $x \in V(G)$ не выходят ребра в обе вершины $u$ и $v$ . Тогда стянем ребро $u v$ : удалим в $G$ вершины $u$ и $v$ и добавим новую вершину $w$ , в которую входят ребра из тех вершин, из которых входили ребра в $u$ и $v$ , и выходят ребра в те вершины, в которые выходили ребра из $v$ . Обозначим полученный граф через $G^{\prime}$ . В $G^{\prime} n-1$ вершина и степень каждой вершины равна 3 , поэтому для него выполнено индукционное предположение. Но тогда и в $G$ есть два непересекающихся цикла, так как если цикл в $G^{\prime}$ проходил через $w$ , то в $G$ этот проход можно заменить на проход через $v$ или $u v$ .

Осталось разобрать случай, когда каждое ребро имеет «предка», то есть вершину, из которой выходят ребра в оба конца этого ребра. Пусть $v$ — вершина наименьшей входящей степени (обозначим эту степень $d^{-}(v)$ ). Очевидно, $d^{-}(v) \leq 3$ .

(1) $d^{-}(v)=0$ . Тогда ребро, исходящее из $v$ , не имеет предка.
(2) $d^{-}(v)=1$ . Тогда ребро, входящее в $v$ , не имеет предка.
(3) $d^{-}(v)=2$ . Пусть есть ребра $u v$ и $w v$ . Тогда $u$ должно быть предком для $w v$ , а $w$ — для $u v$ , но тогда есть ребра $v w$ и $w v$ , а этот случай мы уже разобрали.
(4) $d^{-}(v)=3$ . Тогда все вершины имеют входящую степень 3. Пусть в вершину $x$ входят ребра $u x, v x, w x$ . Предком каждого из этих ребер должна быть $u, v$ или $w$ . Тогда в индуцированном подграфе на вершинах $u, v, w$ в каждую вершину входит хотя бы одно ребро, а так как в $G$ нет встречных ребер, вершины $u, v, w$ образуют цикл длины 3. Заметим, что вершины, в которые ведут ребра из $x$ , также образуют цикл длины 3 (так как мы можем обратить все ребра и повторить те же рассуждения). $B G$ нет встречных ребер, поэтому мы нашли два непересекающихся цикла.

Задача 020

01.01.2025 от

В классе поровну мальчиков и девочек, и все ученики разного роста. Оказалось, что если мальчик дружит с девочкой, то он дружит и со всеми девочками выше неё; и наоборот — если девочка дружит с мальчиком, то она дружит и со всеми мальчиками выше него. Учитель физкультуры хочет выстроить детей в ряд, начиная с мальчика, так, чтобы любые двое соседей в ряду были друзьями разного пола. Оказалось, что количество способов это сделать — натуральное число $N$ , делящееся на 101. Каким наименьшим количеством нулей может оканчиваться десятичная запись числа $N$ ?

Подсказка

Для начала докажите лемму.

Лемма. $N=\left(a_{1} a_{2} \ldots a_{k}\right)^{2}$ , где $a_{1}, \ldots, a_{k}$ — некоторая последовательность неотрицательных целых чисел такая, что $i \geq a_{i} \geq a_{i+1}-1$ при всех $i=1,2, \ldots, k-1$ .

Решение

Ответ. 48.
Решение: Назовём исследуемые расстановки легальными. Пусть $k$ количество мальчиков. Пример получается при $k=101$ , когда все дружат. Действительно, тогда $N=(101!)^{2}$ , причём 2 входит в 101 ! хотя бы в 50 степени, а 5 — в степени $[101 / 5]+\left[101 / 5^{2}\right]=24$ , ибо $101<5^{3}$ . Значит, $N$ оканчивается ровно 48 нулями.

Сначала выведем оценку из леммы. Поскольку $N$ натурально, $a_{1} \geq 1$ , то есть $a_{1}=1$ . Если $N$ делится на 101 , то одно из чисел $a_{1}, \ldots, a_{k}$ делится на $101-$ скажем, это $a_{j}$ . Из условий $a_{i-1} \geq a_{i}-1$ следует, что среди чисел $a_{1}, \ldots, a_{j-1}$ встретятся все числа от 1 до 100 , то есть $N$ делится на ( $100!)^{2}$ и, следовательно, на $10^{48}$ .

Осталось доказать лемму. Числа $a_{k-i}$ будут определяться так. Выкинем из компании $i$ самых маленьких девочек и $i$ самых больших мальчиков. Тогда $a_{k-i}$ — это количество оставшихся мальчиков, знакомых со всеми оставшимися девочками. Из этого описания немедленно следуют условия на $a_{i}$ , указанные в лемме.

Индукция по $k$ . При $k=1$ имеем $N=1=a_{1}$ . Пусть теперь $k>1$ . Рассмотрим самую маленькую девочку $d$ ; пусть $M$ — множество мальчиков, которые с ней дружат, $|M|=a_{k}$ . Заметим, что $M$ состоит из $a_{k}$ самых высоких мальчиков.

В любой легальной расстановке перед $d$ стоит мальчик $m$ из $M$ , а после неё — либо мальчик $m^{\prime}$ из $M$ , либо никто. Так как $m^{\prime}$ , если он существует, знаком со всеми девочками, то после выбрасывания пары ( $m, d$ ) из расстановки получится легальная расстановка оставшихся детей. Наоборот, в любую легальную расстановку $2(k-1)$ детей, отличных от $m$ и $d$ , пару ( $m, d$ ) можно вставить либо перед произвольным $m^{\prime} \in M\{m\}$ , либо в конец, то есть $a_{k}$ способами.

Далее, поскольку $m$ дружит со всеми, для всех $m \in M$ после выкидывания пары ( $m, d$ ) останутся «одинаковые» компании детей (научным языком, графы их дружб изоморфны). Поэтому в них будет поровну легальных расстановок, и эти количества будут по предположению индукции иметь вид $N^{\prime}=\left(a_{1} a_{2} \ldots a_{k-1}\right)^{2}$ . Итак, для каждого из $a_{k}$ мальчиков из $M$ в каждую из $N^{\prime}$ перестановок можно вставить пару ( $m, d$ ) ровно $a_{k}$ способами. Значит, $N=N^{\prime} a_{k}^{2}$ , что и требовалось.