Question

设 $N$ 是满足以下性质的非空集合 $\mathcal{A}$ 和 $\mathcal{B}$ 的有序对数：• $\mathcal{A} \cup \mathcal{B}$ $\small = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12\}$ ，• $\mathcal{A} \cap \mathcal{B} = \emptyset$ ，• $\mathcal{A}$ 的元素个数不属于 $\mathcal{A}$ ，• $\mathcal{B}$ 的元素个数不属于 $\mathcal{B}$ 。求 $N$ 。

Let $N$ be the number of ordered pairs of nonempty sets $\mathcal{A}$ and $\mathcal{B}$ that have the following properties: • $\mathcal{A} \cup \mathcal{B}$ $\small = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12\},$ • $\mathcal{A} \cap \mathcal{B} = \emptyset,$ • the number of elements of $\mathcal{A}$ is not an element of $\mathcal{A},$ • the number of elements of $\mathcal{B}$ is not an element of $\mathcal{B}.$ Find $N.$

答案

答案：772

知识点：子集组合补集计数

难度评级：2520

解答：

令 $k = |\mathcal{A}|$ ，则 $|\mathcal{B}| = 12 - k$ ，其中 $1 \le k \le 11$ 。因为每个元素恰好属于一个集合， $k \notin \mathcal{A}$ 意味着 $k \in \mathcal{B}$ ，而 $12 - k \notin \mathcal{B}$ 意味着 $12 - k \in \mathcal{A}$ 。若 $k = 6$ ，则 $6$ 必须同时属于两个集合，这是不可能的，所以 $k \ne 6$ 。

对其他每个 $k$ ，元素 $k$ 和 $12 - k$ 已经放好， $\mathcal{A}$ 中剩下的 $k - 1$ 个元素可从其他 $10$ 个数中选出，有 $\binom{10}{k-1}$ 种方式， $\mathcal{B}$ 取其余元素。因此 $\begin{aligned} N &= \sum_{k=1}^{11} \binom{10}{k-1} - \binom{10}{5} \\ &= 2^{10} - 252 = 772. \end{aligned}$

Let $k = |\mathcal{A}|,$ so $|\mathcal{B}| = 12 - k$ with $1 \le k \le 11.$ Since every element lies in exactly one set, $k \notin \mathcal{A}$ means $k \in \mathcal{B},$ and $12 - k \notin \mathcal{B}$ means $12 - k \in \mathcal{A}.$ If $k = 6,$ then $6$ would have to belong to both sets, which is impossible, so $k \ne 6.$

For each other $k,$ the elements $k$ and $12 - k$ are already placed, and the remaining $k - 1$ elements of $\mathcal{A}$ can be chosen from the other $10$ numbers in $\binom{10}{k-1}$ ways, with $\mathcal{B}$ taking the rest. Hence $\begin{aligned} N &= \sum_{k=1}^{11} \binom{10}{k-1} - \binom{10}{5} \\ &= 2^{10} - 252 = 772. \end{aligned}$

2010 AIME II 第 8 题

答案：772

难度评级：2520

解答：

其他年份的第 8 题