Дано: группа из шести человек.
Найти: доказать, что среди них либо трое попарно знакомых, либо трое попарно незнакомых.
Решение:
Предположим, каждый человек либо знаком со всеми остальными, либо не знаком ни с кем, и докажем, что в этой группе обязательно найдутся трое, попарно знакомые, или трое, попарно незнакомые.
Выберем произвольного человека A из группы. Он может быть знаком с пятью другими людьми или не знаком ни с кем. Рассмотрим два случая:
1. Если A знаком со всеми пятью другими людьми, то эти пять человек образуют полный подграф размера 5, и в нем обязательно найдутся три взаимопонятые или три взаимно непонятные вершины (в соответствии с теоремой Рамсея).
2. Если A не знаком ни с одним из пяти человек, то между этими пятью людьми нет связей, и они образуют полный подграф размера 5 без ребер. Тогда при добавлении A будет образовываться полный подграф размера 6 без ребер, и также найдутся три взаимнопонятные или три взаимнонепонятные вершины.
Таким образом, среди любых шести человек есть либо трое попарно знакомых, либо трое попарно незнакомых.
Ответ:
Доказано, что среди любых шести человек найдутся либо трое попарно знакомых, либо трое попарно незнакомых.