Шесть человек присутствуют на встрече. Докажи, что среди них найдутся трое, которые все знакомы друг с другом, или трое, которые все незнакомы друг с другом (теорема Рамсея $R(3,3) = 6$).
Правильный ответ
Возьмём одного человека $A$. Среди 5 остальных по принципу Дирихле хотя бы 3 человека знакомы с $A$ или хотя бы 3 незнакомы. Пусть B, C, D знакомы с $A$. Если хоть двое из B, C, D знакомы, вместе с $A$ образуют тройку знакомых. Иначе B, C, D — все незнакомы между собой.
💡 Авторизуйтесь, чтобы получить помощь AI-тьютора с подсказками и решениями!