Дано:
Пусть есть компания из 6 человек. Обозначим их как A1, A2, A3, A4, A5 и A6.
Найти:
Нужно доказать, что в этой компании найдутся либо трое попарно незнакомых друг с другом, либо трое попарно знакомых.
Решение:
Рассмотрим граф, где вершины графа будут представлять людей, а ребра будут обозначать знакомство между ними. Если два человека знакомы, то между ними проведем ребро, если нет - ребро не проводим.
В таком графе, по теореме Рэмси, для 6 вершин либо существует подмножество из 3-х вершин, между которыми есть ребра (т.е. три попарно знакомых человека), либо существует подмножество из 3-х вершин, не соединенных ребрами (т.е. три попарно незнакомых человека).
Для удобства рассмотрим одну из вершин, например A1. У него может быть знакомство с 5 другими людьми (A2, A3, A4, A5 и A6). Пусть у A1 есть k знакомых. В этом случае рассмотрим два сценария:
1. Если k >= 3, то среди этих 3-х знакомых обязательно найдется хотя бы один тройка, которые знакомы между собой (это следует из теоремы о графах).
2. Если k < 3, значит A1 незнаком с 2 или более людьми. В этом случае, оставшиеся 5 человек могут быть разбиты на группу из 2-х незнакомых и 3-х знакомых, чтобы удовлетворить условию.
Таким образом, независимо от того, сколько знакомых у A1, мы всегда можем найти либо трех знакомых, либо троих незнакомых между собой.
Ответ:
В любой компании из 6 человек найдутся либо трое попарно незнакомых друг с другом, либо трое попарно знакомых.