9 класс — Страница 2 — Задачи на Графы

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

Задача 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$ , если он не проиграл раньше.

Задача 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$ , а в нём неравенство выполнено.