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

Задача 031

01.01.2025 от

В чемпионате по волейболу участвовало $n>2$ команд, каждые две из которых сыграли друг с другом ровно один раз. Оказалось, что для каждых двух команд есть ровно $t$ команд, у которых они обе выиграли. Докажите, что $n=4 t+3$ .

Подсказка

Решение

Возьмем любую команду $A$ . Пусть она выиграла у $k$ команд. Тогда каждая из этих $k$ команд выиграла ровно у $t$ из этих $k$ команд — иначе нарушится условие задачи относительно нее и команды $A$ . Общее число матчей в микротурнире между данными $k$ командами равно $k(k-1) / 2$ с одной стороны и общему числу побед, равному $t k$ — с другой, откуда $k=2 t+1$ . Осталось заметить, что в всем турнире было сыграно $n(n-1) / 2$ матчей и одержано $n(2 t+1)$ побед. Значит, $n(n-1) / 2=n(2 t+1)$ , откуда $n=4 t+3$ .

Задача 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 троек. Значит, какие-то две выбранные задачи образуют запрещённую тройку. Противоречие.

Задача 033

01.01.2025 от

У мальчика Васи в его классе 8 друзей и 11 подруг. Каждый из его друзей дружит с 10 одноклассницами. Для каждых двух мальчиков любая девочка в классе дружит хотя бы с одним из них. Сколько девочек может быть в этом классе?

Подсказка

Пусть девочек $10+k$ . Тогда каждый из друзей Васи не дружит с $k$ девочками.

Решение

Ответ: 11.

Решение: Понятно, что девочек не меньше 11. Пусть их $10+k$ . Тогда каждый из друзей Васи не дружит с $k$ девочками. Тогда всего этих «недружб» — $8 k$ . Если $k>1$ , то $8 k>10+k$ . Следовательно, в этом случае найдётся девочка, которая не дружит хотя бы с двумя друзьями Васи, что противоречит условию.

Задача 034

01.01.2025 от

$m$ и $n$ — натуральные числа, причём $1<m<n-1$ . В компании из $n$ человек некоторые знакомы друг с другом, причём среди любых $m$ человек из этой компании одно и тоже количество пар знакомых. Сколько пар знакомых может быть среди всех $n$ человек?

Подсказка

Надо показать, что в данной компании каждый знаком с каждым.

Решение

Ответ: $n(n-1) / 2$ .
Решение: Надо показать, что в данной компании каждый знаком с каждым. Заметим для начала, что если взять любую группу из $m+1$ человека, у каждого из её членов будет одно и то число же знакомых среди остальных членов этой группы (назовём это число cmeпенью группы). В самом деле, кого бы ни убрать из группы, общее число знакомств среди $m$ оставшихся по условию будет одним и тем же.

Допустим, в компании есть люди, не знакомые между собой. Тогда, поскольку по условию в компании есть и знакомые, найдётся группа $L$ из $m+1$ человека, среди которых есть как не знакомые между собой люди $A$ и $B$ , так и хотя бы двое знакомых между собой. Поскольку $m<n-1$ , найдется человек $C$ , не входящий в $L$ . Заменим в группе $L$ человека $A$ на $C$ . Получится новая группа $M$ . При замене $L$ на $M$ число знакомых человека $B$ среди членов группы не уменьшилось, поэтому степень у $M$ не меньше, чем у $L$ . С другой стороны, после удаления $A$ и добавления $C$ число знакомых у тех, кто был знаком с $A$ , не увеличилось. Поэтому степень у $M$ не больше, чем у $L$ . Стало быть, степени у $M$ и $L$ равны. Поэтому $C$ знаком в $L$ точности с теми же людьми, что и $A$ : ведь при переходе от $L$ к $M$ им надо восполнить потерю знакомства с $A$ .

Пусть $D$ — один из этих людей. Заменим в $L$ человека $D$ на $C$ . Получим некоторую группу $N$ . Поскольку $D$ знаком в $L$ не со всеми (так как не со всеми знаком в ней $A$ ), рассуждая так же, как выше, убеждаемся, что степени групп $L$ и $N$ равны. Но это невозможно, так как при перехо-

