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 "2002 AIME II Problems/Problem 9"
(Improved explanations, grammar, formatting, and LaTeX)
 
(6 intermediate revisions by 5 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
Let <math>\mathcal{S}</math> be the set <math>\lbrace1,2,3,\ldots,10\rbrace</math> Let <math>n</math> be the number of sets of two non-empty disjoint subsets of <math>\mathcal{S}</math>. (Disjoint sets are defined as sets that have no common elements.) Find the remainder obtained when <math>n</math> is divided by <math>1000</math>.
+
Let <math>\mathcal{S}</math> be the [[set]] <math>\lbrace1,2,3,\ldots,10\rbrace</math>. Let <math>n</math> be the number of sets of two non-empty disjoint subsets of <math>\mathcal{S}</math>. (Disjoint sets are defined as sets that have no common elements.) Find the remainder obtained when <math>n</math> is divided by <math>1000</math>.
  
−
== Solution ==
+
== Solution 1 (combinatorial) ==
−
For simplicity, let's call the sets <math>\mathcal{A}</math> and <math>\mathcal{B}</math>. Now if we choose <math>x</math> members from <math>\mathcal{S}</math> to be in <math>\mathcal{A}</math>, then we have <math>10-x</math> elements to choose for <math>\mathcal{B}</math>. Thus
+
Let the two disjoint subsets be <math>A</math> and <math>B</math>, and define <math>C = \mathcal{S}\setminus\left(A \cup B\right)</math> (so <math>C</math> is disjoint from both <math>A</math> and <math>B</math>, and every element of <math>\mathcal{S}</math>, if not contained in <math>A</math> or <math>B</math>, is necessarily contained in <math>C</math>). This means every element <math>s \in \mathcal{S}</math> satisfies exactly one of <math>s \in A</math>, <math>s \in B</math>, or <math>s \in C</math>, i.e. for each of the <math>10</math> elements, we have to independently choose <math>1</math> of these <math>3</math> subsets into which to place it. Hence there are a total of <math>3^{10}</math> ways to partition <math>\mathcal{S}</math> into disjoint subsets <math>A</math>, <math>B</math>, and <math>C</math>.  
  
−
<math>n=\sum_{x=1}^{9} (\binom{10}{x}\cdot(\sum_{n=1}^{10-x}\binom{10-x}{n}))=\sum_{x=1}^{9} (\binom{10}{x}\cdot(2^{10-x}-1))=\binom{10}{1}\cdot511+\binom{10}{2}\cdot255+\binom{10}{3}\cdot127+\binom{10}{4}\cdot63+\binom{10}{5}\cdot31+\binom{10}{6}\cdot15+\binom{10}{7}\cdot7+\binom{10}{8}\cdot3+\binom{10}{9}\cdot1=\binom{10}{1}\cdot512+\binom{10}{2}\cdot258+\binom{10}{3}\cdot134+\binom{10}{4}\cdot78+\binom{10}{5}\cdot31</math>.
+
However, we must exclude those partitions in which <math>A</math> or <math>B</math> (or both) is empty. If <math>A = \emptyset</math>, and thus <math>\mathcal{S} = B \cup C</math>, then we have to place each of the <math>10</math> elements of <math>\mathcal{S}</math> into either <math>B</math> or <math>C</math>, giving <math>2^{10}</math> such partitions (similarly to above). By symmetry, the case where <math>B = \emptyset</math> and <math>\mathcal{S} = A \cup C</math> also gives <math>2^{10}</math> partitions, so we need to subtract <math>2^{10}</math> twice from <math>3^{10}</math>. But then the partition <math>A = B = \emptyset, \mathcal{S} = C</math>, which falls within ''both'' of the above <math>2</math> cases, would be double-counted in the subtraction, so we must add it back.  
  
−
We want the remainder when <math>n</math> is divided by 1000, so we find the last three digits of each.
+
Accordingly, there are <math>\left(3^{10}-2\cdot2^{10}+1\right)</math> possible ordered pairs <math>(A,B)</math> (or equivalently, partitions <math>A,B,C</math>). Each pair has <math>2</math> possible orders (as <math>A</math> and <math>B</math>, being disjoint, obviously cannot be the same), so the above expression counts each ''unordered'' set <math>\left\{A,B\right\}</math> exactly twice. Thus, finally, we deduce that <math>n = \frac{1}{2}\left(3^{10}-2\cdot2^{10}+1\right) = 28501 \equiv \boxed{501} \pmod{1000}</math>.
  
−
==Solution 2==
+
== Solution 2 (computational/'bash') ==
−
Let the two disjoint subsets be <math>A</math> and <math>B</math>, and let <math>C = S-(A+B)</math>.
+
As in Solution 1, let the two disjoint subsets be <math>A</math> and <math>B</math>. We observe that if <math>A</math> has <math>p</math> elements, which can be chosen in <math>\binom{10}{p}</math> ways, then there are <math>(10-p)</math> remaining elements of <math>\mathcal{S}</math> from which to choose the elements of <math>B</math>.
−
For each <math>i \in S</math>, either <math>i \in A</math>, <math>i \in B</math>, or <math>i \in C</math>. So there are <math>3^{10}</math> ways to organize the elements of <math>S</math> into disjoint <math>A</math>, <math>B</math>, and <math>C</math>.  
 
  
−
However, there are <math>2^{10}</math> ways to organize the elements of <math>S</math> such that <math>A = \emptyset</math> and <math>S = B+C</math>, and there are <math>2^{10}</math> ways to organize the elements of <math>S</math> such that <math>B = \emptyset</math> and <math>S = A+C</math>.  
+
Therefore, letting <math>B</math> have <math>q</math> elements, we must have <math>1 \leq q \leq 10-p</math>, and similarly to above, these <math>q</math> elements can be chosen in <math>\binom{10-p}{q}</math> ways. Moreover, since <math>A</math> and <math>B</math> must both be non-empty, we require <math>p \geq 1</math> and <math>10-p \geq 1</math>, i.e. <math>1 \leq p \leq 9</math>. It follows that for each fixed value of <math>p</math>, the number of possible ordered pairs <math>(A,B)</math> is <cmath>\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*}</cmath> and summing this expression over <math>1 \leq p \leq 9</math> will therefore give the total number of such ordered pairs.
−
But, the combination such that <math>A = B = \emptyset</math> and <math>S = C</math> is counted twice.  
 
  
−
Thus, there are <math>3^{10}-2\cdot2^{10}+1</math> ordered pairs of sets <math>(A,B)</math>. But since the question asks for the number of unordered sets <math>\{ A,B \}</math>, <math>n = \frac{1}{2}(3^{10}-2\cdot2^{10}+1) = 28501 \equiv \boxed{501} \pmod{1000}</math>.
+
Just like in Solution 1, counting ordered pairs <math>(A,B)</math> is equivalent to counting each unordered set <math>\left\{A,B\right\}</math> exactly twice, so we deduce <cmath>\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*}</cmath> Hence, as in Solution 1, <math>n = \frac{1}{2}\left(3^{10}-2\cdot2^{10}+1\right) = 28501 \equiv \boxed{501} \pmod{1000}</math>.
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=2002|n=II|num-b=8|num-a=10}}
 
{{AIME box|year=2002|n=II|num-b=8|num-a=10}}
 +
 +
[[Category:Intermediate Combinatorics Problems]]
 +
{{MAA Notice}}

Latest revision as of 02:53, 17 June 2025

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"