Difference between revisions of "2001 IMO Shortlist Problems/C3"
m (New page: == Problem == Define a <math>k</math>-<i>clique</i> to be a set of <math>k</math> people such that every pair of them are acquainted with each other. At a certain party, every pair of 3-cl...) |
|||
Line 3: | Line 3: | ||
== Solution == | == 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: | ||
+ | |||
+ | <b>Case 1: There exist a pair of 3-cliques that share 2 people.</b> | ||
+ | |||
+ | Let these 3-cliques be <math>\{A,C,D\}</math> and <math>\{B,C,D\}</math>. If every other 3-clique contained either <math>C</math> or <math>D</math>, then removing <math>C</math> and <math>D</math> will leave no 3-clique remaining. | ||
+ | |||
+ | Otherwise, if there was a 3-clique that did not contain <math>C</math> or <math>D</math>, then it would have to contain <math>A</math> and <math>B</math> to satisfy the condition. Call this 3-clique <math>\{A,B,E\}</math>. First notice that <math>\{A,B,C\}</math> and <math>\{A,B,D\}</math> are also 3-cliques now since <math>A</math> and <math>B</math> are now acquainted. We claim that removing <math>A</math> and <math>B</math> will now suffice; suppose there was another 3-clique not containing <math>A</math> or <math>B</math>. This 3-clique must contain <math>C</math>, <math>D</math>, and <math>E</math> (to share with <math>\{A,B,C\}</math>, <math>\{A,B,D\}</math>, and <math>\{A,B,E\}</math>). However, this means <math>\{A,B,C,D,E\}</math> is a 5-clique; contradiction. | ||
+ | |||
+ | <b>Case 2: Every pair of 3-cliques has at most one person in common.</b> | ||
+ | |||
+ | There exist two 3-cliques that share a person whom we will call <math>A</math>: name the 3-cliques <math>\{A,B,C\}</math> and <math>\{A,D,E\}</math>. We now claim that every 3-clique in this case must contain <math>A</math>. | ||
+ | |||
+ | Suppose there existed a 3-clique not containing <math>A</math>. It must share one person with each of <math>\{A,B,C\}</math> and <math>\{A,D,E\}</math>; without loss of generality, let this 3-clique contain <math>B</math> and <math>D</math>. But this means <math>B</math> and <math>D</math> are acquainted, and due to their mutual acquaintance with <math>A</math>, <math>\{A,B,D\}</math> is a 3-clique, which shares 2 people with <math>\{A,B,C\}</math>, contradicting the premise of this case. | ||
+ | |||
+ | Thus, every 3-clique contains <math>A</math>, and so removing <math>A</math> will remove every 3-clique. | ||
+ | |||
+ | <math>\blacksquare</math> | ||
== Resources == | == Resources == |
Latest revision as of 14:01, 23 November 2017
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.