де от $L$ к $N$ мы теряем все знакомства человека $D$ , а восполнить можем только на одно меньше, ибо теряем также знакомство $C$ с $D$ . Полученное противоречие показывает, что незнакомых в данной компании быть не может.

Задача 035

01.01.2025 от

10 команд играют турнир. В некоторый момент оказалось, что любые две команды сыграли между собой не более, чем по одному разу, только «»Металлург»» и «»Локомотив»» сыграли дважды. При этом каждая команда сыграла хотя бы один матч. Могло ли так случиться, что в этот момент все команды сыграли различное число игр?

Подсказка

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

Решение

Ответ: Нет. Решение. Допустим, есть команда, не сыгравшая ни одного матча. Тогда каждая из оставшихся команд сыграла не больше 9 матчей: с каждой из остальных восьми плюс один повторный. Получается 9 возможностей $(1,2, \ldots, 9$ матчей) на 19 команд. Но тогда эти команды вместе сыграли $(1+2+\ldots+9) / 2=22,5$ матчей, что невозможно.

Теперь допустим, что каждая команда сыграла хотя бы один матч. Тогда для числа сыгранных матчей получается 10 возможностей $(1,2, \ldots, 10$ матчей) на 10 команд. Но тогда эти команды вместе сыграли $(1+2+\ldots+10) / 2=27,5$ матчей, что также невозможно.

Задача 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 часов. Легко видеть, что оценка достигается.

Задача 037

01.01.2025 от

Каждые два города страны Гельбии соединены односторонним авиарейсом. Региональные бароны превратили страну в федерацию двух республик с общей столицей (каждый город, кроме столицы, принадлежит ровно одной из республик, а столица — обеим). Министерство путей сообщения посчитало количество $N$ маршрутов, проходящих по каждому городу всей страны по одному разу (не возвращающихся в исходный город), а также аналогичные количества $N_{1}$ и $N_{2}$ для каждой из республик. Докажите, что $N \geq N_{1} N_{2}$ .

Подсказка

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

Решение

Построим ориентированный граф, вершины которого соответствуют городам, а рёбра — дорогам. Пусть вершина $w$ соответствует столице, $A$ и $B$ — графы, соответствующие республикам. Сначала сформулируем несложную лемму.

Пусть $P$ и $Q$ — два непересекащихся пути в полном ориентированном графе Т. Тогда существует путь $R$ на вершинах этих двух путей, в котором все вершины пути $P$ следуют в порядке пути $P$ , а все вершины пути $Q$ следуют в порядке пути $Q$ . Этот факт нетрудно доказать индукцией по длине пути $Q$ , вставляя по очереди его вершины в путь $P$ . Отметим, что лемма верна и для случая, когда один из путей $P$ и $Q$ или они оба — пустые (из 0 вершин). Назовём путь $R$ из леммы склейкой путей $P$ и $Q$ .

Рассмотрим любые гамильтоновы пути $P$ графа $A$ и $Q$ графа $B$ . Эти пути, очевидно, имеют вид $P=P_{1} w P_{2}$ и $Q=Q_{1} w Q_{2}$ (возможно, какие-то из участков $P_{1}, P_{2}, Q_{1}$ и $Q_{2}$ — пустые). По лемме существует путь $R_{1}$ — склейка $P_{1}$ и $Q_{1}$ и путь $R_{2}$ — склейка $P_{2}$ и $Q_{2}$ . Отметим, что если путь $R_{1}$ непустой, то он кончается либо последней вершиной пути $P_{1}$ , либо последней вершиной пути $Q_{1}$ , то есть, из последней вершины пути $R_{1}$ выходит ребро в $w$ . Аналогично, либо путь $R_{2}$ — пустой, либо из $w$ выходит стрелка в первую вершину пути $R_{2}$ . Тогда $R=R_{1} w R_{2}$ — гамильтонов путь в графе $T$ , в котором вершины подграфа $A$ следуют в порядке пути $P$ , а вершины подграфа $B$ следуют в порядке пути $Q$ . Каждой паре гамильтоновых путей ( $P, Q$ ) очевидно, соответствует свой путь $R$ .

Задача 038

01.01.2025 от

