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

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

Задача 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 разносторонних троек.

Задача 083

01.01.2025 от

Степени всех вершин графа $G$ меньше $\frac{3 n}{2}-1$ (где $n>2$ ), причем среди любых $n+1$ вершин есть две несмежных. Назовем блоком множество из $n$ попарно смежных вершин графа $G$ . Известно, что любые два блока имеют общую вершину. Докажите, что все блоки имеют общую вершину.

Подсказка

Лемма 1. (В.Л. Дольников). В графе $2 n-1$ вершин. Оказалось, что после выкидывания любой вершины графа найдется полный подграф с $n$ вершинами. Тогда в исходном графе найдется полный подграф с $n+1$ вершиной.

Лемма 2. Пусть $L$ — пересечение нескольких блоков графа $G$ , причем $L$ непусто. Тогда $L$ содержит не менее $n-k-1$ вершин.

Решение

Доказательство. Пусть утверждение леммы неверно. Будем считать $n$ наименьшим натуральным числом, для которого существует граф, не удовлетворяющий условию задачи. Рассмотрим граф $H$ , дополнительный к графу из условия. Рассмотрим любой пустой подграф графа $H$ с $n$ вершинами, множество его вершин обозначим через $X$ , а множество остальных вершин через $Y$ . Назовем подмножество $Y$ плохим, если количество вершин в нем больше количества вершин в $X$ , смежных хотя бы с одной вершиной из этого подмножества. Обозначим через $A$ максимальное плохое подмножество (оно может быть и пустым), пусть оно содержит $k$ вершин, тогда в $Y A$ нет плохих подмножеств, поэтому, в силу леммы Холла, каждой вершине $Y A$ можно сопоставить смежную с ней вершину $X$ таким образом, чтобы все эти вершины были различны и не смежны с вершинами из Y $\backslash$ A. Множество не сопоставленных вершин $X$ обозначим через $B$ . Рассмотрим граф $H^{\prime}$ , образованный вершинами $A \cup B$ и ребрами графа $H$ , соединяющими эти вершины. Заметим, что при выкидывании любой вершины $H^{\prime}$ в графе $H$ должен был найтись пустой подграф с $n$ вершинами, но в него могло входить не более, чем $n-k-1$ вершина из ( $X \cup Y$ ) $\backslash(A \cup B)$ , следовательно, остальные $k+1$ вершин должны быть из $A \cup B$ , поэтому в $H^{\prime}$ после выкидывания любой вершины найдется пустой подграф с $k+1$ вершинами, но тогда, в силу минимальности $n$ либо в $H^{\prime}$ найдется пустой подграф с $k+2$ вершинами, либо $k=n$ . В первом случае, добавляя к вершинам этого подграфа вершины из $X \backslash B$ , получим пустой подграф с $n+1$ вершинами, во втором — выкинем вершину из $X$ , несмежную ни с одной вершиной $Y$ , найдем пустой подграф $H$ с $n$ вершинами и добавим к нему эту вершину, получим пустой подграф $H$ с $n+1$ вершинами. Полученное противоречие доказывает утверждение леммы.

Обозначим через $k$ разность максимальной степени графа и $n$ . Из условия следует, что $2 k+2 \leq n$ .

Доказательство. Пусть $T$ — объединение всех блоков, содержащих $L$ . Тогда $|T| \leq n+k+1$ , поскольку любая вершина из $L$ смежна с любой вершиной из $T$ . Ясно, что любой блок, содержащий $L$ , имеет не менее $n-|L|$ вершин в $T L L$ . Пусть $|L|<n-k-1$ . Заметим, что при выкидывании любой вершины из $T L$ найдется блок, содержащий $L$ , но не содержащий выкинутой вершины (поскольку $L$ — пересечение всех блоков, содержащих $L$ ). Но в $T \backslash L$ нет подграфов, содержащих более $n-|L|$ вершин (иначе объединение такого подграфа с $L$ будет полным подграфом графа $G$ , содержащим более $n$ вершин). Тогда $T L$ содержит не менее $2(n-|L|)$ вершин в силу леммы 1 . Следовательно, $2(n-|L|) \leq|\mathrm{T} \backslash \mathrm{L}| \leq n+k+1-|L|$ , откуда $|L| \geq n-k-1$ . Лемма доказана.

