Question

设 $\mathcal{S}$ 为集合 $\{1, 2, 3, \ldots, 10\}$ 。令 $n$ 为从 $\mathcal{S}$ 中选出两个非空且不相交的子集所组成的集合个数。（不相交集合指没有共同元素的集合。）求 $n$ 除以 $1000$ 所得的余数。

Let $\mathcal{S}$ be the set $\{1, 2, 3, \ldots, 10\}.$ 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.$

答案

答案：501

知识点：子集乘法原理容斥原理

难度评级：2500

解答：

先数不相交子集的有序对 $(A, B)$ 。对于这 $10$ 个元素中的每一个，可以选择放入 $A$ 、放入 $B$ ，或两者都不放，因此共有 $3^{10}$ 个有序对。其中 $2^{10}$ 个有 $A$ 为空， $2^{10}$ 个有 $B$ 为空，而 $(\varnothing, \varnothing)$ 被重复减了一次，所以两个子集都非空的有序对数为 $3^{10} - 2 \cdot 2^{10} + 1 = 57002$

不相交的非空子集不可能相等，所以每个集合 $\{A, B\}$ 被数了两次，得到 $n = \frac{57002}{2} = 28501$ 。模 $1000$ 的余数是 $501$ 。

Count ordered pairs $(A, B)$ of disjoint subsets first: each of the $10$ elements goes in $A,$ in $B,$ or in neither, for $3^{10}$ pairs. Among these, $2^{10}$ have $A$ empty and $2^{10}$ have $B$ empty, with the pair $(\varnothing, \varnothing)$ counted in both, so $3^{10} - 2 \cdot 2^{10} + 1 = 57002$ ordered pairs have both subsets non-empty.

Disjoint non-empty subsets are never equal, so each set $\{A, B\}$ is counted twice, giving $n = \frac{57002}{2} = 28501.$ The remainder mod $1000$ is $501.$

2002 AIME II 第 9 题

答案：501

难度评级：2500

解答：

其他年份的第 9 题