Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2001 IMO Shortlist Problems/C3

Problem

Define a $k$-clique to be a set of $k$ people such that every pair of them are acquainted with each other. At a certain party, every pair of 3-cliques has at least one person in common, and there are no 5-cliques. Prove that there are two or fewer people at the party whose departure leaves no 3-clique remaining.

Solution

Solution 1

If there exists only one 3-clique, remove anyone in that clique. (If there are no 3-cliques, we are done!) Otherwise, consider the following cases:

Case 1: There exist a pair of 3-cliques that share 2 people.

Let these 3-cliques be $\{A,C,D\}$ and $\{B,C,D\}$. If every other 3-clique contained either $C$ or $D$, then removing $C$ and $D$ will leave no 3-clique remaining.

Otherwise, if there was a 3-clique that did not contain $C$ or $D$, then it would have to contain $A$ and $B$ to satisfy the condition. Call this 3-clique $\{A,B,E\}$. First notice that $\{A,B,C\}$ and $\{A,B,D\}$ are also 3-cliques now since $A$ and $B$ are now acquainted. We claim that removing $A$ and $B$ will now suffice; suppose there was another 3-clique not containing $A$ or $B$. This 3-clique must contain $C$, $D$, and $E$ (to share with $\{A,B,C\}$, $\{A,B,D\}$, and $\{A,B,E\}$). However, this means $\{A,B,C,D,E\}$ is a 5-clique; contradiction.

Case 2: Every pair of 3-cliques has at most one person in common.

There exist two 3-cliques that share a person whom we will call $A$: name the 3-cliques $\{A,B,C\}$ and $\{A,D,E\}$. We now claim that every 3-clique in this case must contain $A$.

Suppose there existed a 3-clique not containing $A$. It must share one person with each of $\{A,B,C\}$ and $\{A,D,E\}$; without loss of generality, let this 3-clique contain $B$ and $D$. But this means $B$ and $D$ are acquainted, and due to their mutual acquaintance with $A$, $\{A,B,D\}$ is a 3-clique, which shares 2 people with $\{A,B,C\}$, contradicting the premise of this case.

Thus, every 3-clique contains $A$, and so removing $A$ will remove every 3-clique.

$\blacksquare$

Resources

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2001_IMO_Shortlist_Problems/C3&oldid=88607"