Подсчёты в графах — Страница 3 — Задачи на Графы

Задача 052

01.01.2025 от

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

Подсказка

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

Решение

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

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

— выбрать периферийную площадь, которую мы будем считать красной (это можно сделать $n+1$ способами),

— взять реестр остальной части города с $n$ улицами (по индукционному предположению имеется $2^{n}(n!)^{2}$ вариантов такого реестра),

— в любое место этого реестра вставить запись о красной площади ( $2(n+1)$ вариантов)

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

Задача 055

01.01.2025 от

На каждом ребре полного графа с 2019 вершинами написано число 1,2 или 3 так, что сумма чисел на рёбрах каждого треугольника не меньше 5. Какова наименьшая возможная сумма всех чисел на рёбрах?

Подсказка

Пример. Выберем 1009 рёбер без общих вершин, на них напишем 1, на остальных рёбрах — 2.

Решение

Ответ. 2019.2018-1009 = 4073333.

Решение. Пример. Выберем 1009 рёбер без общих вершин, на них напишем 1, на остальных рёбрах — 2. Сумма написанных чисел будет как раз 2•(2019•2018/2) $1009=4073333$ . Оценка. Назовём вершину плохой, если из неё выходит больше одного ребра, помеченного единицей. Если в графе нет плохих вершин, то всё в порядке: ребер с единицами не больше 1009, и сумма написанных не ребрах чисел не меньше $2 \cdot(2019 \cdot 2018 / 2)-1009$ . Пусть плохая вершина $A$ есть. Возьмём ребро $A B$ , на котором написана единица, и рассмотрим все треугольники вида $A B C$ . Если на одной из сторон $A C$ или $B C$ такого треугольника написана единица, то на другой должна быть тройка. Во всех таких случаях заменим эти единицу и тройку на две двойки. Сумма написанных на ребрах чисел при этом не изменится, сумма чисел на сторонах любого треугольника останется не меньше 5, а число плохих вершин уменьшится. Повторяя описанную процедуру, мы можем уничтожить все плохие вершины, а для графа без плохих вершин всё уже было доказано.

Задача 056

01.01.2025 от

В кружок записались 111 детей. Оказалось, что есть десять кружковцев, каждый из которых знаком более, чем с $4 / 5$ из остальных 101. Докажите, что найдутся два кружковца, не входящих в эту десятку, таких, что каждый из десятки знает хотя бы одного из этих двоих.

Подсказка

Решение

Назовём десятерых, о которых идёт речь в задаче, знатоками, а остальных членов кружка — дружками. Будем говорить, что знаток портит пару дружков, если он не знает никого из этой пары. По условию каждый знаток знает более 4.101/5, то есть не меньше 81 дружка. Значит, он незнаком самое большее с 20 дружками и может испортить максимум $20 \cdot 19 / 2=190$ пар дружков. Стало быть, вместе все 10 знатоков могут испортить максимум 1900 пар дружков, а всего пар дружков — $101 \cdot 100 / 2=5050$ . Поэтому найдется неиспорченная пара дружков (и даже не меньше 3150 таких пар), что и требовалось доказать.

Задача 058

01.01.2025 от

В компании $n$ человек. У каждого из них не менее 2021 знакомого. При этом нет пятерых людей, попарно знакомых друг с другом. При каком наименьшем $n$ такое возможно?

Подсказка

Решение

Ответ. 2695. Решение. Покажем, как могло оказаться 2695 человек. Разобьём их на 4 группы размером $674,674,674$ и 673 . Сделаем людей внутри одной группы незнакомыми, а в разных — знакомыми. Тогда у каждого человека знакомых минимум $673+674+674=2021$ , а пяти попарно знакомых точно нет.
Докажем, что менее 2695 человек быть не могло. Предположим, что у нас $2694-x$ людей. Тогда у каждого не более $672-x$ незнакомых. Будем набирать группу из попарно знакомых. Когда мы добавляем к ней любого человека, он запретит с учётом себя не более $673-x$ . Поскольку $4(673-x)=2692-4 x<2694-x$ , то после того как наберём не более четверых, не запрещённые останутся, поэтому можно будет добавить человека в нашу группу. Получается, найдётся группа из 5 попарно знакомых.

Задача 061

01.01.2025 от

Дано нечетное число $k>1$ и натуральное $n>k . B$ компании из $n$ школьников среди любых $k$ школьников найдется школьник, знакомый с остальными $k-1$ школьниками. Найдите все значения $n$ и $k$ , при которых можно утверждать, что в такой компании всегда найдется школьник, знакомый со всеми. Знакомства взаимные.

Подсказка

