Найти граф — Задачи на Графы

Задача 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 базисных отрезка, что и требовалось.

Задача 016

01.01.2025 от

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

Подсказка

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

Решение

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

Задача 020

01.01.2025 от

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

Подсказка

Для начала докажите лемму.

Лемма. $N=\left(a_{1} a_{2} \ldots a_{k}\right)^{2}$ , где $a_{1}, \ldots, a_{k}$ — некоторая последовательность неотрицательных целых чисел такая, что $i \geq a_{i} \geq a_{i+1}-1$ при всех $i=1,2, \ldots, k-1$ .

Решение

Ответ. 48.
Решение: Назовём исследуемые расстановки легальными. Пусть $k$ количество мальчиков. Пример получается при $k=101$ , когда все дружат. Действительно, тогда $N=(101!)^{2}$ , причём 2 входит в 101 ! хотя бы в 50 степени, а 5 — в степени $[101 / 5]+\left[101 / 5^{2}\right]=24$ , ибо $101<5^{3}$ . Значит, $N$ оканчивается ровно 48 нулями.

Сначала выведем оценку из леммы. Поскольку $N$ натурально, $a_{1} \geq 1$ , то есть $a_{1}=1$ . Если $N$ делится на 101 , то одно из чисел $a_{1}, \ldots, a_{k}$ делится на $101-$ скажем, это $a_{j}$ . Из условий $a_{i-1} \geq a_{i}-1$ следует, что среди чисел $a_{1}, \ldots, a_{j-1}$ встретятся все числа от 1 до 100 , то есть $N$ делится на ( $100!)^{2}$ и, следовательно, на $10^{48}$ .

Осталось доказать лемму. Числа $a_{k-i}$ будут определяться так. Выкинем из компании $i$ самых маленьких девочек и $i$ самых больших мальчиков. Тогда $a_{k-i}$ — это количество оставшихся мальчиков, знакомых со всеми оставшимися девочками. Из этого описания немедленно следуют условия на $a_{i}$ , указанные в лемме.

Индукция по $k$ . При $k=1$ имеем $N=1=a_{1}$ . Пусть теперь $k>1$ . Рассмотрим самую маленькую девочку $d$ ; пусть $M$ — множество мальчиков, которые с ней дружат, $|M|=a_{k}$ . Заметим, что $M$ состоит из $a_{k}$ самых высоких мальчиков.

В любой легальной расстановке перед $d$ стоит мальчик $m$ из $M$ , а после неё — либо мальчик $m^{\prime}$ из $M$ , либо никто. Так как $m^{\prime}$ , если он существует, знаком со всеми девочками, то после выбрасывания пары ( $m, d$ ) из расстановки получится легальная расстановка оставшихся детей. Наоборот, в любую легальную расстановку $2(k-1)$ детей, отличных от $m$ и $d$ , пару ( $m, d$ ) можно вставить либо перед произвольным $m^{\prime} \in M\{m\}$ , либо в конец, то есть $a_{k}$ способами.

Далее, поскольку $m$ дружит со всеми, для всех $m \in M$ после выкидывания пары ( $m, d$ ) останутся «одинаковые» компании детей (научным языком, графы их дружб изоморфны). Поэтому в них будет поровну легальных расстановок, и эти количества будут по предположению индукции иметь вид $N^{\prime}=\left(a_{1} a_{2} \ldots a_{k-1}\right)^{2}$ . Итак, для каждого из $a_{k}$ мальчиков из $M$ в каждую из $N^{\prime}$ перестановок можно вставить пару ( $m, d$ ) ровно $a_{k}$ способами. Значит, $N=N^{\prime} a_{k}^{2}$ , что и требовалось.

Задача 022

01.01.2025 от

Пусть $A$ — количество способов, которыми можно разбить множество натуральных чисел от 1 до $n$ на непустые подмножества. Пусть $B$ — количество способов разбить множество натуральных чисел от 1 до $n+1$ на непустые подмножества так, чтобы соседние числа были в разных подмножествах. Разбиения, отличающиеся только порядком подмножеств, считаются одинаковыми. Докажите, что $A=B$ .

Подсказка

Для каждого разбиения чисел от 1 до $n$ занумеруем составляющие его подмножества в порядке, в котором идут их наименьшие числа. Построим дерево с вершинами, помеченными числами от 1 до $n$ , маршруты из корня которого в его висячие вершины будут находиться во взаимнооднозначном соответствии с разбиениями чисел от 1 до $n$ на непустые подмножества. Корень занумеруем цифрой 1 : единица всегда в первом подмножестве. Двойка может лежать либо в подмножестве 1 , либо в подмножестве 2 , поэтому на следующем ярусе расположим соответствующие этим двум случаям вершины, помеченные цифрами 1 и 2 . Что можно сделать после этого?

