Уральский Турнир Юных Математиков — Задачи на Графы

Задача 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$ , а переход следует из формулы (*).

Задача 002

09.11.202501.01.2025 от admin2

Прямоугольник разбит на 2016 прямоугольничков со сторонами, параллельными его сторонам. Узел — это вершины этих прямоугольничков. Отрезок, лежащий на стороне некоторого прямоугольничка, назовём базисным, если его концы являются узлами и на нем нет других узлов. Какое наименьшее количество базисных отрезков может получиться при разбиении прямоугольника?

Подсказка

Обозначьте узлы за вершины, а базисные отрезки за рёбра. Посчитайте наименьшее количество вершин степени 3.

Решение

Ответ: 4122.

Решение: Рассмотрим граф, вершинами которого являются узлы, а рёбрами — базисные отрезки. Пусть в этом графе $n$ вершин степени $3, m$ вершин степени 4 ; также в нём имеется четыре вершины степени 2.

Посчитаем сумму углов всех прямоугольников. С одной стороны, она равняется $2016 \cdot 360^{\circ}$ . С другой стороны, вершина степени 2 вносит в эту сумму $90^{\circ}$ , вершина степени 3 — $180^{\circ}$ , вершина степени $4-360^{\circ}$ . Следовательно, $2016 \cdot 360^{\circ}=4 \cdot 90^{\circ}+n \cdot 180^{\circ}+m \cdot 360^{\circ}$ , т.е. $n+2 m=4030$ . Пусть количество рёбер в нашем графе равняется $e$ . Тогда $2 e=2 \cdot 4+3 n+4 m$ . Подставляя $4 m=8060-2 n$ , имеем $2 e=8068+n$ . Таким образом, нам нужно доказать, что наименьшее значение, которое может принимать $n$ , равняется 176.

Для начала докажем, что $n \geq 176$ . Проведём через все стороны прямоугольников, не лежащие на сторонах квадрата, прямые. Возьмём какую-нибудь прямую и посмотрим на крайние узлы, оказавшиеся на ней. Соответствующие им вершины, очевидно, не могут иметь степени 2 и 4; значит, они имеют степень 3. Также, очевидно, что никакие две из рассматриваемых вершин не могут совпасть. Следовательно, если $a$ и $b$ — количество вертикальных и горизонтальных прямых соответственно, то вершин степени 3 хотя бы $2(a+b)$ . С другой стороны, эти прямые разбивают квадрат на $(a+1)(b+1)$ прямоугольничков, из которых складываются 2016 прямоугольников из условия. Значит, $(a+1)(b+1) \geq 2016$ . Следовательно, $\quad(a+b+2)^{2} \geq 4(a+1)(b+1) \geq 8064, \quad$ откуда $a+b \geq \sqrt{8064}-2>87, \quad$ а $n \geq 2(a+b) \geq 2 \cdot 88=176$ , что и требовалось.

Теперь приведём пример, в котором $n=176$ . Разделим большой квадрат 44 вертикальными и 44 горизонтальными прямыми на $45^{2}=2025$ маленьких квадратиков. Далее сотрём 9 базисных отрезков, примыкающих к одной из сторон большого квадрата. Тогда прямоугольников разбиения получится ровно 2016, а на каждой из 88 проведённых прямых будет ровно по 2 узла, из которых выходит по 3 базисных отрезка, что и требовалось.

Задача 005

01.01.2025 от

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

Подсказка

Сопоставьте каждому ученику число в двоичной записи.

Решение

Ответ: $2^{n-1}$ .

Решение: Пронумеруем кружки и сопоставим каждому ученику $n$ -значное двоичное число, где в $k$ ом разряде стоит 0 , если ученик не ходит в этот кружок, и 1 , если ходит. Так как для любых двух школьников есть кружок, в который ходит ровно один из них, у разных школьников будут разные коды. Далее, разобьём коды на пары, где коды в каждой из пар не совпадают ни в одном разряде. Так как по условию у любых трёх сопоставленных школьникам кодов должен быть разряд, в котором все три совпадают, из каждой такой пары может быть использовано не больше одного кода. Поэтому школьников не больше, чем половина числа $n$ значных двоичных кодов, то есть не больше $2^{n-1}$ . Пример на $2^{n-1}$ : использованы в точности все коды, начинающиеся с 1 .

Задача 006

01.01.2025 от

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

Подсказка

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

Решение

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

Задача 008

01.01.2025 от

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

Подсказка

Рассмотрите вершину наибольшей степени. Удалите её из графа. Что можно сделать дальше?

Решение

Ответ: 72.