Пусть $n$ четно. Покажем, что можно познакомить между собой $n$ школьников так, что никакой школьник не будет знаком со всеми остальными, но среди любых $k$ из них найдется школьник, знающий оставшихся $k-1$ школьников. Разобьем школьников на пары и познакомим их так, чтобы школьники из одной пары были незнакомы между собой, а из разных пар — знакомы.

Решение

Тогда и только тогда, когда $n$ нечетно. Решение. Пусть $n$ четно. Покажем, что можно познакомить между собой $n$ школьников так, что никакой школьник не будет знаком со всеми остальными, но среди любых $k$ из них найдется школьник, знающий оставшихся $k-1$ школьников. Разобьем школьников на пары и познакомим их так, чтобы школьники из одной пары были незнакомы между собой, а из разных пар — знакомы. Выберем любых $k$ школьников. Поскольку компанию из нечетного числа школьников нельзя разбить на пары, среди них найдется такой, у которого незнакомый ему школьник в эту группу из $k$ человек не вошел. Поэтому этот школьник знает всех остальных $k-1$ школьников. Таким образом, при четном $n$ искомый способ знакомства существует.

Пусть $n$ нечетно. Достаточно показать, что если нет школьника, который знает всех, то условие задачи не выполнено. В компании найдется школьник Вася, которому незнакомы хотя бы два других школьника (иначе компания должна разбиться на пары незнакомых школьников, что при нечетном $n$ невозможно). Покажем, что в этой компании не будет выполнено условие о группе из $k$ школьников. Будем набирать эту группу постепенно. Сначала поместим в нее Васю и каких-то двух незнакомых ему школьников. На каждом шаге будем добавлять в группу двух еще не добавленных в нее незнакомых друг с другом школьников. Поскольку в каждый момент времени количество школьников в группе будет нечетным, то либо на какомто шаге в группе окажется ровно $k$ школьников (и тогда по построению у каждого в группе будет незнакомый ему школьник из группы), либо в какой-то момент окажется, что среди оставшихся школьников все попарно знакомы. Во втором случае у любого оставшегося школьника есть незнакомый ему школьник из группы. Поэтому, если мы доберем группу до $k$ школьников как угодно, то у любого школьника в группе снова будет незнакомый школьник среди остальных школьников группы. Итак, снова найдена группа из $k$ школьников, среди которых нет такого, который знает всех остальных из группы.

Задача 069

01.01.2025 от

В стране 100 городов. Некоторые из них соединены дорогами, причем между любыми двумя городами есть не более одной дороги. Города пронумерованы числами от 1 до 100. Петя совершил 100 путешествий по дорогам страны, каждый раз начиная путешествия в разных городах. Все свои путешествия он осуществляет по следующему правилу. Оказавшись в каком-либо городе $A$ , Петя находит среди всех городов, соединенных с $A$ , город $B$ с наименьшим номером. Если город $B$ уже был посещен в этом путешествии, или из $A$ вообще нет ни одной дороги, путешествие тут же заканчивается в $A$ . $B$ противном случае, Петя перемещается из $A$ в $B$ и продолжает путешествие по этому же правилу. Оказалось, что совершив 100 путешествий, Петя посетил все города страны поровну раз. При каком наибольшем количестве дорог в стране такое возможно?

Подсказка

Рассмотрим город номер 100. Он может быть посещен в двух случаях: 1) мы начали путешествие с него; 2) мы начали путешествие с города $i<100$ и город $i$ соединен только с городом 100.

Решение

Ответ: 2500.

Решение. Оценка. Рассмотрим город номер 100. Он может быть посещен в двух случаях: 1) мы начали путешествие с него; 2) мы начали путешествие с города $i<100$ и город $i$ соединен только с городом 100. Предположим, что все города были посещены хотя бы три раза. Тогда есть хотя бы два города, которые соединены только с городом 100 . Но наибольший из таких городов может быть посещен только один раз (когда путешествие начинается в нем). Если все города посещены 1 раз, то в стране вообще нет дорог, что нас не устраивает. Значит, все города посещены ровно два раза. Удалим город 100 и город $i$ , соединенный только с ним. Мы удалили не более $98+1$ дорог. Для оставшейся части страны всё ещё верно утверждение, что при путешествиях с началом в каждом из городов, все города посещаются поровну раз, так как города $i$ и 100 посещались ровно 2 раза в путешествиях с началом $i$ и 100. Повторяя такие рассуждения, мы будем удалять пары городов, удаляя не более $97,95, \ldots, 1$ дорог. Значит, изначально в стране было не более $1+3+\ldots+99=$ 2500 дорог. Пример: при $i \leqslant 50$ город $i$ соединим с городами с номерами хотя бы $101-i$ . Также соединим попарно города с номерами, большими 50. Тогда начиная в городе $i$ мы перемещаемся в город $101-i$ и останавливаемся. Значит, все города будут посещены дважды. И количество ребер равно $1+2+\ldots+50+50 \cdot 49 / 2=2500$ .

