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

Упражнения. Параграф 36. Вычитание рациональных чисел. Глава 4. Рациональные числа и действия над ними - номер 1032, страница 220.

Условие.

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

Решение.

Решение 2.

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

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

Выберем произвольную вершину графа, назовём её А. Эта вершина соединена рёбрами с остальными пятью вершинами. Согласно принципу Дирихле, из пяти рёбер, выходящих из вершины А, как минимум три должны быть одного цвета. Это так, потому что если бы рёбер каждого цвета было меньше трёх (т.е. максимум по два), то их общее число было бы не более $2+2=4$, а у нас их 5.

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

Здесь возможны два случая:

1. Хотя бы одно из рёбер, соединяющих вершины Б, В и Г, красное. Например, ребро (Б, В) — красное. В этом случае мы получаем красный треугольник АБВ, так как рёбра (А, Б), (А, В) и (Б, В) все красные. Это означает, что люди А, Б и В попарно знакомы.

2. Ни одно из рёбер, соединяющих вершины Б, В и Г, не является красным. Это означает, что все три ребра — (Б, В), (В, Г) и (Г, Б) — синие. В этом случае мы получаем синий треугольник БВГ. Это означает, что люди Б, В и Г попарно не знакомы.

В обоих случаях мы нашли группу из трёх человек, которые либо все попарно знакомы (красный треугольник), либо все попарно не знакомы (синий треугольник). Рассуждение будет абсолютно аналогичным, если бы мы изначально предположили, что из вершины А выходят как минимум три синих ребра — мы бы либо нашли синий треугольник с вершиной А, либо красный треугольник, образованный тремя другими вершинами.

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

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