Разделы 
Дополнительно
Задача по математике - 2070
2019-01-23 
В лагерь приехало несколько пионеров, каждый из них имеет от 50 до 100 знакомых среди остальных. Докажите, что пионерам можно выдать пилотки, покрашенные в 1331 цвет так, чтобы у знакомых каждого пионера были пилотки хотя бы 20 различных цветов.
Решение:
В решении мы будем пользоваться следующей известной теоремой.
Теорема Холла. Пусть дан двудольный граф $G$ (т. е. его вершины разбиты на два подмножества $A$ и $B$ таких, что любое ребро соединяет вершины из разных подмножеств). Предположим, что для любого подмножества вершин $A_1 \subseteq A$ количество вершин в $A_1$ не больше, чем количество вершин, соединенных хотя бы с одной вершиной из $A_1$. Тогда в графе найдется паросочетание (т. е. набор ребер с различными концами), содержащее все вершины множества $A$.
Перейдем к решению задачи. Построим граф, вершины которого соответствуют пионерам, а ребра - знакомствам. Степени вершин этого графа не менее 50 и не более 100. Докажем вспомогательное утверждение.
Лемма 1. Пусть $k \leq n \leq m$ - натуральные числа. Тогда из графа, степени вершин которого не менее $n$ и не более $m$, можно удалить несколько ребер так, чтобы степени всех вершин стали не менее $n - к$ и не более $m - к$.
Доказательство. Понятно, что достаточно доказать утверждение леммы для $k = 1$. До тех пор, пока есть ребра, соединяющие пары вершин степени $m$, будем удалять такие ребра. Пусть таких ребер больше нет, обозначим через $A$ множество всех вершин степени $m$ в полученном после удаления ребер графе $G$, а через $B$ множество всех остальных вершин.
Рассмотрим двудольный граф $G^{\prime}$ на тех же вершинах, в котором останутся лишь ребра между $A$ и $B$. Проверим выполнение условия теоремы Холла для этого графа. Рассмотрим множество $A_1 \subset A,$ пусть $B_1$ - множество вершин, смежных с вершинами из $A_1$. Из $A_1$ выходит не менее $m|A_1|$ ребер к вершинам множества $B_1$, а в каждую вершину из $B_1$ входит менее $m$ ребер, следовательно, $|B_1| \geq |A_1|$ (через $|X|$ мы, как обычно, обозначаем количество элементов в множестве $X$). Таким образом, по теореме Холла существует паросочетание, содержащее все вершины из $A$. Удалив из графа $G$ ребра этого паросочетания, мы получим граф $G_1$, степени вершин которого не менее $n - 1$ и не более $m - 1$. Лемма 1 доказана.
Перейдем к решению задачи. Применив лемму 1 для исходного графа и $к = 30$, мы получим граф $H$, степени вершин которого не менее 20 и не более 70. Сделаем его ребра красными. Для каждой вершины этого графа отметим 20 вершин среди ее соседей и попарно соединим эти 20 вершин зелеными ребрами. Так как из каждой вершины выходит не более 70 красных ребер, то из нее выходит не более, чем $70 \cdot 19 = 1330$ зеленых ребер.
Рассмотрим граф $H^{\prime}$ с зелеными ребрами на вершинах графа $H$. Несложно по очереди покрасить эти вершины в 1331 цвет так, чтобы соседние вершины были разноцветными: рассматривая каждую следующую вершину, покрасим ее в любой незадействованный среди ее соседей цвет.
Теперь опять рассмотрим граф $H$ с красными ребрами. Среди соседей каждой его вершины есть 20 выделенных и все они покрашены в разные цвета.
Замечание. Можно покрасить пилотки пионеров всего в 761 цвет. Для доказательства этого факта надо заменим лемму 1 на более сильную лемму 2, доказательство которой предоставляется читателю.
Лемма 2. Пусть $k < n$ - натуральные числа. В графе $G$ степени всех вершин не менее $n$ и не более $2n$. Тогда можно удалить несколько ребер так, чтобы степени всех вершин стали не менее $k$ и не более $2k$.
В лагерь приехало несколько пионеров, каждый из них имеет от 50 до 100 знакомых среди остальных. Докажите, что пионерам можно выдать пилотки, покрашенные в 1331 цвет так, чтобы у знакомых каждого пионера были пилотки хотя бы 20 различных цветов.
Решение:
В решении мы будем пользоваться следующей известной теоремой.
Теорема Холла. Пусть дан двудольный граф $G$ (т. е. его вершины разбиты на два подмножества $A$ и $B$ таких, что любое ребро соединяет вершины из разных подмножеств). Предположим, что для любого подмножества вершин $A_1 \subseteq A$ количество вершин в $A_1$ не больше, чем количество вершин, соединенных хотя бы с одной вершиной из $A_1$. Тогда в графе найдется паросочетание (т. е. набор ребер с различными концами), содержащее все вершины множества $A$.
Перейдем к решению задачи. Построим граф, вершины которого соответствуют пионерам, а ребра - знакомствам. Степени вершин этого графа не менее 50 и не более 100. Докажем вспомогательное утверждение.
Лемма 1. Пусть $k \leq n \leq m$ - натуральные числа. Тогда из графа, степени вершин которого не менее $n$ и не более $m$, можно удалить несколько ребер так, чтобы степени всех вершин стали не менее $n - к$ и не более $m - к$.
Доказательство. Понятно, что достаточно доказать утверждение леммы для $k = 1$. До тех пор, пока есть ребра, соединяющие пары вершин степени $m$, будем удалять такие ребра. Пусть таких ребер больше нет, обозначим через $A$ множество всех вершин степени $m$ в полученном после удаления ребер графе $G$, а через $B$ множество всех остальных вершин.
Рассмотрим двудольный граф $G^{\prime}$ на тех же вершинах, в котором останутся лишь ребра между $A$ и $B$. Проверим выполнение условия теоремы Холла для этого графа. Рассмотрим множество $A_1 \subset A,$ пусть $B_1$ - множество вершин, смежных с вершинами из $A_1$. Из $A_1$ выходит не менее $m|A_1|$ ребер к вершинам множества $B_1$, а в каждую вершину из $B_1$ входит менее $m$ ребер, следовательно, $|B_1| \geq |A_1|$ (через $|X|$ мы, как обычно, обозначаем количество элементов в множестве $X$). Таким образом, по теореме Холла существует паросочетание, содержащее все вершины из $A$. Удалив из графа $G$ ребра этого паросочетания, мы получим граф $G_1$, степени вершин которого не менее $n - 1$ и не более $m - 1$. Лемма 1 доказана.
Перейдем к решению задачи. Применив лемму 1 для исходного графа и $к = 30$, мы получим граф $H$, степени вершин которого не менее 20 и не более 70. Сделаем его ребра красными. Для каждой вершины этого графа отметим 20 вершин среди ее соседей и попарно соединим эти 20 вершин зелеными ребрами. Так как из каждой вершины выходит не более 70 красных ребер, то из нее выходит не более, чем $70 \cdot 19 = 1330$ зеленых ребер.
Рассмотрим граф $H^{\prime}$ с зелеными ребрами на вершинах графа $H$. Несложно по очереди покрасить эти вершины в 1331 цвет так, чтобы соседние вершины были разноцветными: рассматривая каждую следующую вершину, покрасим ее в любой незадействованный среди ее соседей цвет.
Теперь опять рассмотрим граф $H$ с красными ребрами. Среди соседей каждой его вершины есть 20 выделенных и все они покрашены в разные цвета.
Замечание. Можно покрасить пилотки пионеров всего в 761 цвет. Для доказательства этого факта надо заменим лемму 1 на более сильную лемму 2, доказательство которой предоставляется читателю.
Лемма 2. Пусть $k < n$ - натуральные числа. В графе $G$ степени всех вершин не менее $n$ и не более $2n$. Тогда можно удалить несколько ребер так, чтобы степени всех вершин стали не менее $k$ и не более $2k$.