Задача 075

01.01.2025 от

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

Подсказка

Рассмотрим пару знакомых человек: назовем их $u$ и $v$ . В множестве членов компании, отличных от $u$ и $v$ , выделим три множества: $A$ — множество общих знакомых $u$ и $v ; B$ — множество знакомых с $v$ , но не с $u ; C$ множество знакомых с $u$ , но не с $v$ .

Решение

Ответ. ( $x, 1$ ) для любого $x$ .

Решение. Рассмотрим пару знакомых человек: назовем их $u$ и $v$ . В множестве членов компании, отличных от $u$ и $v$ , выделим три множества: $A$ — множество общих знакомых $u$ и $v ; B$ — множество знакомых с $v$ , но не с $u ; C$ множество знакомых с $u$ , но не с $v$ .

Если $V_{1}, V_{2}$ — два непересекающихся множества членов компании, то через $e\left(V_{1}\right)$ обозначаем количество пар знакомых в $V_{1}$ , через $e\left(V_{1}, V_{2}\right)$ — количество пар знакомых, один из которых в $V_{1}$ , а второй — в $V_{2}$ . Количество элементов множества $M$ обозначаем через $|M|$ .
$У$ каждого человека $w \in A$ имеется ровно $x-1$ знакомых в множестве $A \cup C$ (это его общие знакомые с $u$ , отличные от $v$ ). Просуммируем эти количества по всем $w \in A$ . Получаем $|A| \cdot(x-1)=2 e(A)+e(A, C)$ (здесь каждая пара знакомств внутри $A$ посчитана дважды, а каждое знакомство между $A$ и $C$ — один раз). Аналогично, $|A| \cdot(x-1)=2 e(A)+e(A, B)$ . Поэтому $e(A, B)=e(A, C)$ .

Далее, каждый человек в $B$ имеет $y-1$ соседей в $A \cup C$ (это его общие знакомые с $u$ , кроме $v$ ); Суммируя эти количества, получаем $(y-1)|B|=e(A, B)+e(B, C)$ . Аналогично, $(y-1)|C|=e(A, C)+e(C, B)$ . Поскольку $e(A, B)=e(A, C)$ и $e(B, C)= e(C, B)$ , мы приходим к выводу, что $(y-1)|B|=(y-1)|C|$ , а тогда $|B|=|C|$ или $y=1$ .

Если $y>1$ , то мы получили, что любые два знакомых человека имеют одинаковое число знакомых. А поскольку любые два либо знакомы, либо имеют общего знакомого, то такое невозможно, так как Дима и Саша имеют разное число знакомых.

Значит $y=1$ . Осталось показать, что такое действительно бывает. Рассмотрим компанию из $2 x+3$ человек, выделим в ней две группы по $x+1$ человеку и пусть оставшийся — Дима. Пусть Дима знаком со всеми, и внутри каждой из групп также все знакомы со всеми. Тогда для любых двух незнакомых людей (это люди из разных групп) у них есть единственный общий знакомый — Дима. У Димы с человеком из группы ровно $x$ общих знакомых — это остальные люди этой группы. У любых двух людей из одной группы $x$ общих знакомых — остальные люди этой группы и Дима. Также, Дима единственный, кто знаком со всеми, значит у них с Сашей разное число знакомых.

Задача 077

01.01.2025 от

В кружке $n$ ребят, причём любые двое ребят либо дружат, либо враждуют. Оказалось, что у каждого из ребят ровно 10 врагов в этом же кружке, причём если $A$ дружит с $B$ , но враждует с $C$ , то $B$ и $C$ враждуют. Найдите все возможные значения $n$ .

Подсказка

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

Решение

Ответ. 11, 12, 15, 20.

Решение. Если все враги одного из двух друзей являются врагами другого, то у любых двух друзей одни и те же враги. При этом друг моего друга — мой друг, иначе у меня был бы враг, который не враждует с моим другом. Поэтому все кружковцы разбиваются на группы, где каждый дружит с каждым, причём в каждой группе на 10 человек меньше, чем во всём кружке. Пусть в каждой группе $k$ человек. Тогда 10 должно делиться на $k$ , а всего ребят в кружке — $10+k$ . С другой стороны, если $m$ — делитель числа 10 , то кружок, состоящий из $m+1$ группы размера $k=10 / m$ , где любые двое из одной группы дружат, а из разных групп — враждуют, удовлетворяет условию задачи Перебирая теперь делители числа 10, получаем ответ.

Задача 078

01.01.2025 от

