Низкая сложность — Страница 3 — Задачи на Графы

Задача 063

01.01.2025 от

В турнире по бадминтону участвовало 16 спортсменов. Каждые двое сыграли не более одной игры, при этом ничьих не было. После окончания турнира оказалось, что все игроки одержали различное количество побед. Докажите, что все участники потерпели различное количество поражений.

Подсказка

На турнире можно одержать от 0 до 15 побед. Так как это ровно 16 вариантов, то каждый из этих вариантов встретился у одного из спортсменов.

Решение

На турнире можно одержать от 0 до 15 побед. Так как это ровно 16 вариантов, то каждый из этих вариантов встретился у одного из спортсменов. Следовательно, было сыграно $0+1+2+\ldots+15=15 \cdot 14 / 2$ игр, а это все возможные игры, которые могли быть сыграны. Таким образом, каждый участник сыграл 15 игр, у всех участников разное число побед, поэтому и разное число поражений.

Задача 066

01.01.2025 от

В турнире принимает участие 250 команд, каждая играет с каждой один раз дома и один раз на выезде. Можно ли к каждому матчу приставить одного из 10 судей так, чтобы для каждой команды множества судей, которые будут судить у неё дома, и судей, которые будут судить у неё на выезде, не пересекались?

Подсказка

Сопоставим каждой команде свою пятерку судей.

Решение

Ответ. Можно.

Решение. Сопоставим каждой команде свою пятерку судей. Так как $C_{10}^{5}=252>250$ , такое сопоставление возможно. В качестве судьи матча между командами $A$ и $B$ , где для $A$ матч домашний, выберем любого судью, сопоставленного команде $A$ , но не сопоставленного команде $B$ . Тогда у каждой команды домашние матчи судят только пять судей, которые ей сопоставлены, а выездные матчи — только пять судей, которые ей не сопоставлены.

Задача 070

01.01.2025 от

B стране $n$ городов, некоторые пары из них соединены дорогами с двухсторонним движением. В некоторых городах построены школы, назовём такие города важными. Оказалось, что 1) из каждого города можно добраться до любого другого; 2) каждый не важный город соединён дорогой с важным городом. Для какого наименьшего $k$ всегда можно закрыть все дороги, кроме некоторых $k$ , на ремонт так, чтобы эти два условия сохранились?

Подсказка

Можно оставить только остовное дерево.

Решение

Ответ: $n-1$ . Решение. Рассмотрим граф, вершинами которого являются города, ребрами — дороги. Понятно, что $k \geqslant n-1$ , в противном случае граф на оставшихся ребрах не будет связным. Докажем, что в этом графе всегда можно выделить остовное дерево, удовлетворяющее условиям. Будем последовательно удалять ребра из графа. Пусть в графе к текущему моменту есть цикл, проходящий по вершинам $C_{1} C_{2} \ldots C_{m} C_{1}$ . Предположим, что мы не можем удалить ребро $C_{i} C_{i+1}$ (считаем, что $C_{m+1}=C_{1}$ ) с сохранением всех условий. Тогда один из городов $C_{i}$ и $C_{i+1}$ должен быть важным, а другой — не важным. Поэтому если мы не можем удалить ни одно из ребер цикла, то в нем чередуются важные и не важные города. В этом случае удалим любое ребро из нашего цикла. Каждый не важный город будет по-прежнему соединен с важным. В какой-то момент в графе не останется циклов, а все условия будут выполнены. Поэтому оставшийся граф дерево, и ребер в нем ровно $n-1$ .

Задача 071

01.01.2025 от

В графстве Липшир имеется 100 селений, некоторые из которых соединены дорогами (между двумя селениями может быть не более одной дороги). Древний закон не допускает, чтобы дорога соединяла два селения, каждое из которых соединено со всеми остальными. Какое наибольшее количество дорог может быть в графстве?

Подсказка

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

Решение

