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

Задача 001

01.01.2025 от

В стране $n \geq 2$ городов, каждые два из которых соединены прямым автобусным сообщением в обе стороны. Сколькими способами можно попасть из города $A$ в другой город $B$ , проехав на автобусе ровно $k$ раз? Маршрут может проходить через любой город (в том числе $A$ и $B$ ), а также использовать любой рейс между городами более одного раза.

Подсказка

Попробуйте доказать по индукции.

Решение

Ответ: $\frac{(n-1)^{k}-(-1)^{k}}{n}$ .

Обозначим через $a_{k}$ количество маршрутов длины $k$ из $A$ в $B$ . Выедем из города $A$ и будем ехать каждый раз в произвольный город. На каждом шаге у нас будет ровно $n-1$ вариант, поэтому всего маршрутов длины $k-1$ выходящих из $A$ , будет ровно $(n-1)^{k-1}$ . Заметим, что каждый такой маршрут либо заканчивается в городе $B$ , либо можно сделать еще один ход в $B$ . Поэтому $(n-1)^{k-1}=a_{k}+a_{k-1}(*)$ . Теперь искомую формулу можно доказать методом математической индукции: базой является $a_{1}=1$ , а переход следует из формулы (*).

Задача 006

01.01.2025 от

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

Подсказка

Рассмотрите вершину с наибольшей степенью.

Решение

Рассмотрим город $A$ , из которого можно попасть в наибольшее число городов. Если есть город $B$ , в который нельзя попасть из $A$ , то из $B$ можно попасть в $A$ , а, значит, и во все города, в которые можно попасть из $A$ . Получается противоречие: из $B$ можно попасть в большее число городов, чем из $A$ . Значит из города $A$ можно попасть во все города.

Задача 007

01.01.2025 от

На вечеринку собрались несколько мальчиков и несколько девочек. После вечеринки выяснилось, что для каждой пары девочек есть ровно три мальчика, которые танцевали и с той, и с другой, а для каждой пары мальчиков есть ровно три девочки, которые танцевали и с тем, и с другим. Докажите, что на вечеринке было поровну мальчиков и девочек.

Подсказка

Рассмотрите отдельно пары из двух мальчиков, знакомые с парами из двух девочек.

Решение

Скажем, что пара мальчиков и пара девочек сопряжены, если каждый мальчик из первой пары танцевал с каждой девочкой из второй. Из условия следует, что каждая пара мальчиков сопряжена ровно с тремя парами девочек, а каждая пара девочек — ровно с тремя парами мальчиков. Отсюда следует, что пар мальчиков столько же, сколько пар девочек, а именно — втрое меньше общего числа сопряжённых пар. Таким образом, если мальчиков на вечеринке было $m$ , а девочек — $d$ , то $m(m-1)=d(d-1)$ , откуда $m=d$ .

Задача 011

01.01.2025 от

В некоторой стране 100 городов. Любые два города этой страны соединены дорогой. От этой страны отделилась независимая республика, причем количество дорог, соединяющих города этой республики, равно количеству дорог, ведущих из республики в остальные города этой страны. Сколько городов в отделившейся республике? (Приведите все варианты и докажите, что других нет).

Подсказка

Обозначьте число городов в республике за х.

Решение

Ответ: 67.

Решение: Пусть в отделившейся республике $x$ городов. Тогда количество дорог, соединяющих ее города, равно $x(x-1) / 2$ (из каждого из $x$ городов выходит по $x-1$ дороге, и каждая дорога при этом считается дважды), а количество дорог, ведущих из республики в остальные города страны, равно $x(100-x)$ . По условию $x(x-1) / 2=x(100-x)$ . Сократив на $x$ и решив получившееся уравнение, находим ответ.

Задача 012

01.01.2025 от

Существует ли такая компания из 125 человек, в которой каждый человек имеет ровно 50 знакомых и любые двое людей имеют общего знакомого тогда и только тогда, когда они сами незнакомы?

Подсказка

Разбейте 125 человек на 5 групп.

