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

2002 AIME II Problems/Problem 9

Problem

Let $\mathcal{S}$ be the set $\lbrace1,2,3,\ldots,10\rbrace$. Let $n$ be the number of sets of two non-empty disjoint subsets of $\mathcal{S}$. (Disjoint sets are defined as sets that have no common elements.) Find the remainder obtained when $n$ is divided by $1000$.

Solution 1 (combinatorial)

Let the two disjoint subsets be $A$ and $B$, and define $C = \mathcal{S}\setminus\left(A \cup B\right)$ (so $C$ is disjoint from both $A$ and $B$, and every element of $\mathcal{S}$, if not contained in $A$ or $B$, is necessarily contained in $C$). This means every element $s \in \mathcal{S}$ satisfies exactly one of $s \in A$, $s \in B$, or $s \in C$, i.e. for each of the $10$ elements, we have to independently choose $1$ of these $3$ subsets into which to place it. Hence there are a total of $3^{10}$ ways to partition $\mathcal{S}$ into disjoint subsets $A$, $B$, and $C$.

However, we must exclude those partitions in which $A$ or $B$ (or both) is empty. If $A = \emptyset$, and thus $\mathcal{S} = B \cup C$, then we have to place each of the $10$ elements of $\mathcal{S}$ into either $B$ or $C$, giving $2^{10}$ such partitions (similarly to above). By symmetry, the case where $B = \emptyset$ and $\mathcal{S} = A \cup C$ also gives $2^{10}$ partitions, so we need to subtract $2^{10}$ twice from $3^{10}$. But then the partition $A = B = \emptyset, \mathcal{S} = C$, which falls within both of the above $2$ cases, would be double-counted in the subtraction, so we must add it back.

Accordingly, there are $\left(3^{10}-2\cdot2^{10}+1\right)$ possible ordered pairs $(A,B)$ (or equivalently, partitions $A,B,C$). Each pair has $2$ possible orders (as $A$ and $B$, being disjoint, obviously cannot be the same), so the above expression counts each unordered set $\left\{A,B\right\}$ exactly twice. Thus, finally, we deduce that $n = \frac{1}{2}\left(3^{10}-2\cdot2^{10}+1\right) = 28501 \equiv \boxed{501} \pmod{1000}$.

Solution 2 (computational/'bash')

As in Solution 1, let the two disjoint subsets be $A$ and $B$. We observe that if $A$ has $p$ elements, which can be chosen in $\binom{10}{p}$ ways, then there are $(10-p)$ remaining elements of $\mathcal{S}$ from which to choose the elements of $B$.

Therefore, letting $B$ have $q$ elements, we must have $1 \leq q \leq 10-p$, and similarly to above, these $q$ elements can be chosen in $\binom{10-p}{q}$ ways. Moreover, since $A$ and $B$ must both be non-empty, we require $p \geq 1$ and $10-p \geq 1$, i.e. $1 \leq p \leq 9$. It follows that for each fixed value of $p$, the number of possible ordered pairs $(A,B)$ is \begin{align*}\binom{10}{p}\sum_{q=1}^{10-p}\binom{10-p}{q} &= \binom{10}{p}\sum_{q=1}^{10-p}\binom{10-p}{q}1^q 1^{(10-p)-q} \\ &= \binom{10}{p}\left(\sum_{q=0}^{10-p}\binom{10-p}{q}1^q 1^{(10-p)-q} - \binom{10-p}{0}\cdot 1^0 \cdot 1^{(10-p)-0}\right) \\ &= \binom{10}{p}\left(\left(1+1\right)^{10-p} - 1 \cdot 1 \cdot 1\right) \qquad \text{(by the binomial theorem)} \\ &= \binom{10}{p}\left(2^{10-p}-1\right),\end{align*} and summing this expression over $1 \leq p \leq 9$ will therefore give the total number of such ordered pairs.

Just like in Solution 1, counting ordered pairs $(A,B)$ is equivalent to counting each unordered set $\left\{A,B\right\}$ exactly twice, so we deduce \begin{align*}2n &= \sum_{p=1}^{9}\binom{10}{p}\left(2^{10-p}-1\right) \\ &= \sum_{p=1}^{9}\binom{10}{p}1^p 2^{10-p} - \sum_{p=1}^{9}\binom{10}{p}1^p 1^{10-p} \\ &= \left(\sum_{p=0}^{10}\binom{10}{p}1^p 2^{10-p} - \binom{10}{0} \cdot 1^0 \cdot 2^{10-0} - \binom{10}{10} \cdot 1^{10} \cdot 2^{10-10}\right) \\ &\phantom{=} -\left(\sum_{p=0}^{10}\binom{10}{p}1^p 1^{10-p} - \binom{10}{0} \cdot 1^0 \cdot 1^{10-0} - \binom{10}{10} \cdot 1^{10} \cdot 1^{10-10}\right) \\ &= \left(\left(1+2\right)^{10} - 1 \cdot 1 \cdot 2^{10} - 1 \cdot 1 \cdot 1\right) - \left(\left(1+1\right)^{10} - 1 \cdot 1 \cdot 1 - 1 \cdot 1 \cdot 1\right) \\ &\phantom{=} \text{(again by the binomial theorem)} \\ &= 3^{10}-2^{10}-1-2^{10}+1+1 \\ &= 3^{10} - 2 \cdot 2^{10} + 1.\end{align*} Hence, as in Solution 1, $n = \frac{1}{2}\left(3^{10}-2\cdot2^{10}+1\right) = 28501 \equiv \boxed{501} \pmod{1000}$.

See also

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

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2002_AIME_II_Problems/Problem_9&oldid=251276"