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 "2023 AIME II Problems/Problem 11"
m (→‎Solution)
Line 86: Line 86:
 
Case 4: <math>N \geq 3</math>.
 
Case 4: <math>N \geq 3</math>.
  
−
The number of subsets of <math>\left\{ 1, 2, 3, 4, 5 \right\}</math> that contain at least three elements is <math>\sum_{i=3}^5 \binom{5}{3} = 16</math>.
+
The number of subsets of <math>\left\{ 1, 2, 3, 4, 5 \right\}</math> that contain at least three elements is <math>\sum_{i=3}^5 \binom{5}{i} = 16</math>.
 
Because <math>\mathcal C</math> has 16 elements, we must select all such subsets into <math>\mathcal C</math>.
 
Because <math>\mathcal C</math> has 16 elements, we must select all such subsets into <math>\mathcal C</math>.
 
Therefore, the number of solutions in this case is 1.
 
Therefore, the number of solutions in this case is 1.

Revision as of 14:44, 5 August 2023

Problem

Find the number of collections of $16$ distinct subsets of $\{1,2,3,4,5\}$ with the property that for any two subsets $X$ and $Y$ in the collection, $X \cap Y \not= \emptyset.$

Solution

Denote by $\mathcal C$ a collection of 16 distinct subsets of $\left\{ 1, 2, 3, 4, 5 \right\}$. Denote $N = \min \left\{ |S|: S \in \mathcal C \right\}$.

Case 1: $N = 0$.

This entails $\emptyset \in \mathcal C$. Hence, for any other set $A \in \mathcal C$, we have $\emptyset \cap A = \emptyset$. This is infeasible.

Case 2: $N = 1$.

Let $\{a_1\} \in \mathcal C$. To get $\{a_1\} \cap A \neq \emptyset$ for all $A \in \mathcal C$. We must have $a_1 \in \mathcal A$.

The total number of subsets of $\left\{ 1, 2, 3, 4, 5 \right\}$ that contain $a_1$ is $2^4 = 16$. Because $\mathcal C$ contains 16 subsets. We must have $\mathcal C = \left\{ \{a_1\} \cup A : \forall \ A \subseteq \left\{ 1, 2, 3, 4, 5 \right\} \backslash \left\{a_1 \right\} \right\}$. Therefore, for any $X, Y \in \mathcal C$, we must have $X \cap Y \supseteq \{a_1\}$. So this is feasible.

Now, we count the number of $\mathcal C$ in this case. We only need to determine $a_1$. Therefore, the number of solutions is 5.

Case 3: $N = 2$.

Case 3.1: There is exactly one subset in $\mathcal C$ that contains 2 elements.

Denote this subset as $\left\{ a_1, a_2 \right\}$. We then put all subsets of $\left\{ 1, 2, 3, 4, 5 \right\}$ that contain at least three elements into $\mathcal C$, except $\left\{ a_3, a_4, a_5 \right\}$. This satisfies $X \cap Y \neq \emptyset$ for any $X, Y \in \mathcal C$.

Now, we count the number of $\mathcal C$ in this case. We only need to determine $\left\{ a_1, a_2 \right\}$. Therefore, the number of solutions is $\binom{5}{2} = 10$.

Case 3.2: There are exactly two subsets in $\mathcal C$ that contain 2 elements.

They must take the form $\left\{ a_1, a_2 \right\}$ and $\left\{ a_1, a_3 \right\}$.

We then put all subsets of $\left\{ 1, 2, 3, 4, 5 \right\}$ that contain at least three elements into $\mathcal C$, except $\left\{ a_3, a_4, a_5 \right\}$ and $\left\{ a_2, a_4, a_5 \right\}$. This satisfies $X \cap Y \neq \emptyset$ for any $X, Y \in \mathcal C$.

Now, we count the number of $\mathcal C$ in this case. We only need to determine $\left\{ a_1, a_2 \right\}$ and $\left\{ a_1, a_3 \right\}$. Therefore, the number of solutions is $5 \cdot \binom{4}{2} = 30$.