Решение

Ответ. Существует.
Решение: Разобьём 125 человек на 5 групп по 25 человек, расставим группы по кругу, и пусть каждый дружит со всеми пятьюдесятью из двух соседних групп. Легко проверить, что все условия задачи при этом выполнены.

Задача 015

01.01.2025 от

В классе 29 детей. Каждый из детей послал новогодние подарки 9 своим одноклассникам. Всегда ли найдутся трое детей, ни один из которых не посылал подарки никому из двух других?

Подсказка

Постройте пример. Поставьте детей по кругу.

Решение

Ответ: Нет.

Решение: Построим пример. Выстроим учеников по кругу, и пусть каждый пошлёт подарки 9 следующим по часовой стрелке. Возьмём любых троих и рассмотрим три десятки учеников каждая из которых состоит из одного из трёх взятых и девятерых, которым он послал подарки. Если никто из этих троих не посылал никому подарка, то три этих десятки учеников не должны пересекаться. Но тогда в классе не меньше 30 учеников, а по условию их там 29.

Задача 016

01.01.2025 от

Любые два натуральных числа от 1 до 100 включительно соединены стрелкой, ведущей от меньшего числа к большему. Как раскрасить эти стрелки в красный и синий цвета так, чтобы любой одноцветный путь проходил не более, чем по девяти стрелкам?

Подсказка

Разделите числа на 10 групп.

Решение

Разобьём числа на десять десятков: $1-10,11-20, \ldots, 91-100$ , и числа из одного десятка будем соединять синей стрелкой, а из разных десятков — красной. Понятно, что по синим стрелкам мы не выйдем за пределы десятка, и потому пройдем не больше 9 стрелок, а идя по красным стрелкам, мы каждый раз будем попадать в новый десяток и также пройдем не больше 9 стрелок.

Задача 021

01.01.2025 от

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

Подсказка

Попробуйте для начала подумать над компанией из 150 человек.

Решение

Ответ: 151.
Решение: Допустим, удалось выбрать 151 человека, не знакомых друг с другом. У них вместе 453 знакомства с оставшимися 149 людьми, но у тех вместе всего 447 знакомств — противоречие. Таким образом, среди любых 151 человека найдутся двое знакомых. Покажем, что 150 человек, не знакомых друг с другом, могут найтись. Разобьём компанию на 50 шестёрок, каждую шестёрку — на две тройки, и пусть в каждой шестёрке каждый человек из одной тройки знаком с каждым человеком из другой; в набор из 150 человек возьмём по одной тройке из каждой шестёрки.

Задача 023

01.01.2025 от

В однокруговом чемпионате по матбоям участвовали 16 команд из 16 разных школ. Каждый бой проходил в одной из школ-участниц. Могло ли по окончании чемпионата случиться, что каждая команда сыграла во всех школах, кроме своей?

Подсказка

Сколько боёв было сыграно в любой из школ?

Решение

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

Задача 028

01.01.2025 от

В стране 300 городов. Некоторые пары городов соединены дорогами. Оказалось, что из каждого города выходит ровно 10 дорог. Страна распалась на две республики Иксия и Игрекия. В Иксии оказалось 200 городов, а в Игрекии — 100 городов. Оказалось, что число дорог, соединяющих города Иксии, равно $x$ , а дорог, соединяющих города Игрекии, равно $y$ . Чему может быть равно $x-y$ ?

Подсказка

Пусть из Иксии в Игрекию ведёт $z$ дорог. Сколько ещё дорог в республиках?

Решение

Ответ. 500. Решение. Пусть из Иксии в Игрекию ведёт $z$ дорог. Тогда из городов Иксии в совокупности выходит $10 \cdot 200=2 x+z$ дорог, а из городов Игрекии — $10 \cdot 100=2 y+z$ дорог ( $x$ и $y$ умножаются на 2 , так как каждая дорога, соединяющая города одной республики, считается тут дважды). Вычитая два полученных равенства и деля результат пополам, получаем ответ.