Кубок Колмогорова — Страница 3 — Задачи на Графы

Задача 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 , а значит, это будет простой цикл, который мы легко покрасим в три цвета.

Задача 059

01.01.2025 от

В стране $N$ городов. Некоторые пары городов соединены двусторонними авиарейсами, каждый рейс имеет цену, большую 1000 рублей, причём из любого города можно добраться до любого другого (возможно, с пересадками). Компания публикует сборник, в котором для каждой из $N(N-1) / 2$ пар городов указана минимальная цена, которую надо заплатить, чтобы добраться от одного из них до другого; в конце сборника указывается сумма всех этих $N(N-1) / 2$ чисел. В некоторый момент компания уменьшила стоимость одного из рейсов на 1000 рублей. Докажите, что итоговая сумма в новом сборнике будет отличаться от старой не более, чем на $250 N^{2}$ .

Подсказка

Обозначим два города, между которыми уменьшили стоимость рейса, через $X$ и $Y$ . Пусть $A$ — множество городов, из которых после уменьшения дешевле добраться до $X$ , чем до $Y$ , в том числе в множество $A$ входит сам город $X$ . Пусть $B$ множество городов, из которых добраться до $Y$ не дороже, чем до $X$ , в том числе в множество $B$ входит сам город $Y$ . Что будеь если при проезде самым дешевым путем между городами $U$ и $V$ множества $A$ мы сначала доезжаем из $U$ до $X$ , потом летим из $X$ в $Y$ по удешевленному рейсу, а затем долетаем из $Y$ в $V$ .

Решение

Пусть при проезде самым дешевым путем между городами $U$ и $V$ множества $A$ мы сначала доезжаем из $U$ до $X$ , потом летим из $X$ в $Y$ по удешевленному рейсу, а затем долетаем из $Y$ в $V$ . Тогда, если из $X$ сразу полететь в $V$ по пути наименьшей стоимости, мы заплатим меньшую цену за весь путь: ведь цена перелета между $X$ и $Y$ все равно осталась положительной, и хотя бы эту цену мы сэкономим. Аналогичны рассуждения для двух вершин из множества $B$ . Поэтому путь минимальной стоимости между двумя вершинами одного множества не содержит рейс из $X$ в $Y$ .

Обозначим количество городов в множестве $A$ через $a$ . Тогда в множестве $B$ всего $N-a$ городов. Стоимость самого дешевого пути между городами одного множества, как было показано выше, не уменьшилась. Значит, лишь между $a(N-a)$ парами городов из разных множеств стоимость самого дешевого пути могла уменьшиться. Это количество пар не больше $N^{2} / 4$ , по неравенству между средними арифметическим и геометрическим.

Новый самый дешевый путь между городами из разных множеств проходит по удешевленному ребру $X Y$ не более одного раза, а до удешевления стоимость такого же пути была не ниже стоимости самого дешевого пути между этими городами. Поэтому для каждой пары городов из разных множеств стоимость самого дешевого пути уменьшилась не более, чем на 1000. Значит, итоговая сумма будет отличаться от старой не более, чем на $250 N^{2}$ рублей.

Задача 060

01.01.2025 от

В стране несколько городов, один из которых — Москва. Некоторые пары городов соединены двусторонними дорогами. Мэр хочет обгединить Москву ещё с п городами в большую Москву так, чтобы (1) между любыми двумя городами большой Москвы можно было проехать по дорогам, не попадая в города вне неё, и (2) было ровно $k$ городов вне большой Москвы, соединённых хотя бы одной дорогой с большой Москвой. Докажите, что есть не более $C_{n+k}^{k}$ способов совершить такое обгединение.

Подсказка

Пронумеруем вершины, кроме Москвы, произвольным образом.
Будем красить города из большой Москвы в красный цвет, а их соседей в зелёный цвет. То есть мэру нужно покрасить $n$ городов в красный, а $k$ других городов в зелёный.