Завершение доказательства. Рассмотрим любой блок. Назовем его Н. Рассмотрим пересечение всех блоков, имеющих непустое пересечение с $H$ (включая $H$ ). Будем добавлять эти блоки по одному и следить за пересечением. До тех пор, пока оно непусто, оно содержит не менее $n-k-1$ вершин, в силу леммы 2 . Но тогда следующий добавляемый подграф должен иметь не менее $n-k-1$ общих вершин с $H$ (в силу леммы 2 ), но $2(n-k-1)>n$ (по условию $n>2(k+1)$ ), следовательно новый блок имеет непустое пересечение с пересечением старых.

Задача 084

01.01.2025 от

Ребра полного графа с $n$ вершинами покрашены в несколько цветов таким образом, что каждый цвет встречается не более $n-2$ раз. Докажите, что есть три вершины, все ребра между которыми покрашены в различные цвета.

Подсказка

Предположим противное, пусть в любом треугольнике есть два одноцветных ребра. Рассмотрим вершину, из которой выходит наибольшее количество ребер одного цвета (или любую из них, если таких несколько). Пусть это вершина $A$ , и она соединена ребрами цвета 1 с вершинами $B_{1}, \ldots B_{k}$ . Поскольку $k \leq n-1$ , то остались еще вершины $C_{k+1}, \ldots C_{n-1}$ , каждая из которых соединена с вершиной $A$ ребром какого-то другого цвета.

Решение

Решение 1. Предположим противное, пусть в любом треугольнике есть два одноцветных ребра. Рассмотрим вершину, из которой выходит наибольшее количество ребер одного цвета (или любую из них, если таких несколько). Пусть это вершина $A$ , и она соединена ребрами цвета 1 с вершинами $B_{1}, \ldots B_{k}$ . Поскольку $k \leq n-1$ , то остались еще вершины $C_{k+1}, \ldots C_{n-1}$ , каждая из которых соединена с вершиной $A$ ребром какого-то другого цвета. Рассмотрим вершину $C_{i}$ , пусть она соединена с $A$ ребром цвета $i$ . Тогда $C_{i}$ должна быть соединена с каждой из вершин $B_{1}, \ldots B_{k}$ либо ребром цвета 1 , либо ребром цвета $i$ (иначе будет треугольник с разноцветными сторонами). Если все эти $k$ ребер окрашены в цвет $i$ , то всего из вершины $C_{i}$ выходит $k+1$ ребро цвета $i$ , что противоречит выбору вершины $A$ и цвета 1 . Следовательно, хотя бы одно из этих ребер окрашено в цвет 1. Таким образом, из каждой вершины $C_{k+1}, \ldots C_{n-1}$ выходит хотя бы одно ребро цвета 1 , и всего мы имеем $n-1$ ребро цвета 1 , что противоречит условию. Следовательно, обязательно найдутся три вершины, все три ребра между которыми покрашены в разные цвета.

Решение 2. Пусть в любом треугольнике есть два одноцветных ребра. Так как ребер любого цвета не более $n-2$ , то они образуют несвязный граф на данных нам $n$ вершинах. Для каждого цвета такой граф распадается хотя бы на две компоненты связности. Среди всех таких компонент связности (для всех цветов) найдем наибольшую по количеству вершин компоненты связности $F$ (пусть ее ребра окрашены в цвет 1). Очевидно, существует вершина $A$ , не вошедшая в $F$ . Рассмотрим любую вершину $B_{1}$ из $F$ , она соединена с $B$ ребром не цвета 1 , пусть это ребро цвета 2 . Если вершина $B_{2}$ из $F$ соединена с $B_{1}$ ребром цвета 1 , то $A$ также соединена с $B$ ребром цвета 2 (иначе будет треугольник $A B_{1} B_{2}$ будет иметь разноцветными ребрами). Такими же рассуждениями мы получим, что $A$ соединена со всеми вершинами компоненты связности $F$ ребрами цвета 2 , но тогда существует компонента связности цвета 2 , содержащая все вершины из $F$ и вершину $A$ . Противоречие с максимальностью компоненты связности $F$ .

