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

小提示：

若 $|\mathcal{A}| = k$ ，则 $|\mathcal{B}| = 12 - k$ ，条件迫使 $k \in \mathcal{B}$ 且 $12 - k \in \mathcal{A}$ 。

If $|\mathcal{A}| = k,$ then $|\mathcal{B}| = 12 - k,$ and the conditions force $k \in \mathcal{B}$ and $12 - k \in \mathcal{A}$

大提示：

对每个 $k \ne 6$ ，从未指定的 $10$ 个数中选择剩下的 $k - 1$ 个元素放入 $\mathcal{A}$ 。情况 $k = 6$ 不成立，因为 $6$ 必须同时属于两个集合。

For each $k \ne 6,$ choose the remaining $k - 1$ elements of $\mathcal{A}$ from the $10$ unassigned numbers. The case $k = 6$ fails because $6$ would have to lie in both sets.

解答：

令 $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}\text{。}$

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 题