Номер 1140, страница 235 - гдз по математике 6 класс учебник Мерзляк, Полонский

Упражнения. Параграф 32. Вычитание рациональных чисел. Глава 4. Рациональные числа - номер 1140, страница 235.

Условие.

1140. Докажите, что в любой компании из шести человек найдётся трое попарно знакомых или трое попарно незнакомых.

Решение.

Решение 2.

Для доказательства этого утверждения воспользуемся методом из теории графов. Представим шестерых человек как шесть вершин полного графа $K_6$. В полном графе каждая пара вершин соединена ребром, которое символизирует отношение между двумя людьми. Всего в таком графе $C_6^2 = \frac{6 \cdot 5}{2} = 15$ рёбер.

Раскрасим рёбра этого графа в два цвета. Если два человека знакомы, соединяющее их ребро будет красным. Если они не знакомы, ребро будет синим. Поскольку любая пара людей либо знакома, либо не знакома, каждое ребро графа $K_6$ будет окрашено в один из двух цветов.

Задача в терминах теории графов формулируется так: доказать, что при любой двуцветной раскраске рёбер полного графа $K_6$ обязательно найдётся одноцветный (монохроматический) треугольник. "Красный" треугольник будет означать наличие трёх попарно знакомых людей, а "синий" треугольник — трёх попарно незнакомых.

Доказательство

Выберем произвольную вершину графа, назовём её $A$. Из этой вершины выходит 5 рёбер, соединяющих её с остальными пятью вершинами. Эти 5 рёбер окрашены либо в красный, либо в синий цвет.

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

Теперь рассмотрим отношения между людьми $B$, $C$ и $D$. Они образуют треугольник с рёбрами $(B, C)$, $(C, D)$ и $(D, B)$. Возможны два случая для цветов этих рёбер:

Случай 1. Среди рёбер $(B, C)$, $(C, D)$ и $(D, B)$ есть хотя бы одно красное ребро.
Пусть, например, ребро $(B, C)$ красное. Тогда, поскольку рёбра $(A, B)$ и $(A, C)$ тоже красные (по нашему предположению), вершины $A, B, C$ образуют красный треугольник. Это соответствует группе из трёх попарно знакомых людей. В этом случае утверждение доказано.

Случай 2. Среди рёбер $(B, C)$, $(C, D)$ и $(D, B)$ нет ни одного красного ребра.
Это означает, что все три ребра — $(B, C)$, $(C, D)$ и $(D, B)$ — синие. В этом случае вершины $B, C, D$ образуют синий треугольник. Это соответствует группе из трёх попарно незнакомых людей. Утверждение доказано и в этом случае.

Итак, в любой ситуации мы неизбежно находим либо красный, либо синий треугольник. Это доказывает, что в любой компании из шести человек всегда найдётся либо трое попарно знакомых, либо трое попарно незнакомых. Рассуждения были бы аналогичными, если бы мы изначально предположили, что из вершины $A$ выходит не менее трёх синих рёбер.

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