Номер 5.107, страница 192 - гдз по алгебре 9 класс учебник Шыныбеков, Шыныбеков

5.107. Покажите, что среди любых 9 людей найдутся 3 человека, знакомых друг с другом, или 4 человека, которые не знакомы друг с другом.

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

Раскрасим ребра графа в два цвета: ребро будет красным, если два человека знакомы друг с другом, и синим, если они не знакомы. Задача теперь формулируется так: доказать, что в любой такой раскраске полного графа $K_9$ найдется либо красный треугольник ($K_3$), соответствующий трем попарно знакомым людям, либо синий полный подграф на 4 вершинах ($K_4$), соответствующий четырем попарно незнакомым людям. Это утверждение эквивалентно тому, что число Рамсея $R(3, 4) \le 9$.

Мы докажем это утверждение методом от противного. Предположим, что существует такая раскраска ребер графа $K_9$, в которой нет ни красного $K_3$, ни синего $K_4$.

Шаг 1: Анализ произвольной вершины. Выберем произвольную вершину графа, назовем ее $v$. Эта вершина соединена с остальными 8 вершинами. Каждое из этих 8 ребер окрашено либо в красный, либо в синий цвет. Пусть $d_R(v)$ — это количество красных ребер, инцидентных вершине $v$ (число знакомых у человека $v$), а $d_B(v)$ — количество синих ребер, инцидентных вершине $v$ (число незнакомых у человека $v$). Очевидно, что для любой вершины $v$ выполняется равенство: $d_R(v) + d_B(v) = 8$.

Шаг 2: Вывод ограничений на степени вершин. Рассмотрим множество $N_R(v)$ вершин, соединенных с $v$ красными ребрами. Их количество равно $d_R(v)$. Если бы между любыми двумя вершинами из $N_R(v)$ было красное ребро, то эти две вершины вместе с $v$ образовывали бы красный треугольник. Поскольку мы предположили, что красных $K_3$ нет, все ребра внутри подграфа, порожденного вершинами из $N_R(v)$, должны быть синими. Это означает, что все люди из группы знакомых человека $v$ попарно не знакомы друг с другом. Так как мы предположили, что нет синего $K_4$ (четырех попарно незнакомых), то количество вершин в $N_R(v)$ не может быть 4 или больше. Следовательно, $d_R(v) < 4$, то есть $d_R(v) \le 3$.

Теперь рассмотрим множество $N_B(v)$ вершин, соединенных с $v$ синими ребрами. Их количество равно $d_B(v)$. В подграфе, порожденном этими вершинами, не может быть синего треугольника. Иначе, если бы в $N_B(v)$ нашлись три вершины, образующие синий $K_3$, то вместе с вершиной $v$ (которая соединена с ними синими ребрами) они бы образовали синий $K_4$. Это противоречит нашему предположению. Итак, в подграфе на $d_B(v)$ вершинах множества $N_B(v)$ нет синего $K_3$. Также, по основному предположению, в нем нет и красного $K_3$. Таким образом, в группе из $d_B(v)$ человек (незнакомых с $v$) нет ни тройки попарно знакомых, ни тройки попарно незнакомых. Известно, что число Рамсея $R(3, 3) = 6$. Это означает, что в любой группе из 6 человек обязательно найдется либо трое попарно знакомых, либо трое попарно незнакомых. Следовательно, количество вершин в $N_B(v)$ должно быть меньше 6. Таким образом, $d_B(v) < 6$, то есть $d_B(v) \le 5$.

Шаг 3: Получение противоречия. Поскольку наш выбор вершины $v$ был произвольным, выведенные ограничения должны выполняться для каждой вершины графа: $d_R(v) \le 3$ и $d_B(v) \le 5$. При этом для каждой вершины должно выполняться условие $d_R(v) + d_B(v) = 8$. Единственный способ удовлетворить всем этим условиям одновременно — это если для каждой вершины $v$ в точности $d_R(v) = 3$ и $d_B(v) = 5$.

Это означает, что если бы наше предположение о существовании контрпримера было верным, то красный подграф (граф знакомств) должен быть 3-регулярным графом. То есть, у каждого из 9 человек должно быть ровно 3 знакомых.

Рассмотрим сумму степеней всех вершин в красном графе. С одной стороны, она равна $9 \text{ вершин} \times 3 \text{ (степень каждой)} = 27$. С другой стороны, согласно лемме о рукопожатиях, сумма степеней всех вершин любого графа равна удвоенному числу его ребер: $\sum_{v \in V} d_R(v) = 2|E_R|$, где $|E_R|$ — число красных ребер. Таким образом, мы получаем $2|E_R| = 27$. Это уравнение не имеет решения в целых числах, так как слева стоит четное число, а справа — нечетное. Мы пришли к противоречию.

Шаг 4: Заключение. Наше исходное предположение о том, что можно найти такую группу из 9 человек, где нет ни троих попарно знакомых, ни четверых попарно незнакомых, привело к противоречию. Следовательно, это предположение неверно. Это доказывает, что среди любых 9 человек всегда найдутся либо 3 человека, знакомых друг с другом, либо 4 человека, которые не знакомы друг с другом.

Ответ: Утверждение доказано.