В государстве 2018 городов, каждые два соединены либо автобусным, либо железнодорожным маршрутом. Регион — это любое непустое множество, состоящее не более, чем из 1009 городов. Автобусная мобильность региона определяется как отношение числа автобусных маршрутов, идущих из городов региона в города вне региона, к количеству городов в регионе. Железнодорожная мобильность региона определяется аналогично. Пусть $A$ — наименьшая из автобусных мобильностей регионов государства, а $B$ — наименьшая из их железнодорожных мобильностей. Какое наименьшее значение может принимать число $A+B$ ?

Подсказка

Пусть минимум автобусной мобильности дает регион $M$ , а железнодорожной — регион $N$ . Пусть $X=M \cap N, Y=M \backslash X, Z=N \backslash X$ , а $T$ — совокупность всех городов, не входящих ни в $M$ , ни в $N$ .

Пусть количества городов в $X, Y, Z$ и $T$ равны соответственно $a, b, c$ и $d$ . Все дороги, ведущие из $T$ в $X$ и из $Y$ в $Z$ , учитываются при подсчете либо числа автобусных маршрутов, ведущих из $M$ наружу, либо числа железнодорожных маршрутов, ведущих из $N$ наружу. Поэтому в совокупности таких маршрутов не меньше, чем $a d+b c$ , откуда $A+B \geq(a d+b c) / 1009$ , так как по условию в $M$ и $N$ не больше, чем по 1009 городов.

Решение

Ответ. 1.

Решение: Оченка. Пусть минимум автобусной мобильности дает регион $M$ , а железнодорожной — регион $N$ . Пусть $X=M \cap N, Y=M \backslash X, Z=N \backslash X$ , а $T$ — совокупность всех городов, не входящих ни в $M$ , ни в $N$ .

Если ни один из сомножителей $a, b, c$ и $d$ не равен 0 , то $a d+b c \geq(a+d-1)+(b+c-1)=2016$ , откуда $A+B \geq 2016 / 1009>1$ .

Пусть $c=0$ . Тогда во множестве $N$ а элементов, откуда $a \neq 0$ . При этом $a+b+d=2018$ , откуда $d \geq 1009$ и $A+B \geq(a d+b c) / 1009 \geq 1$ . Случай $b=0$ аналогичен.

Пусть, наконец, $b c \neq 0$ , но $a d=0$ . Если $a \neq 0$ , то $d=0$ , откуда $2018=a+b+c<2 a+b+c=(a+b)+(a+c) \leq 2018$ , противоречие. Итак, $a=0$ . Значит, любой из $b c$ маршрутов между $Y$ и $Z$ учитывается в одной из мобильностей с коэффициентом, не меньшим $\frac{1}{\max (b, c)}$ , поэтому $A+B \geq \frac{b c}{\max (b, c)}=\min (b, c) \geq 1$ .

Пример. Пусть город $X$ связан с остальными только железнодорожными маршрутами, а город $Y$ со всеми остальными, кроме $X$ , связан только автобусными маршрутами. Тогда автобусная мобильность города $X$ равна 0 , а железнодорожная мобильность города $Y$ равна 1.

Задача 082

01.01.2025 от

На площадке можно сыграть или в волейбол, или в футбол, или в баскетбол. На площадку пришли 7 команд, и каждая команда сыграла с каждой ровно один матч. Известно, что нет трёх команд, которые друг с другом играли в один и тот же вид спорта. Тройку команд, которые между собой сыграли во все три вида спорта, назовём разносторонней. Какое наибольшее количество разносторонних троек команд могло быть?

Подсказка

Всего троек команд можно составить $7 \cdot 6 \cdot 5 / 2=35$ . Назовем плохой командой не разносторонней тройки ту, которая с двумя другими играла в одну и ту же игру. Так как нет трех команд, которые друг с другом играли в один и тот же вид спорта, в каждой не разносторонней тройке одна плохая команда.

Решение

Ответ. 14.

Решение. Оценка. Всего троек команд можно составить $7 \cdot 6 \cdot 5 / 2=35$ . Назовем плохой командой не разносторонней тройки ту, которая с двумя другими играла в одну и ту же игру. Так как нет трех команд, которые друг с другом играли в один и тот же вид спорта, в каждой не разносторонней тройке одна плохая команда. С другой стороны, каждая команда является плохой самое меньшее в трех тройках. В самом деле, если она играла в один и тот же вид спорта хотя бы с тремя командами, то она образует не разносторонние тройки с каждыми двумя из них. Иначе она играла в каждый вид спорта с двумя командами, и три не разносторонние тройки тоже налицо. Таким образом, не разносторонних троек хотя бы $3 \cdot 7=21$ , а разносторонних — не более $35-21=14$ . Пример. Расставим команды по кругу, и пусть в футбол, баскетбол и волейбол играют между собой те, между которыми по часовой стрелке нет других команд, одна другая команда и две другие команды соответственно. Нетрудно проверить, что тогда получится ровно 14 разносторонних троек.