2022 AIME I 第 12 题

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 题