Решение

Для каждого разбиения чисел от 1 до $n$ занумеруем составляющие его подмножества в порядке, в котором идут их наименьшие числа. Построим дерево с вершинами, помеченными числами от 1 до $n$ , маршруты из корня которого в его висячие вершины будут находиться во взаимнооднозначном соответствии с разбиениями чисел от 1 до $n$ на непустые подмножества. Корень занумеруем цифрой 1 : единица всегда в первом подмножестве. Двойка может лежать либо в подмножестве 1 , либо в подмножестве 2 , поэтому на следующем ярусе расположим соответствующие этим двум случаям вершины, помеченные цифрами 1 и 2 . Далее дерево строится по индукции: если уже построены $k$ ярусов, то с каждой вершиной $C k$ -го яруса связано $m+1$ вершин ( $k+1$ )-го яруса, помеченных числами от 1 до $m+1$ , где $m$ — наибольшее число на маршруте из $C$ в корень дерева.

Теперь построим аналогичное дерево для разбиений чисел от 1 до $n+1$ , где соседние числа находятся в разных подмножествах. Из его корня, помеченного единицей, ведет ребро в единственную вершину второго яруса, помеченную двойкой, а из неё — в две вершины третьего яруса, помеченные единицей и тройкой (двойка невозможна, поскольку тогда числа 2 и 3 попадут в одно подмножество). Далее дерево строится по индукции: если уже построены $k$ ярусов, то с каждой вершиной $C k$ -го яруса связано $m$ вершин ( $k+1$ )-го яруса, помеченных числами от 1 до $m+1$ , исключая число, которым помечена вершина $C$ , где $m$ — наибольшее число на маршруте из $C$ в корень дерева.

Осталось заметить, что если у второго дерева удалить единственное ребро, ведущее из корня во второй ярус, то в новом корне (бывшей единственной вершине второго яруса) у него окажется двойка, и потому получившийся обрубок второго дерева изоморфен первому дереву (доказывается индукцией по ярусам совместно с утверждением, что максимальное число на пути из вершины в корень во втором дереве на 1 больше максимального числа на соответствующем пути в первом дереве).

Задача 026

01.01.2025 от

В городе 2015 жителей, которые организовали $n$ клубов. Оказалось, что для каждых двух клубов количество жителей, состоящих хотя бы в одном из них, не больше 2011. Однако для любых трёх клубов хотя бы в одном из них состоит каждый житель города. Найдите наибольшее возможное значение $n$ .

Подсказка

По первому условию для каждых двух клубов $A$ и $B$ найдутся 4 человека, которые в этих клубах не состоят. Но по второму условию эти 4 человека состоят во всех оставшихся клубах.

Решение

Ответ: 32.

Решение: Оценка. По первому условию для каждых двух клубов $A$ и $B$ найдутся 4 человека, которые в этих клубах не состоят. Но по второму условию эти 4 человека состоят во всех оставшихся клубах. Отсюда следует, что четверки, соответствующие разным парам клубов, не пересекаются. Отсюда $4 C_{n}^{2}<2015$ , то есть $n \leq 32$ . Пример. Выделим среди жителей города $C_{32}^{2}=496$ непересекающихся четверок. Каждой из них поставим в соответствие пару клубов, в которых жители, входящие в неё, они не состоят, так, чтобы каждой паре клубов соответствовала какая-то четверка. Остальные (не входящие в четверки) жители состоят во всех клубах.

Задача 032

01.01.2025 от

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

Подсказка

Назовём две непересекающиеся тройки задач запрещённой парой, если задачи, не входящие ни в одну из этих двух троек, образуют выбранную тройку.

Решение

Ответ: 56.

Решение: Пример на 56 команд получаем, выбрав 8 задач и рассмотрев все 56 составленных из них троек: они удовлетворяют всем условиям задачи. Допустим, мы выбрали больше 56 троек задач. Назовём две непересекающиеся тройки задач запрещённой парой, если задачи, не входящие ни в одну из этих двух троек, образуют выбранную тройку. Понятно, что хотя бы одна из двух троек, образующих запрещённую пару, не должна быть выбранной. Поскольку из шести задач можно выбрать три $C_{6}^{3}=20$ способами, каждая выбранная тройка порождает 10 запрещённых пар, причём, очевидно, разные тройки порождают разные запрещённые пары. При этом для каждой тройки задач существует 20 не пересекающихся с ней, то есть каждая тройка входит не больше, чем в 20 запрещённых пар. Если мы выбрали хотя бы 57 троек, у нас не меньше 570 запрещённых пар, в которые входит не менее $570 / 20>28$ различных троек задач. Но из 9 задач можно образовать лишь $C_{9}^{3}=84$ тройки, поэтому невыбранными останутся максимум 27 троек. Значит, какие-то две выбранные задачи образуют запрещённую тройку. Противоречие.

