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

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

Задача 003

01.01.2025 от

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

Подсказка

Предположите, что нечётного цикла нет. Что следует из двудольности?

Решение

Пусть данные важные ребра — $a b$ и $a c$ , а максимальный размер пустого подграфа — $k$ . Тогда есть такие множества вершин $B$ и $C$ мощности $k+1$ каждое, что $a b$ и $a c$ соответственно являются в них единственными ребрами. Выкинем из графа все вершины, кроме $B \cup C$ , от этого условие не изменится. После этого все вершины множества $B \cap C$ , кроме вершины $a$ , ни с какой вершиной не соединены. Поэтому их тоже можно выбросить, после чего как $k$ , так и количества элементов в $B$ и $C$ уменьшатся на одну и ту же величину. После этого у нас остался граф на $2 k+1$ вершине; если в нем нет нечетного цикла, то он двудольный, тогда в нем есть пустой подграф на $k+1$ вершине, что не так. Следовательно, нечетный цикл есть.

Задача 004

01.01.2025 от

Дано дерево $T$ с $n>2$ вершинами, в котором степени всех вершин меньше $n-1$ . Пусть $A$ — множество его висячих вершин. Добавим к дереву $T$ рёбра некоторого цикла, проходящего по всем вершинам множества $A$ ровно по одному разу и не проходящего через остальные вершины. Докажите, что вершины полученного графа можно правильно раскрасить в три цвета.

Подсказка

Рассмотрите в графе висячую вершину и вершины на расстоянии 2 от неё.

Решение

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

Задача 013

01.01.2025 от

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

Подсказка

Попробуйте доказать лемму. Если в связном ориентированном графе $k$ вершин и хотя бы $2 k-1$ ребро (причем некоторые пары вершин могут быть соединены ребрами в обоих направлениях), то одно из ребер можно удалить без потери связности.

Решение

Ответ. 197.
Решение: Построим ориентированный граф, вершины которого соответствуют городам, а ребра — дорогам (направление ребра будет соответствовать направлению дороги). Любые две вершины соединены не более, чем одним ориентированным ребром. Полученный граф будет связным (из любой вершины можно попасть в любую другую), но при удалении любого ребра связность теряется.

Построим пример такого графа со 197 ребрами. Он будет состоять из вершин $A, B, \mathrm{C}_{1}, \ldots, \mathrm{C}_{98}$ , и ребер $A \rightarrow C$ , а также $C \rightarrow B_{i}$ и $B_{i} \rightarrow A$ для всех $i$ . Нетрудно проверить, что этот граф подходит.

Докажем лемму: если в связном ориентированном графе $k$ вершин и хотя бы $2 k-1$ ребро (причем некоторые пары вершин могут быть соединены ребрами в обоих направлениях), то одно из ребер можно удалить без потери связности.

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

Перейдем к доказательству утверждения задачи. Из связности графа следует, что в нем есть (ориентированный) цикл $C_{1} \rightarrow C_{2} \rightarrow \ldots \rightarrow C_{m} \rightarrow C_{1}$ . Понятно, что $m \geq 3$ и нет никаких ребер между входящими в цикл вершинами, кроме ребер самого цикла (иначе такое ребро можно удалить без потери связности). Также отметим, что из любой не входящей в цикл вершины А существует не более одного ребра, выходящего к вершинам цикла (если таких ребер хотя бы два, то одно из них можно удалить без потери связности). Аналогично, существует не более одного ребра, выходящего из вершин цикла в А.

Заменим все вершины цикла на одну вершину $C$ и для любой другой вершины $A$ проведем ребро $A \rightarrow C$ , если существует одно из ребер $A \rightarrow C_{i}$ и ребро $C \rightarrow A$ , если существует одно из ребер $C_{i} \rightarrow \mathrm{~A}$ . Получится новый связный ориентированный графG’, в котором ровно на $m$ ребер меньше, чем в исходном графе и удаление любого ребра нарушает связность. (Однако, в этом графе возможно наличие двух ребер разного направления между двумя вершинами.) В графе G’ ровно $100-m+1$ вершина и, по доказанному выше утверждению, не более $2(100-m+1)-2=200-2 m$ ребер. Следовательно, в исходном графе было не более, чем $200-m \leq 200-3=197$ ребер.