Теперь построим соответствие способу покраски способ расставить в ряд $k$ зелёных и $n$ красных символов (способов сделать это $C_{n+k}^{k}$ ). Для удобства сначала будем писать не просто символы, а номера городов, после чего забудем сами номера, оставив только строчку цветных символов.

Решение

На первом этапе алгоритма выпишем в возрастающем порядке номера городов, соседних с Москвой (все они покрашены!). При этом мы покрасим красные в розовый, а зелёные так и оставим зелёными. На очередном шаге будем брать строчку, брать в ней самый левый розовый номер $x$ , и записывать в конец строки номера всех его ещё не выписанных соседей (все они покрашены!) в порядке возрастания номеров, причём номера красных городов запишем розовым, а зелёных — зелёным. После чего поменяем цвет номера $x$ на красный.

Так как на каждом шаге количество красных номеров увеличивалось на 1 , то процесс закончится.
Докажем, что полученное отображение инъективно. Предположим, есть две покраски городов, дающие одну и ту же последовательность. Тогда существует символ, который соответствует разным номерам в раскрасках; рассмотрим самый левый такой символ. Пусть до него последовательности имели вид $a_{1} a_{2} \ldots a_{t} x$ и $a_{1} a_{2} \ldots a_{t} y$ . В каждой из раскрасок номера $x$ и $y$ появились как соседи красных вершин с выписанными ранее номерами. Но поскольку предыдущие символы совпадали, то должен был совпасть и номер на месте $t+1$ .

Задача 064

01.01.2025 от

Докажите, что у любого конечного множества $A$ натуральных чисел существует подмножество $B$ , удовлетворяющее следующим условиям: если $b_{1}, b_{2} \in B$ различны, то ни одно из чисел $b_{1}, b_{2}$ не делится на другое и ни одно из чисел $b_{1}+1, b_{2}+1$ не делится на другое, а также для любого $a \in A$ найдётся $b \in B$ такое, что или $b$ делится на $a$ , или $a+1$ делится на $b+1$ .

Подсказка

Решение

Рассмотрим двуцветный ориентированный граф, у которого вершинами будут элементы множества $A$ , и от вершины $b$ к вершине $a$ идет синяя стрелка, если $b$ делится на $a$ , и красная, если $a+1$ делится на $b+1$ . Тогда мы хотим выбрать независимое подмножество вершин $B$ такое, что в любую вершину множества $A \backslash B$ ведет стрелка из $B$ .

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

Задача 067

01.01.2025 от

Дано натуральное число п. Назовём словом последовательность из $n$ нулей и единиц, а маской — последовательность из п нулей, единии, и звёздочек. Слово соответствует маске, если оно получено из неё заменой звёздочек на нули и единицы. Рассмотрим набор масок $\mathcal{M}$ , удовлетворяющий следующим двум условиям:

(1) каждое слово соответствует ровно одной маске, и

(2) для каждой из п позиций найдётся маска из $\mathcal{M}$ , в которой в этой позиции стоит не звездочка.

Найдите наименьшее возможное количество масок в таком наборе $\mathcal{M}$ .

Подсказка

Рассмотрим двудольный граф $G$ , в котором вершинами одной из долей будут номера позиций в слове длины $n$ , вершинами второй из долей будут маски, а рёбрами соединим каждую маску с теми позициями, на которых стоит не звездочка. Пусть доля $V_{1}$ это вершины $\{1,2 \ldots, n\}$ , соответствующие номерам позиций, а доля $V_{2}$ это вершины $\left\{u_{1}, u_{2} \ldots, u_{k}\right\}$ , соответствующие маскам.

Решение