Ответ: $\frac{1}{2} \cdot 100 \cdot 98=4900$ .
Решение. Оценка. Каждые два селения, не соединенные дорогой, соединим телеграфным проводом. По закону в графстве нет двух селений, каждое из которых соединено с остальными селениями дорогами. Значит, по крайней мере из 99 селений выходит хотя бы один телеграфный провод. Тогда имеется не менее 50 проводов, и количество дорог не больше разности чисел $\frac{1}{2} \cdot 100 \cdot 99=4950$ (число дорог в полном графе) и 50 (число проводов, которые заменяют собой некоторые «несостоявшиеся» дороги). Пример. Разобьем селения произвольным образом на пары, каждое селение соединим дорогами со всеми остальными, кроме парного ему.

Задача 076

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$ , что противоречит нашему изначальному выбору. Таким образом, вершина наибольшей степени обязана быть соединена со всеми остальными вершинами.

Задача 079

01.01.2025 от

В компании из 100 человек некоторые знакомы друг с другом. Каждую минуту из компании уходит человек, который имеет знакомых больше, чем любой из оставшихся. Через несколько минут такого человека не нашлось. Какое наименьшее количество людей могло остаться к этому моменту в компании?

Подсказка

Предположим, что могло остаться не более двух человек. Рассмотрим момент, когда осталось ровно три человека $A, B, C$ .

Решение

Ответ: 3.

Решение. Оценка. Предположим, что могло остаться не более двух человек. Рассмотрим момент, когда осталось ровно три человека $A, B, C$ . Пусть $A$ тот, у кого больше всех знакомых. Если у $A$ один знакомый, то у кого-то из $B$ и $C$ тоже есть один знакомый (сам $A$ ), но тогда у $A$ не больше всех знакомых. Следовательно, у $A$ два знакомых и он знаком с $B$ и $C$ . Пусть $D$ — человек, который ушел перед $A$ . Так как у $A$ хотя бы два знакомых из $B, C$ и $D$ , то у $D$ их должно быть не менее 3 . Значит, $D$ знаком с $A, B$ и $C$ . Но тогда и у $A$ три знакомых. Противоречие.

Пример. Выстроим людей в ряд и познакомим каждого со всеми, кроме его соседей в ряду. Кроме того, не будем знакомить 1 и 3 человек в ряду. Последний человек в ряду знаком со всеми, кроме одного (если людей больше трех). А все остальные люди в ряду имеют как минимум двух незнакомых. Более того, после ухода последнего получается ряд, вновь удовлетворяющий условиям выше. Следовательно, люди будут уходить, пока не останется 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}$ , знакомый со всеми оставшимися, будет знаком и с Б, что противоречит нашему предположению. Назовем таких игроков А и Б антиподами. Из проведенного рассуждения следует, что при нашем предположении у каждого игрока А есть единственный антипод Б, для которого А в свою очередь является антиподом. Но это значит, что все игроки должны разбиться на пары антиподов, а это невозможно, ибо число игроков нечетно. Противоречие.

Задача 097

01.01.2025 от

Среди 20 людей есть пары знакомых. Известно, что среди любых пяти людей не более трёх знакомств. Докажите, что можно выбрать10 людей, среди которых нет знакомых.

Подсказка

Если в графе знакомств есть треугольник, то из остальных 17 вершин не выходят ребра. Пусть треугольников нет.

Решение

Если в графе знакомств есть треугольник, то из остальных 17 вершин не выходят ребра. Пусть треугольников нет. Заметим, что каждая компонента связности графа знакомств содержит не более 4 вершин (иначе там есть пять вершин, связанные минимум 4 ребрами). Такие компоненты могут иметь вид одиночного ребра, цепи из двух или трех ребер и «»ежа»» из трех ребер, исходящих из одной вершины. Легко проверить, что в каждой такой компоненте можно отметить не менее половины вершин так, чтобы никакие две отмеченные вершины не были связаны ребром. Сделав это, получим не менее 10 отмеченных вершин, попарно не соединенных между собой.