AIME 2002 II · 第 9 题

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{aligned}\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{aligned}$$ 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{aligned}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{aligned}$$ Hence, as in Solution 1, $n = \frac{1}{2}\left(3^{10}-2\cdot2^{10}+1\right) = 28501 \equiv \boxed{501} \pmod{1000}$.