Задача 085

01.01.2025 от

Архипелаг состоит из 1000 островов, некоторые пары которых соединены мостами, причём от любого острова можно добраться по мостам до любого другого. Оказалось, что для любых четырёх островов $A, B, C, D$ таких, что есть мост между $A$ и $B$ , между $B$ и $C$ , между $C$ и $D$ , также есть мост между $A$ и $C$ или между $B$ и $D$ . Докажите, что есть остров, соединённый мостами со всеми остальными.

Подсказка

Решение

Рассмотрим граф, в котором вершины — архипелаги, ребра — мосты. Выберем в этом графе вершину наибольшей степени, назовем её $B$ . Предположим, что $B$ соединена не со всеми вершинами. Так как граф связный, какая-то вершина, соединенная с $B$ , должна быть соединена с вершиной, не соединенной с $B$ (иначе мы не доберемся от $B$ до тех вершин, с которыми она не соединена). Пусть $B$ соединена с $C, C$ соединена с $D$ , но $B$ не соединена с $D$ . Теперь для любой вершины $A$ , которая соединена с $B$ , мы можем применить условие задачи для пути $A-B-C-D$ и получить, что $A$ соединена с $C$ (так как между $B$ и $D$ нет ребра). Таким образом, $C$ соединена с $B$ , со всеми вершинами, с которыми соединена $B$ , и ещё с вершиной $D$ . Это значит, что её степень больше степени $B$ , что противоречит нашему изначальному выбору. Таким образом, вершина наибольшей степени обязана быть соединена со всеми остальными вершинами.

Задача 086

01.01.2025 от

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

Подсказка

a) Условие означает, что граф — дерево. Петя выбирает произвольную вершину. От каждой вершины существует ровно один путь в выбранную. Все рёбра на этом пути он ориентирует в сторону выбранной вершины.

б) По условию граф связен и содержит цикл. Будем доказывать индукцией по количеству вершин, что Вася может гарантировать себе победу, причём для любой изначальной расстановки стрелок перед его ходом (включая «невозможный» случай, когда все стрелки ведут из вершины, где стоит фишка перед первым ходом Васи).

Решение

Рассмотрим граф, вершинами которого являются города, а рёбрами — дороги.
a) Условие означает, что граф — дерево. Петя выбирает произвольную вершину. От каждой вершины существует ровно один путь в выбранную. Все рёбра на этом пути он ориентирует в сторону выбранной вершины.

Первым ходом Петя перемещает туриста в выбранную вершину. Все ориентированные пути ведут к туристу. Вася разворачивает одно ребро. Турист идёт по нему. Ясно, что все пути снова ведут к нему. Вася снова разворачивает одно ребро и так далее. Поэтому у Пети всегда есть ход и он не проиграет.
б) По условию граф связен и содержит цикл. Будем доказывать индукцией по количеству вершин, что Вася может гарантировать себе победу, причём для любой изначальной расстановки стрелок перед его ходом (включая «невозможный» случай, когда все стрелки ведут из вершины, где стоит фишка перед первым ходом Васи).

База — простые циклы. Пусть в простом цикле $A_{1} A_{2} \ldots A_{n}$ как-то расставлены стрелки на рёбрах и турист смог сделать ход, пойдя из $A_{1}$ в $A_{2}$ . Вася будет разворачивать стрелки перед ним. Поэтому турист не сможет идти в обратную сторону. Допустим, турист смог дойти до $A_{1}$ . Тогда перед ним разворачивают стрелку, и ему некуда идти. Петя проиграл.

Шаг индукции. Граф не является простым циклом. Выберем в нём цикл С минимальной длины. Ясно, что $C$ — простой и не содержит ребёр внутри себя. Поэтому есть вершины вне $C$ . Выберем из них вершину $V$ с максимальным расстоянием до $C$ . Обозначим граф без $V$ буквой $G$ . Ясно, что $G$ связен и содержит цикл.