Город Сугробск представляет собой квадрат со стороной $100 n$ метров, разбитый прямыми улицами на $n^{2}$ одинаковых кварталов ( $n$ — чётное натуральное число, большее 2). На каждой из $2 n+2$ улиц, идущих по сторонам кварталов от края до края города, введено одностороннее движение. На соседних параллельных улицах движение направлено в разные стороны. В одном из углов города находится автопарк; обе выходящие из этого угла улицы направлены от автопарка. Снегоуборочная машина выезжает из автопарка и начинает убирать снег. Чтобы не портить дорожное покрытие, по уже убранным участкам (кроме перекрестков) машина не ездит. В конце смены машина должна прибыть в противоположный угол города. Какое наибольшее расстояние она может проехать?

Подсказка

Докажите, что наименьшее количество не пройденных отрезков есть $4 n-4$ .

Решение

Ответ. $100\left(2 n^{2}-2 n+4\right)$ .

Решение: Будем считать, что машина едет из левого нижнего в правый верхний угол, а все стороны маленьких квадратов равны 1 . Всего горизонтальных единичных отрезков $n(n+1)$ , тогда всего единичных отрезков $2 n(n+1)$ . Докажем, что наименьшее количество не пройденных отрезков есть $4 n-4$ . Тогда наибольшее количество пройденных отрезков не более $2 n(n+1)-(4 n-4)=2 n^{2}-2 n+4$ . Введем прямоугольную систему координат: левый нижний угол будет иметь координату $(0,0)$ , а верхний правый — ( $n, n$ ). Рассмотрим прямые вида $x+y=k+1 / 2$ , где $k$ целое число от 0 до $2 n-1$ . Очевидно, что ее пересекает поровну вертикальных и горизонтальных отрезков, ввиду симметрии относительно $x=y$ . Так как начальная и конечная точка нашего маршрута находятся по разные стороны от этой прямой, то маршрут пересечет ее нечетное число раз, а, следовательно, один из отрезков будет не пройденным. Итого уже не пройденных отрезков будет 2n. Рассмотрим прямую $x+y=k+1 / 2$ где $k-$ четное дислот че ниных отрезка, пескащих ра сли ренлу. По условию, если аетно, то оба дин ных отрезка ориентированы из ооласти старта в ооласть финиша, а если $a$ — нечетно, то наооорот. Всего отрезков первого типа $-k+2$ , а отрезков второго типа $-k$ . Заметим, что пройденных отрезков первого типа должно быть ровно на один больше, чем пройденных отрезков второго типа. Однако, точки $(k, 0)$ и $(0, k)$ лежат на границе, поэтому в них входит ровно один отрезок, следовательно, для каждой этой точки, один из выходящих отрезков будет не пройденным. Остается не более $k$ отрезков первого типа, и не более $k-1$ отрезков второго типа. Т.е. эта прямая пересекает хотя бы три не пройденных отрезка. Таких прямых $(n-2) / 2$ , и они дают еще $n-2$ не пройденных отрезков. Аналогично, рассматривая прямую $x+y=k-1 / 2$ , где $k$ — четное число от $n+1$ до $2 n-2$ , найдем еще $n-2$ не пройденных отрезков. Всего не пройденных отрезков будет хотя бы $2 n+2(n-2)=4 n-4$ . Оценка доказана.

Приведем пример. Удалим все ребра вида ( $n, 2 k-1)-(n, 2 k)$ при $1 \leq k \leq n / 2$ и вида ( $2 k, 0)-(2 k+1,0)$ при $1 \leq k \leq(n-2) / 2$ . Всего удалено $n-1$ ребро. Далее удалим пути ( $2 k, n)-(2 k, n-1)-(2 k+1, n-1)-(2 k+1, n)$ при $1 \leq k \leq(n-2) / 2$ , а также пути $(0,2 k-1)-(1,2 k-1)-(1,2 k)-(0,2 k)$ при $2 \leq k \leq(n-2) / 2$ . Итого в этих путях $3 n-9$ ребер. Наконец, удалим пути $(0,0)-(0,1),(1,0)-(1,2)-(0,2)$ и $(0, n-1)-(1, n-1)-(1, n)$ . Всего удалено $4 n-4$ ребра. Все не граничные вершины имели степень входяших и исходяших ребер ровно по два, поэтому после удаления они остались равными. Легко проверить, что у всех вершин, лежащих строго на стороне квалрата стапо по одному входнему и исхолящему ребру У начальной и конечной вершины стало по одному исходящему и одному входящему ребру. Пример построен.