Задача 018

01.01.2025 от

На танцах было $2 n$ мальчиков и $2 n$ девочек. Боря танцевал со всеми девочками, Аня танцевала со всеми мальчиками, и для любых двух девочек есть ровно n мальчиков, танцевавших ровно с одной из них. Докажите, что каждый мальчик, кроме Бори, танцевал ровно с $n$ девочками.

Подсказка

Рассмотрите вместе с Аней ещё одну (любую) девочку. Что следует их условия?

Решение

Возьмём Аню и любую другую девочку Д. По условию, ровно с одной девочкой из этих двух танцевало ровно $n$ мальчиков. Так как с Аней танцевали все мальчики, то эти $n$ мальчиков танцевали именно с ней, а остальные $n$ мальчиков танцевали и с ней, и с Д. Итак, с каждой девочкой, кроме Ани, танцевали ровно $n$ мальчиков. Возьмём любых двух таких девочек. Пусть с обеими танцевали $m$ мальчиков. Тогда ровно с одной танцевали $n=2(n-m)$ мальчиков, откуда $m=n / 2$ .

Забудем про Аню и Борю. Тогда каждая из девочек танцевала с $n-1$ мальчиком, а с каждыми двумя девочками танцевали $n / 2-1$ мальчиков. Занумеруем мальчиков и пусть $i$ -ый мальчик танцевал с $d_{i}$ девочками. Тогда троек, состоящих из мальчика и двух девочек, с которыми он танцевал, будет $d_{1}\left(d_{1}-1\right) / 2+\ldots+d_{2 k-1}\left(d_{2 k-1}-1\right) / 2$ . С другой стороны, число таких троек равно $n / 2-1$ , умноженному на количество пар девочек, то есть $(n / 2-1)(2 n-1)(n-1)$ .
Заметим, что

$d_{1}\left(d_{1}-1\right) / 2+\ldots+d_{2 k-1}\left(d_{2 k-1}-1\right) / 2=\left(d_{1}^{2}+\ldots+d_{2 n-1}^{2}\right) / 2-\left(d_{1}+\ldots+d_{2 n-1}\right) / 2 \text {. }$

Так как $d_{1}+\ldots+d_{2 k-1}=(n-1)(2 n-1)$ (считаем ту же сумму «со стороны девочек»), то получаем, что

$d_{1}^{2}+\ldots+d_{2 n-1}^{2}=2(n / 2-1)(2 n-1)(n-1)+(n-1)(2 n-1)=(n-1)^{2}(2 n-1) .$

С другой стороны, по неравенству между средним арифметическим и средним квадратическим

$d_{1}^{2}+\ldots+d_{2 n-1}^{2} \geq\left(d_{1}+\ldots+d_{2 n-1}\right)^{2} /(2 n-1)=(n-1)^{2}(2 n-1)$

причём равенство достигается только при $d_{1}=\ldots=d_{2 k-1}$ . Итак, все $d_{i}$ равны между собой, откуда $d_{i}=n-1$ , что и (вспомним про Аню!) требовалось доказать.

Задача 019

01.01.2025 от

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

Подсказка

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

Решение

Будем доказывать индукцией по числу $n$ вершин. База для $n=3$ и $n=4$ проверяется без труда. Пусть для всех графов с менее чем $n$ вершинами условие выполнено, а в графе $G$ с $n$ вершинами и исходящими степенями 3 не нашлось двух непересекающихся циклов.

Предположим, что в $G$ есть встречные ребра между вершинами $v$ и $w$ . Тогда в $G$ есть цикл $v w$ , и в $G-\{v, w\}$ есть цикл, так как в нем из каждой вершины выходит хотя бы одно ребро. Следовательно, в $G$ нет встречных ребер.