Решение: Обозначим команды точками, а матчи — соединяющими точки отрезками. Возьмем точку, из которой выходит больше всего отрезков, присвоим ей номер 1 и сотрем все исходящие из нее отрезки. После этого рассмотрим точку, из которой выходит больше всего оставшихся отрезков, присвоим ей номер 2, сотрем все исходящие из нее отрезки и т.д. Если из каждой из первых 24 точек перед стиранием выходило не меньше, чем по 2 отрезка, то всего отрезков не менее $2 \times 24+24=72$ , поскольку команды с номерами от 25 до 72 сыграли между собой не менее 24 матчей. Если же из точки 24 перед стиранием выходило не более 1 отрезка, то из точек от 25 до 72 в этот момент тоже выходит не более, чем по одному отрезку, и среди команд с номерами от 24 до 72 нетрудно найти 48 команд, сыгравшие менее 24 матчей. Итак, матчей сыграно не менее 72 . Пример на 72 матча: команды выстраиваются по кругу, и каждая играет со следующей по часовой стрелке. В самом деле, уберем 24 из этих 72 команд. Они уменьшили число сыгранных матчей максимум на $2 \times 24=48$ , поэтому оставшиеся 48 команд сыграли между собой не меньше 24 матчей.

Задача 009

01.01.2025 от

В день Св. Валентина $n$ влюбленных пар провели два однокруговых турнира по пинг-понгу — один для юношей, другой для девушек. Юноша и девушка из каждой пары вместе выиграли $n-1$ игру. Докажите, что количество троек юношей ( $A, B, C$ ), в которых $A$ обыграл $B, B$ обыграл $C$ и $C$ обыграл $A$ , равно количеству таких троек девушек.

Подсказка

Попробуйте сравнить не количество циклических троек, а количество оставшихся троек.

Решение

Занумеруем все пары числами от 1 до $n$ . Пусть в паре с номером $k$ юноша выиграл $a_{k}$ , а девушка $-n-1-a_{k}$ партий. Заметим, что тогда девушка из этой пары проиграла $a_{k}$ партий.

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

Рассмотрим теперь пару номер $k$ . Легко видеть, что количество троек юношей, в которых юноша из $k$ -й пары выиграл обе партии равно $\frac{a_{k}\left(a_{k}-1\right)}{2}$ . Поскольку в каждой нециклической тройке юношей есть ровно один юноша, одержавший две победы, количество таких троек равно $\sum_{k=1}^{n} \frac{a_{k}\left(a_{k}-1\right)}{2}$ . Аналогично, количество троек девушек, в которых девушка из $k$ -й пары обе партии проиграла, также равно $\frac{a_{k}\left(a_{k}-1\right)}{2}$ и, следовательно, количество нециклических троек девушек также равно $\sum_{k=1}^{n} \frac{a_{k}\left(a_{k}-1\right)}{2}$ .

Задача 010

01.01.2025 от

В лагере $2012^{2012}$ детей, у каждого не более трех друзей. Всегда ли можно их построить в ряд так, чтобы между любыми двумя друзьями стояло не более чем 2012 человек?

Подсказка

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

Решение

Ответ: Не всегда.

Решение: Пусть Петя знаком с двоими, каждый из его знакомых — с двоими новыми, каждый из этих четверых — снова с двоими новыми и т.д., пока не перезнакомим всех $2012^{2012}$ детей. В получившемся «двоичном дереве» знакомств на $k$ -ом от Пети ярусе (кроме, возможно, самого последнего) — $2^{k}$ детей, поэтому ярусов в нем не больше, чем $m$ , где $m$ таково, что $2^{m-1}<2012^{2012}<2^{m}$ . Поскольку $2^{11}=2048>2012, m<11 \cdot 2012$ . Допустим, нам удалось построить детей нужным образом. Возьмем самого левого и самого правого. Между ними в построенном нами дереве есть путь длины не более $2 m<22 \cdot 2012$ . Но между любыми двумя соседями на этом пути в строю стоят не более 2012 человек. Поэтому длина строя должна быть не больше 2013•22•2012, что, очевидно, намного меньше, чем $2012^{2012}$ . Противоречие.

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

Задача 014

01.01.2025 от

На Луне п городов, некоторые из которых соединены платными дорогами так, что из любого города можно добраться до любого другого. Стоимость проезда по пути, проходящему через несколько городов, определяется как цена проезда по самой дорогостоящей дороге этого пути, а стоимость турпоездки из города $A$ в город $B$ — как стоимость проезда из А в В по самому дешевому пути. Докажите, что в прайс-листе лунного турагентства не более $n-1$ различных цен.

Подсказка

Предположите, что в графе есть цикл. Все ли рёбра цикла используются?

Решение

Если граф дорог — дерево, у него $n-1$ ребро, и утверждение задачи очевидно. Если же нет, выбросим самую дорогую из дорог, входящих в циклы. Поскольку можно считать, что эта дорога не используется (обходной путь по циклу не дороже), стоимости проезда между городами эта процедура не изменит. Будем повторять ее, пока не останется дерево.