Every pair either know each other or do not. How many people make a triple of one type unavoidable?
The Unavoidable Trio
Riddle statement
At a gathering, every pair of people either know each other or are strangers to each other.
What is the smallest number of people that guarantees, whatever the relationships may be, either three mutual acquaintances or three mutual strangers?
Show solution
Solution
Answer: the smallest number is 6.
First, we show that six people are enough.
Choose any person, \(X\). Each of the other five people has one of two possible relationships with \(X\): they either know each other or they do not.
By the pigeonhole principle, at least three of those five relationships have the same type. Call three such people \(A\), \(B\), and \(C\).
If \(X\) knows all three, there are only two possibilities:
- some pair among \(A\), \(B\), and \(C\) know each other; that pair together with \(X\) forms three mutual acquaintances;
- no pair know each other; then \(A\), \(B\), and \(C\) are three mutual strangers.
If \(X\) knows none of the three, the argument is symmetric: either some pair forms three mutual strangers together with \(X\), or all three know one another.
Thus, among six people one of the two kinds of triple is unavoidable.
We must now show that five people are not enough.
Place five people at the vertices of a pentagon and let each person know only their two neighbors. The acquaintance relationships form a five-cycle, which contains no triangle.
The stranger relationships are the five diagonals of the pentagon. These also form a five-cycle and contain no triangle.
Therefore, five people can avoid both kinds of triple, whereas six cannot:
Key idea: six force a triple through the pigeonhole principle; five still escape through the pentagon construction.