Question

对任意有限集合 $X$ ，令 $|X|$ 表示 $X$ 中元素的个数。定义 $S_n = \sum |A \cap B|\text{，}$ 其中求和遍历所有有序数对 $(A, B)$ ，满足 $A$ 和 $B$ 都是 $\{1, 2, 3, \ldots, n\}$ 的子集且 $|A| = |B|$ 。例如， $S_2 = 4$ ，因为求和遍历以下子集对： $\begin{aligned} &(A, B) \in {}\\ &\quad \small\left\{\begin{gathered} (\emptyset, \emptyset), (\{1\}, \{1\}), \\ (\{1\}, \{2\}), (\{2\}, \{1\}), \\ (\{2\}, \{2\}), (\{1, 2\}, \{1, 2\}) \end{gathered}\right\} \end{aligned}\text{，}$ 所以 $S_2 = 0 + 1 + 0 + 0 + 1 + 2 = 4$ 。设 $\frac{S_{2022}}{S_{2021}} = \frac{p}{q}$ ，其中 $p$ 和 $q$ 是互质正整数。求 $p + q$ 除以 $1000$ 的余数。

For any finite set $X,$ let $|X|$ denote the number of elements in $X.$ Define $S_n = \sum |A \cap B|,$ where the sum is taken over all ordered pairs $(A, B)$ such that $A$ and $B$ are subsets of $\{1, 2, 3, \ldots, n\}$ with $|A| = |B|.$ For example, $S_2 = 4$ because the sum is taken over the pairs of subsets $\begin{aligned} &(A, B) \in {}\\ &\quad \small\left\{\begin{gathered} (\emptyset, \emptyset), (\{1\}, \{1\}), \\ (\{1\}, \{2\}), (\{2\}, \{1\}), \\ (\{2\}, \{2\}), (\{1, 2\}, \{1, 2\}) \end{gathered}\right\}, \end{aligned}$ giving $S_2 = 0 + 1 + 0 + 0 + 1 + 2 = 4.$ Let $\frac{S_{2022}}{S_{2021}} = \frac{p}{q},$ where $p$ and $q$ are relatively prime positive integers. Find the remainder when $p + q$ is divided by $1000.$

答案

答案：245

知识点：子集组合双重计数范德蒙德卷积

难度评级：2990

小提示：

交换求和顺序：对每个元素，数满足 $|A| = |B|$ 且两个集合都包含它的数对 $(A, B)$

Swap the order of summation: for each element, count the pairs $(A, B)$ with $|A| = |B|$ that contain it in both sets

大提示：

$\sum_k \binom{n-1}{k-1}^2 = \binom{2n-2}{n-1}$ ，所以 $S_n = n\binom{2n-2}{n-1}$ ；然后化简相邻两项的比值

$\sum_k \binom{n-1}{k-1}^2 = \binom{2n-2}{n-1},$ so $S_n = n\binom{2n-2}{n-1};$ then simplify the ratio of consecutive terms

解答：

按元素计数： $S_n$ 等于三元组 $(x, A, B)$ 的个数，其中 $|A| = |B|$ 且 $x \in A \cap B$ 。固定 $x$ 和集合大小 $k$ 后，包含 $x$ 的 $A$ 和 $B$ 各有 $\binom{n-1}{k-1}$ 种选择，所以由范德蒙德恒等式， $\begin{aligned} S_n &= n \sum_{k=1}^{n} \binom{n-1}{k-1}^2 \\ &= n\binom{2n-2}{n-1} \end{aligned}\text{。}$

因此 $\begin{aligned} \frac{S_{2022}}{S_{2021}} &= \frac{2022\binom{4042}{2021}}{2021\binom{4040}{2020}} \\ &= \frac{2022}{2021} \cdot \frac{4042 \cdot 4041}{2021^2} \\ &= \frac{2 \cdot 2022 \cdot 4041}{2021^2} \end{aligned}\text{。}$ 因为 $2021 = 43 \cdot 47$ ，它不整除 $2022$ 、 $4041 = 3^2 \cdot 449$ 或 $2$ ，所以该分数已最简： $p = 2 \cdot 2022 \cdot 4041 = 16341804$ ，且 $q = 2021^2 = 4084441$ 。

于是 $p + q = 20426245$ ，除以 $1000$ 的余数为 $245$ 。

Count element by element: $S_n$ equals the number of triples $(x, A, B)$ with $|A| = |B|$ and $x \in A \cap B.$ For a fixed $x$ and size $k,$ there are $\binom{n-1}{k-1}$ choices for each of $A$ and $B$ containing $x,$ so by the Vandermonde identity $\begin{aligned} S_n &= n \sum_{k=1}^{n} \binom{n-1}{k-1}^2 \\ &= n\binom{2n-2}{n-1}. \end{aligned}$

Therefore $\begin{aligned} \frac{S_{2022}}{S_{2021}} &= \frac{2022\binom{4042}{2021}}{2021\binom{4040}{2020}} \\ &= \frac{2022}{2021} \cdot \frac{4042 \cdot 4041}{2021^2} \\ &= \frac{2 \cdot 2022 \cdot 4041}{2021^2}. \end{aligned}$ Since $2021 = 43 \cdot 47$ divides neither $2022,$ $4041 = 3^2 \cdot 449,$ nor $2,$ this fraction is in lowest terms: $p = 2 \cdot 2022 \cdot 4041 = 16341804$ and $q = 2021^2 = 4084441.$

Then $p + q = 20426245,$ whose remainder modulo $1000$ is $245.$

2022 AIME I 第 12 题

答案：245

难度评级：2990

小提示：

大提示：

解答：

其他年份的第 12 题