Предположим, что в $G$ есть ребро $u v$ такое, что ни из какой вершины $x \in V(G)$ не выходят ребра в обе вершины $u$ и $v$ . Тогда стянем ребро $u v$ : удалим в $G$ вершины $u$ и $v$ и добавим новую вершину $w$ , в которую входят ребра из тех вершин, из которых входили ребра в $u$ и $v$ , и выходят ребра в те вершины, в которые выходили ребра из $v$ . Обозначим полученный граф через $G^{\prime}$ . В $G^{\prime} n-1$ вершина и степень каждой вершины равна 3 , поэтому для него выполнено индукционное предположение. Но тогда и в $G$ есть два непересекающихся цикла, так как если цикл в $G^{\prime}$ проходил через $w$ , то в $G$ этот проход можно заменить на проход через $v$ или $u v$ .

Осталось разобрать случай, когда каждое ребро имеет «предка», то есть вершину, из которой выходят ребра в оба конца этого ребра. Пусть $v$ — вершина наименьшей входящей степени (обозначим эту степень $d^{-}(v)$ ). Очевидно, $d^{-}(v) \leq 3$ .

(1) $d^{-}(v)=0$ . Тогда ребро, исходящее из $v$ , не имеет предка.
(2) $d^{-}(v)=1$ . Тогда ребро, входящее в $v$ , не имеет предка.
(3) $d^{-}(v)=2$ . Пусть есть ребра $u v$ и $w v$ . Тогда $u$ должно быть предком для $w v$ , а $w$ — для $u v$ , но тогда есть ребра $v w$ и $w v$ , а этот случай мы уже разобрали.
(4) $d^{-}(v)=3$ . Тогда все вершины имеют входящую степень 3. Пусть в вершину $x$ входят ребра $u x, v x, w x$ . Предком каждого из этих ребер должна быть $u, v$ или $w$ . Тогда в индуцированном подграфе на вершинах $u, v, w$ в каждую вершину входит хотя бы одно ребро, а так как в $G$ нет встречных ребер, вершины $u, v, w$ образуют цикл длины 3. Заметим, что вершины, в которые ведут ребра из $x$ , также образуют цикл длины 3 (так как мы можем обратить все ребра и повторить те же рассуждения). $B G$ нет встречных ребер, поэтому мы нашли два непересекающихся цикла.

Задача 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 больше максимального числа на соответствующем пути в первом дереве).

Задача 025

01.01.2025 от

2016 мальчиков выбирают девочек. Каждый мальчик выбирает ровно двух девочек: одну блондинку и одну брюнетку. Оказалось, что для любого натурального числа $k, 1 \leq k \leq 80$ , найдется девочка (блондинка или брюнетка), которую выбрали ровно $k$ мальчиков. Докажите, что какие-то два мальчика выбрали одних и тех же девочек.

Подсказка

Зафиксируйте 80 вершин со степенями $1,2, \ldots, 80$ соответственно.

Решение

Рассмотрим двудольный (мульти)граф, где вершины — блондинки и брюнетки, а рёбра — выборы мальчиков. В нем 2016 рёбер. Надо доказать, что есть два ребра с общими концами.

Зафиксируем 80 вершин со степенями $1,2, \ldots, 80$ соответственно; назовём их выбранными. Пусть имеется $k$ рёбер, оба конца которых выбраны; также назовём их выбранными. Тогда рёбер, один конец которых выбран, будет $1+2+\ldots+80-2 k$ . С другой стороны, их не больше, чем 2016- $k$ , откуда $k \geq 1+2+\ldots+80-2016=1224$ .

Рассмотрим выбранные вершины со степенями $1,2, \ldots, 26$ . Из них исходит не более $1+2+\ldots+26=351$ выбранного ребра. Значит, остальные 54 вершины связывают не менее $1224-351=873$ рёбер. С другой стороны, пусть среди этих 54 вершин $x$ блондинок и $54-x$ брюнеток, и между любыми двумя вершинами — не более одного ребра. Тогда всего между этими вершинами не более $x(54-x) \leq(x+54-x)^{2} / 2^{2}=27^{2}=729$ рёбер. Противоречие.

Задача 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$ . Полученное противоречие показывает, что незнакомых в данной компании быть не может.