Question

设 $S$ 为集合 $\{1, 2, 3, \ldots, 10\}$ 。令 $n$ 为由 $S$ 的两个非空不相交子集组成的二元集合的个数。（若两个集合没有共同元素，则称它们不相交。）求 $n$ 除以 $1000$ 所得的余数。

Let $S$ be the set $\{1, 2, 3, \ldots, 10\}.$ Let $n$ be the number of sets of two non-empty disjoint subsets of $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$ ，或两者都不放。

Build an ordered pair $(A, B)$ of disjoint subsets by sending each of the $10$ elements to $A,$ to $B,$ or to neither

大提示：

用容斥原理减去 $A$ 或 $B$ 为空的有序对，再除以 $2$ ，得到无序的二元集合。

Subtract the pairs where $A$ or $B$ is empty by inclusion-exclusion, then divide by $2$ to make the pairs unordered

解答：

先数不相交子集的有序对 $(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 题