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

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}}
+
=== 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 15:01, 23 November 2017

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"