Докажем, что в графе $G$ для доли $V_{1}$ выполнено условие леммы Холла. Предположим противное. Рассмотрим в $V_{1}$ минимальное по включению множество $A$ , для которого условие леммы Холла не выполнено. То есть у вершин из $A$ количество соседей меньше, чем $|A|$ , а для любого подмножества $B$ множества $A$ количество соседей у вершин из $B$ хотя бы $|B|$ . Отсюда следует, что у $A$ ровно $|A|-1$ соседних вершин. Без ограничения общности будем считать, что $A=\{1, \ldots, s+1\}$ , а $\left\{u_{1}, \ldots, u_{s}\right\}$ это соседние вершины множества $A$ . Тогда для множества $\{1, \ldots, s\}$ выполнена лемма Холла. Пусть без ограничения общности существует паросочетание $\left(1, u_{1}\right),\left(2, u_{2}\right), \ldots,\left(s, u_{s}\right)$ . Значит, в словах $u_{1}$ , $u_{2}, \ldots, u_{s}$ на $1,2, \ldots, s$ местах соответственно стоят не звёздочки (пусть без ограничения общности там стоят нули). Рассмотрим маски $u_{s+1}, \ldots, u_{k}$ . По построению в этих масках на местах с 1 по $s$ стоят звёздочки. Так как каждое слово можно получить из масок ровно одним способом, то из масок $u_{s+1}, \ldots, u_{k}$ получаются не все слова. Значит, существует множество слов $\underbrace{* * \ldots * *}_{s} \alpha$ (на первых $s$ позициях стоит что угодно, а затем идёт слово $\alpha$ длины $n-s$ ), которое нельзя получить из масок $u_{s+1}, \ldots, u_{k}$ . Тогда слово $\underbrace{1 \ldots 1}_{s} \alpha$ нельзя получить ни из какой маски. Противоречие.

Следовательно, для доли $V_{1}$ выполнено условие леммы Холла. Рассмотрим любое паросочетание, покрывающее долю $V_{1}$ . Пусть это паросочетание $\left(1, u_{1}\right),\left(2, u_{2}\right), \ldots,\left(n, u_{n}\right)$ , а в словах $u_{1}, u_{2}, \ldots, u_{n}$ на $1,2, \ldots, n$ местах соответственно стоят нули. Тогда чтобы получить слово $11 \ldots 11$ нам нужна ещё хотя бы одна маска. Откуда и получаем оценку на $n+1$ .

Задача 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.

Задача 081

01.01.2025 от

В городе есть несколько мальчиков и девочек, некоторые пары знакомы. Оказалось, что в любом множестве $D$ из 8 девочек найдётся (возможно, пустое) подмножество $D^{\prime}$ такое, что любой мальчик, знакомый со всеми девочками из $D^{\prime}$ , знаком ещё хотя бы с одной девочкой из $D$ . Докажите, что в любом множестве $M$ из 300 мальчиков найдётся (возможно, пустое) подмножество $M^{\prime}$ такое, что любая девочка, знакомая со всеми мальчиками из $M^{\prime}$ , знакома ещё хотя бы с одним мальчиком из $M$ .

Подсказка

Решение

Заметим, что $D_{1} \subset D$ может быть взято за $D^{\prime}$ тогда и только тогда, когда ни для какого мальчика множество его знакомых в $D$ не совпадает с $D_{1}$ . Аналогично с $M$ и $M^{\prime}$ . Предположим, что нашлось множество из $M$ мальчиков, в котором нельзя выделить $M^{\prime}$ , удовлетворяющее условию. Тогда для любого $M_{1} \subset M$ найдется девочка, которая в множестве $M$ знакома в точности с мальчиками из $M_{1}$ . Выберем в $M_{1} 300$ мальчиков, из них — 256 , и каждому мальчику сопоставим своё четырёхзначное двоичное число. Выберем 8 девочек так, чтобы $i$ -ая девочка знала в множестве $M$ в точности тех мальчиков, которым сопоставлено число с 1 в $i$ -ом разряде (мальчиков, которым ничего не сопоставлено, все эти девочки не знают). Тогда легко видеть, что в выбранном множестве девочек никакое подмножество нельзя назначить $D^{\prime}$ . Действительно, если $i_{1}, \ldots, i_{k}$ — номера девочек в подмножестве, то мальчик, которому сопоставлено число с единицами в разрядах $i_{1}, \ldots, i_{k}$ и нулями во всех остальных разрядах, из восьми выбранных девочек знает в точности $i_{1}, \ldots, i_{k}$ .