По предположению индукции в $G$ есть выигрышная стратегия для Васи при любой ориентации рёбер. Внутри $G$ Вася будет следовать ей. Так как в $G$ Петя проигрывает, то турист вынужден будет когда-то пойти в $V$ . Тогда Вася развернёт эту стрелку. Турист выйдет из $V$ , а Вася сделает любой допустимый ход в $G$ . Турист пойдёт внутри $G$ . Сейчас у Васи опять есть выигрышная стратегия в $G$ , которой он и будет следовать. Турист снова будет вынужден зайти в $V$ , уменьшив количество стрелок, идущих из $G$ в $V$ . В конце концов они кончатся, и Петя проиграет в $G$ , если он не проиграл раньше.

Задача 087

01.01.2025 от

В первый день $2^{n}$ школьников играли в пинг-понг «навылет»: сначала сыграли двое, затем победитель сыграл с третьим, победитель этой пары — с четвёртым и т.д., пока не сыграл последний школьник (ничьих в пинг-понге не бывает). Во второй день те же школьники разыграли кубок: сначала произвольно разбились на пары и сыграли в парах, проигравшие выбыли, а победители снова произвольно разбились на пары и сыграли в парах, и т.д. Оказалось, что наборы игравших пар в первый и во второй день были одни и те же (возможно, победители были другие). Найдите наибольшее возможное значение $n$ .

Подсказка

Построим следующий граф: вершины — игроки, рёбра — сыгранные партии. Согласно условию, для обоих турниров этот граф один и тот же. Рассмотрим первый турнир и выберем те партии, победители которых до этого не выигрывали (например, такова первая партия).

Решение

Ответ. 3.

Решение. Построим следующий граф: вершины — игроки, рёбра — сыгранные партии. Согласно условию, для обоих турниров этот граф один и тот же. Рассмотрим первый турнир и выберем те партии, победители которых до этого не выигрывали (например, такова первая партия). Тогда соответствующие рёбра образуют путь, а остальные рёбра одним концом примыкают к этому пути. В частности, если выбросить все висячие вершины, то останется только наш путь без крайних вершин.

Теперь рассмотрим тот же граф как граф кубкового турнира. Если из него выбросить висячие вершины, останется граф турнира на $2^{n-1}$ победителях первого этапа. Он, очевидно, является путём лишь при $n \leq 3$ , в противном случае победитель турнира будет иметь степень не меньше 3 . Значит, $n \leq 3$ .

Осталось привести пример при $n=3$ . Пусть участники пронумерованы от 1 до 8 и пары в кубке таковы (первым указан проигравший, вторым победитель): $1-2,3-4,5-6,7-8,2-4,6-8$ , $4-8$ тогда при игре навылет пары могли быть такими (победитель снова указан вторым): $1-2$ , $2-4,3-4,4-8,7-8,8-6,6-5$ .

Задача 088

01.01.2025 от

У Пети есть колода из 36 карт ( 4 масти по 9 карт в каждой). Он выбирает из неё половину карт (какие хочет) и отдаёт Васе, а вторую половину оставляет себе. Далее каждым ходом игроки по очереди выкладывают на стол по одной карте (по своему выбору, в открытом виде); начинает Петя. Если в ответ на ход Пети Вася смог выложить карту той же масти или того же достоинства, Вася зарабатывает 1 очко. Какое наибольшее количество очков он может гарантированно заработать?

Подсказка

Мы воспользуемся известной леммой Холла о сватовстве.
Лемма. Пусть есть $n$ юношей. Известно, что для каждой группы из $k$ юношей ( $k=1,2$ , $\ldots, n$ ) имеется по крайней мере $k$ девушек, имеющих знакомых среди этой группы юношей. Тогда каждого юношу можно женить на знакомой девушке.

Решение

Доказательство и обсуждение см., например, в статьях: М. Большаков, «Паросочетания и транспортные сети («Квант» №4 за 1970 год); А. Романов, «Задачи и теоремы о представителях» («Квант» №1 за 2015 год); М. Шевцова, «Многократная лемма Холла в задачах про мудрецов» («Квант» № 7 за 2019 год)

