Exercise 2187Combinatorics › Pigeonhole principleOlympiadAdded 3 Nov 2026

Ramsey-type pigeonhole

#pigeonhole#Ramsey#coloring

Statement

In any party of $6$ people, show that there are either $3$ mutual friends or $3$ mutual strangers.

Hint

Fix a person $P$ . Consider the $5$ other people: at least $\lceil 5/2\rceil=3$ are friends or strangers.

Show solutionHide solution

Solution

Setup. By pigeonhole on the $5$ remaining people's relation to $P$ ( $2$ categories: friend or stranger): at least $3$ fall into the same category. WLOG, $P$ is friends with $A,B,C$ .

Among $A,B,C$ .
- If any two are friends, they and $P$ form $3$ mutual friends. Done.
- If none are friends with each other, then $A,B,C$ are $3$ mutual strangers. Done.

Conclusion. $6$ people guarantee $3$ mutual friends or $3$ mutual strangers (Ramsey $R(3,3)\le6$ ).

Ramsey-type pigeonhole

Statement

Solution

More problems in Pigeonhole principle