Задача 039

01.01.2025 от

Пусть $G$ — связный граф, имеющий хотя бы три вершины. Определим $G^{3}$ как граф на тех же вершинах, в котором соединены ребрами вершины, находящиеся в $G$ на расстоянии не более трех. Докажите, что в графе $G^{3}$ есть гамильтонов цикл.

Подсказка

Для начала рассмотрите вершины, у которых много соседних висячих вершин.

Решение

Разумеется, достаточно доказать теорему для случая, когда $G$ — дерево. Длиной ребра в графе $G^{3}$ мы назовем расстояние между его концами в исходном графе $G$ . Так, у графа $G^{3}$ бывают рёбра длин 1,2 и 3 . Доказательство будет индукцией по количеству вершин. База для дерева из трех вершин очевидна. Пусть для всех деревьев, имеющих меньше вершин, чем $G$ (и хотя бы три вершины), теорема уже доказана. Рассмотрим два случая.
а) В дереве существует вершина w, смежная хотя бы с двумя висячими вершинами. Пусть $v_{1}$ и $v_{2}$ — две висячие вершины, смежные с $w$ и $T=G-v_{2}$ . Можно считать, что $v(T) \geq 3$ , иначе утверждение для графа $G$ доказано в базе. В гамильтоновом цикле $Z$ графа $T^{3}$ есть участок $u v_{1} u^{\prime}$ , который, очевидно, можно заменить на $u v_{1} v_{2} u^{\prime}$ и получить гамильтонов цикл графа $G^{3}$ .
б) Любая невисячая вершина смежна не более, чем с одной висячей.

Рассмотрим вершину $w$ степени хотя бы 3 , к которой присоединён путь $v_{1} \ldots v_{k}$ , заканчивающийся висячей вершиной $v_{k}$ (возможно, $k=1$ ) и дерево $T=G-\left\{v_{1}, \ldots, v_{k}\right\}$ . Понятно, что $v(T) \geq 3$ , в графе $T^{3}$ существует гамильтонов цикл $Z$ , а в цикле $Z$ есть ребро $u u^{\prime}$ , соединяющее две разных компоненты связности графа $T-w$ . Так как длина ребра $u u^{\prime}$ не более трёх а единственный $u u^{\prime}-$ путь в дереве $T$ проходит через $w$ , то хотя бы одна из вершин $u$ и $u^{\prime}$ смежна в $T$ с вершиной $w$ . Пусть $u w \in E(T)$ . При $k=1$ заменим ребро $u u^{\prime}$ на $u v_{1} u^{\prime}$ . Если $k \geq 2$ , заменим $u u^{\prime}$ на $u v_{2} \ldots v_{1} u^{\prime}$ (вставим между $u$ и $u^{\prime}$ сначала $v_{2}$ , затем все вершины с четными номерами, большими двух в порядке возрастания номеров, затем все вершины с нечетными номерами, большими одного в порядке убывания номеров, затем $v_{1}$ ). Легко видеть, что в полученном гамильтоновом цикле графа $G^{3}$ длины всех рёбер не более трёх.

Задача 040

01.01.2025 от

30 кружковцев Дмитрия Андреевича $k$ раз делились на две команды и проводили тренировочный матбой. На каждом матбое Дмитрий Андреевич называл одну из команд хорошей. При каком наименьшем $k$ он, как бы кружковиы ни делились, гарантированно мог сделать так, чтобы каждый ребенок хоть раз побывал в хорошей команде?

Подсказка

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

Решение

Ответ: 5.

Решение. Назовем невезучими детей, которые ни разу еще не побывали в хорошей команде. Стратегия Дмитрия Андреевича состоит в том, чтобы каждый раз называть хорошей команду, куда попала большая часть невезучих. Так ему после первого боя удастся сделать так, чтобы невезучих было не более 15, после второго — не более 7 , после третьего — не более 3 , после четвертого — не более одного. С другой стороны, если дети каждый раз будут делиться так, чтобы количества невезучих в двух командах отличались не более, чем на 1 , Дмитрию Андреевичу не удастся сделать всех везучими за 4 боя.