В терминах решения 1 объявим чёрные клетки юношами (при этом $n=18$ ), белые девушками, а знакомыми — клетки, находящиеся в одном ряду. Мы докажем, что для каждой группы из $k$ юношей ( $k=4,2, \ldots, 18$ ) имеется по крайней мере $k-3$ девушки, имеющих знакомых среди этой группы юношей. Добавив трёх виртуальных девушек, знакомых со всеми юношами, мы окажемся в условиях леммы Холла. Переженив всех юношей и отбросив не более чем троих, которым достались виртуальные девушки, получим не менее 15 хороших пар.

Пусть есть группа $X$ из $k$ юношей (чёрных клеток). Переставим столбцы, их содержащие, влево, а строки — вниз. Пересечение этих строк и столбцов — прямоугольник площади $S_{1}$ — содержит $X$ , а дополнение к их объединению — прямоугольник площади $S_{2}-$ содержит всех незнакомых с ними девушек. Значит, $k \leq \min \left(S_{1}, 18\right)$ , а количество знакомых с ними девушек не меньше $18-\min \left(S_{2}, 18\right)$ .

Нам достаточно доказать, что $18-\min \left(S_{2}, 18\right) \geq \min \left(S_{1}, 18\right)-3$ , т.е. что $\min \left(S_{1}, 18\right)+\min \left(S_{2}, 18\right) \leq 21$ .

Выражение $F=\min \left(S_{1}, 18\right)+\min \left(S_{2}, 18\right)$ симметрично, поэтому достаточно рассмотреть случай, когда общая вершина $A$ построенных прямоугольников лежит в верхней половине доски. Тогда $S_{2} \leq 18$ .

Отбросим очевидный случай, когда $A$ лежит на границе доски (тогда $S_{1}=0$ или $S_{2}=0$ ). Если $S_{1}<S_{2}$ , то можно сдвинуть $A$ вправо, чтобы стало $S_{1}=18$ (поскольку 18 делится как на 2 , так и на 3 ), при этом $F=S_{1}+S_{2}$ не уменьшится. Если $S_{1}>S_{2}$ , то можно сдвинуть $A$ влево, чтобы стало $S_{1}=18$ , при этом $F=18+S_{2}$ увеличится.

Остался единственный случай $S_{1}=18, S_{2}=3$ , а в нём неравенство выполнено.

Задача 089

01.01.2025 от

На турнир приехали 100 человек. Известно, что среди любых 50 из них есть человек, знакомый с остальными 49. Докажите, что можно найти 52 человека, любые два из которых знакомы между собой.

Подсказка

Выберем из этих 100 человек наибольшее возможное количество пар незнакомых.

Решение

Выберем из этих 100 человек наибольшее возможное количество пар незнакомых. Если таких пар наберется 25 , среди входящих в них 50 человек не найдется никого, кто был бы знаком с 49 остальными — противоречие. Значит, таких пар не больше 24 , и в них входит не больше 48 человек. Понятно, что среди 52 (или большего числа) остальных людей каждый знает каждого, что и требовалось доказать.

Задача 090

01.01.2025 от

На турнир приехал 101 человек. Известно, что среди любых 100 из них есть человек, знакомый со всеми остальными. Докажите, что найдется человек, который знаком со всеми остальными.

Подсказка

Пусть нет игрока, знакомого со всеми остальными. Возьмем любого игрока А. По условию есть игрок Б, знакомый со всеми игроками, кроме А.

Решение

Будем называть участников турнира игроками. Пусть нет игрока, знакомого со всеми остальными. Возьмем любого игрока А. По условию есть игрок Б, знакомый со всеми игроками, кроме А. Уберем игрока Б. Со всеми оставшимися может быть знаком только игрок A : иначе игрок $\mathrm{C} \neq \mathrm{A}$ , знакомый со всеми оставшимися, будет знаком и с Б, что противоречит нашему предположению. Назовем таких игроков А и Б антиподами. Из проведенного рассуждения следует, что при нашем предположении у каждого игрока А есть единственный антипод Б, для которого А в свою очередь является антиподом. Но это значит, что все игроки должны разбиться на пары антиподов, а это невозможно, ибо число игроков нечетно. Противоречие.