Exercise 1807Combinatorics › Pigeonhole principleOlympiadAdded 3 Nov 2026
Friends and enemies
#pigeonhole#Ramsey#relation
Statement
Among any people, show that either are mutual friends, or are mutual strangers (each pair either friends or strangers).
Hint
Fix ; among others, at least are in the same relation.
Show solutionHide solution
Solution
Pigeonhole at . has relations: at least friends (WLOG) .
Among . If are friends, then are mutual friends. If are strangers, then... we only get mutual strangers among , not .
Correction. This works for people, not . For , the statement is false: color without a monochromatic triangle.
Conclusion. For people, we get mutual friends or mutual strangers (Ramsey ). For , it can fail.