Case 3.3: There are exactly three subsets in $\mathcal C$ that contain 2 elements. They take the form $\left\{ a_1, a_2 \right\}$, $\left\{ a_1, a_3 \right\}$, $\left\{ a_1, a_4 \right\}$.

We then put all subsets of $\left\{ 1, 2, 3, 4, 5 \right\}$ that contain at least three elements into $\mathcal C$, except $\left\{ a_3, a_4, a_5 \right\}$, $\left\{ a_2, a_4, a_5 \right\}$, $\left\{ a_2, a_3, a_5 \right\}$. This satisfies $X \cap Y \neq \emptyset$ for any $X, Y \in \mathcal C$.

Now, we count the number of $\mathcal C$ in this case. We only need to determine $\left\{ a_1, a_2 \right\}$, $\left\{ a_1, a_3 \right\}$, $\left\{ a_1, a_4 \right\}$. Therefore, the number of solutions is $5 \cdot \binom{4}{3} = 20$.

Case 3.4: There are exactly three subsets in $\mathcal C$ that contain 2 elements. They take the form $\left\{ a_1, a_2 \right\}$, $\left\{ a_1, a_3 \right\}$, $\left\{ a_2, a_3 \right\}$.

We then put all subsets of $\left\{ 1, 2, 3, 4, 5 \right\}$ that contain at least three elements into $\mathcal C$, except $\left\{ a_3, a_4, a_5 \right\}$, $\left\{ a_2, a_4, a_5 \right\}$, $\left\{ a_1, a_4, a_5 \right\}$. This satisfies $X \cap Y \neq \emptyset$ for any $X, Y \in \mathcal C$.

Now, we count the number of $\mathcal C$ in this case. We only need to determine $\left\{ a_1, a_2 \right\}$, $\left\{ a_1, a_3 \right\}$, $\left\{ a_2, a_3 \right\}$. Therefore, the number of solutions is $\binom{5}{3} = 10$.

Case 3.5: There are exactly four subsets in $\mathcal C$ that contain 2 elements. They take the form $\left\{ a_1, a_2 \right\}$, $\left\{ a_1, a_3 \right\}$, $\left\{ a_1, a_4 \right\}$, $\left\{ a_1, a_5 \right\}$.

We then put all subsets of $\left\{ 1, 2, 3, 4, 5 \right\}$ that contain at least three elements into $\mathcal C$, except $\left\{ a_3, a_4, a_5 \right\}$, $\left\{ a_2, a_4, a_5 \right\}$, $\left\{ a_1, a_4, a_5 \right\}$, $\left\{ a_2, a_3, a_4 \right\}$. This satisfies $X \cap Y \neq \emptyset$ for any $X, Y \in \mathcal C$.

Now, we count the number of $\mathcal C$ in this case. We only need to determine $\left\{ a_1, a_2 \right\}$, $\left\{ a_1, a_3 \right\}$, $\left\{ a_1, a_4 \right\}$, $\left\{ a_1, a_5 \right\}$. Therefore, the number of solutions is 5.

Putting all subcases together, the number of solutions is this case is $10 + 30 + 20 + 10 + 5 = 75$.

Case 4: $N \geq 3$.

The number of subsets of $\left\{ 1, 2, 3, 4, 5 \right\}$ that contain at least three elements is $\sum_{i=3}^5 \binom{5}{i} = 16$. Because $\mathcal C$ has 16 elements, we must select all such subsets into $\mathcal C$. Therefore, the number of solutions in this case is 1.

Putting all cases together, the total number of $\mathcal C$ is $5 + 75 + 1 = \boxed{\textbf{(081) }}$.

Video Solution

https://youtu.be/FH2QUGVNchw

See also

2023 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 10 		Followed by
Problem 12
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2023_AIME_II_Problems/Problem_11&oldid=196435"