2001 IMO Shortlist Problems/C3
Contents
[hide]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.