Задача 034

01.01.2025 от

$m$ и $n$ — натуральные числа, причём $1<m<n-1$ . В компании из $n$ человек некоторые знакомы друг с другом, причём среди любых $m$ человек из этой компании одно и тоже количество пар знакомых. Сколько пар знакомых может быть среди всех $n$ человек?

Подсказка

Надо показать, что в данной компании каждый знаком с каждым.

Решение

Ответ: $n(n-1) / 2$ .
Решение: Надо показать, что в данной компании каждый знаком с каждым. Заметим для начала, что если взять любую группу из $m+1$ человека, у каждого из её членов будет одно и то число же знакомых среди остальных членов этой группы (назовём это число cmeпенью группы). В самом деле, кого бы ни убрать из группы, общее число знакомств среди $m$ оставшихся по условию будет одним и тем же.

Допустим, в компании есть люди, не знакомые между собой. Тогда, поскольку по условию в компании есть и знакомые, найдётся группа $L$ из $m+1$ человека, среди которых есть как не знакомые между собой люди $A$ и $B$ , так и хотя бы двое знакомых между собой. Поскольку $m<n-1$ , найдется человек $C$ , не входящий в $L$ . Заменим в группе $L$ человека $A$ на $C$ . Получится новая группа $M$ . При замене $L$ на $M$ число знакомых человека $B$ среди членов группы не уменьшилось, поэтому степень у $M$ не меньше, чем у $L$ . С другой стороны, после удаления $A$ и добавления $C$ число знакомых у тех, кто был знаком с $A$ , не увеличилось. Поэтому степень у $M$ не больше, чем у $L$ . Стало быть, степени у $M$ и $L$ равны. Поэтому $C$ знаком в $L$ точности с теми же людьми, что и $A$ : ведь при переходе от $L$ к $M$ им надо восполнить потерю знакомства с $A$ .

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

де от $L$ к $N$ мы теряем все знакомства человека $D$ , а восполнить можем только на одно меньше, ибо теряем также знакомство $C$ с $D$ . Полученное противоречие показывает, что незнакомых в данной компании быть не может.

Задача 038

01.01.2025 от

Город Сугробск представляет собой квадрат со стороной $100 n$ метров, разбитый прямыми улицами на $n^{2}$ одинаковых кварталов ( $n$ — чётное натуральное число, большее 2). На каждой из $2 n+2$ улиц, идущих по сторонам кварталов от края до края города, введено одностороннее движение. На соседних параллельных улицах движение направлено в разные стороны. В одном из углов города находится автопарк; обе выходящие из этого угла улицы направлены от автопарка. Снегоуборочная машина выезжает из автопарка и начинает убирать снег. Чтобы не портить дорожное покрытие, по уже убранным участкам (кроме перекрестков) машина не ездит. В конце смены машина должна прибыть в противоположный угол города. Какое наибольшее расстояние она может проехать?

Подсказка

Докажите, что наименьшее количество не пройденных отрезков есть $4 n-4$ .

Решение

Ответ. $100\left(2 n^{2}-2 n+4\right)$ .

