Maths WorkshopMaths problems with full solutions
Exercise 1807Combinatorics › Pigeonhole principleOlympiadAdded 3 Nov 2026

Friends and enemies

#pigeonhole#Ramsey#relation

Statement

Among any 55 people, show that either 33 are mutual friends, or 33 are mutual strangers (each pair either friends or strangers).

Hint

Fix PP; among 44 others, at least 22 are in the same relation.

Show solutionHide solution

Solution

Pigeonhole at PP. PP has 44 relations: at least 22 friends (WLOG) A,BA,B.

Among A,BA,B. If A,BA,B are friends, then P,A,BP,A,B are 33 mutual friends. If A,BA,B are strangers, then... we only get 22 mutual strangers among A,BA,B, not 33.

Correction. This works for 66 people, not 55. For 55, the statement is false: color K5K_5 without a monochromatic triangle.

Conclusion. For 66 people, we get 33 mutual friends or 33 mutual strangers (Ramsey R(3,3)=6R(3,3)=6). For 55, it can fail.