2001 IMO Shortlist Problems/C3
Contents
Problem
Define a 
-clique to be a set of 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 
and 
. If every other 3-clique contained either 
or 
, then removing and will leave no 3-clique remaining.
Otherwise, if there was a 3-clique that did not contain or , then it would have to contain 
and 
to satisfy the condition. Call this 3-clique 
. First notice that 
and 
are also 3-cliques now since and are now acquainted. We claim that removing and will now suffice; suppose there was another 3-clique not containing or . This 3-clique must contain , , and 
(to share with , , and ). However, this means 
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 : name the 3-cliques and 
. We now claim that every 3-clique in this case must contain .
Suppose there existed a 3-clique not containing . It must share one person with each of and ; without loss of generality, let this 3-clique contain and . But this means and are acquainted, and due to their mutual acquaintance with , is a 3-clique, which shares 2 people with , contradicting the premise of this case.
Thus, every 3-clique contains , and so removing will remove every 3-clique.