Решение: Будем считать, что машина едет из левого нижнего в правый верхний угол, а все стороны маленьких квадратов равны 1 . Всего горизонтальных единичных отрезков $n(n+1)$ , тогда всего единичных отрезков $2 n(n+1)$ . Докажем, что наименьшее количество не пройденных отрезков есть $4 n-4$ . Тогда наибольшее количество пройденных отрезков не более $2 n(n+1)-(4 n-4)=2 n^{2}-2 n+4$ . Введем прямоугольную систему координат: левый нижний угол будет иметь координату $(0,0)$ , а верхний правый — ( $n, n$ ). Рассмотрим прямые вида $x+y=k+1 / 2$ , где $k$ целое число от 0 до $2 n-1$ . Очевидно, что ее пересекает поровну вертикальных и горизонтальных отрезков, ввиду симметрии относительно $x=y$ . Так как начальная и конечная точка нашего маршрута находятся по разные стороны от этой прямой, то маршрут пересечет ее нечетное число раз, а, следовательно, один из отрезков будет не пройденным. Итого уже не пройденных отрезков будет 2n. Рассмотрим прямую $x+y=k+1 / 2$ где $k-$ четное дислот че ниных отрезка, пескащих ра сли ренлу. По условию, если аетно, то оба дин ных отрезка ориентированы из ооласти старта в ооласть финиша, а если $a$ — нечетно, то наооорот. Всего отрезков первого типа $-k+2$ , а отрезков второго типа $-k$ . Заметим, что пройденных отрезков первого типа должно быть ровно на один больше, чем пройденных отрезков второго типа. Однако, точки $(k, 0)$ и $(0, k)$ лежат на границе, поэтому в них входит ровно один отрезок, следовательно, для каждой этой точки, один из выходящих отрезков будет не пройденным. Остается не более $k$ отрезков первого типа, и не более $k-1$ отрезков второго типа. Т.е. эта прямая пересекает хотя бы три не пройденных отрезка. Таких прямых $(n-2) / 2$ , и они дают еще $n-2$ не пройденных отрезков. Аналогично, рассматривая прямую $x+y=k-1 / 2$ , где $k$ — четное число от $n+1$ до $2 n-2$ , найдем еще $n-2$ не пройденных отрезков. Всего не пройденных отрезков будет хотя бы $2 n+2(n-2)=4 n-4$ . Оценка доказана.

Приведем пример. Удалим все ребра вида ( $n, 2 k-1)-(n, 2 k)$ при $1 \leq k \leq n / 2$ и вида ( $2 k, 0)-(2 k+1,0)$ при $1 \leq k \leq(n-2) / 2$ . Всего удалено $n-1$ ребро. Далее удалим пути ( $2 k, n)-(2 k, n-1)-(2 k+1, n-1)-(2 k+1, n)$ при $1 \leq k \leq(n-2) / 2$ , а также пути $(0,2 k-1)-(1,2 k-1)-(1,2 k)-(0,2 k)$ при $2 \leq k \leq(n-2) / 2$ . Итого в этих путях $3 n-9$ ребер. Наконец, удалим пути $(0,0)-(0,1),(1,0)-(1,2)-(0,2)$ и $(0, n-1)-(1, n-1)-(1, n)$ . Всего удалено $4 n-4$ ребра. Все не граничные вершины имели степень входяших и исходяших ребер ровно по два, поэтому после удаления они остались равными. Легко проверить, что у всех вершин, лежащих строго на стороне квалрата стапо по одному входнему и исхолящему ребру У начальной и конечной вершины стало по одному исходящему и одному входящему ребру. Пример построен.

Задача 051

01.01.2025 от

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

Подсказка

Цикл длины 4 можно получить, только соединив концы цепи длины 3. Поэтому тот, после хода которого образуется цепь длины 3, проиграл.

Решение

Ответ. Вася.

Решение. Цикл длины 4 можно получить, только соединив концы цепи длины 3. Поэтому тот, после хода которого образуется цепь длины 3, проиграл. Значит, концы цепи длины 2 соединять с другими точками нельзя. Стратегия Васи: после каждого хода Пети соединять ту же красную точку с какой-то синей, которая ещё не соединена ни с какой другой. Тогда после каждой пары ходов Пети и Васи число не соединённых с другими синих точек будет уменьшаться на 2 , и после 50 -го хода Васи каждая синяя точка будет концом цепи длины 2. Своим 51-м ходом Петя создаст цепь длины 3 и проиграет.

Задача 064

01.01.2025 от

Докажите, что у любого конечного множества $A$ натуральных чисел существует подмножество $B$ , удовлетворяющее следующим условиям: если $b_{1}, b_{2} \in B$ различны, то ни одно из чисел $b_{1}, b_{2}$ не делится на другое и ни одно из чисел $b_{1}+1, b_{2}+1$ не делится на другое, а также для любого $a \in A$ найдётся $b \in B$ такое, что или $b$ делится на $a$ , или $a+1$ делится на $b+1$ .

Подсказка

Решение

Рассмотрим двуцветный ориентированный граф, у которого вершинами будут элементы множества $A$ , и от вершины $b$ к вершине $a$ идет синяя стрелка, если $b$ делится на $a$ , и красная, если $a+1$ делится на $b+1$ . Тогда мы хотим выбрать независимое подмножество вершин $B$ такое, что в любую вершину множества $A \backslash B$ ведет стрелка из $B$ .

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