AIME 2022 I · 第 12 题

Solution 1 (Easy to Understand)

Let's try out for small values of $n$ to get a feel for the problem. When $n=1, S_n$ is obviously $1$. The problem states that for $n=2, S_n$ is $4$. Let's try it out for $n=3$.

Let's perform casework on the number of elements in $A, B$.

$\textbf{Case 1:} |A| = |B| = 1$

In this case, the only possible equivalencies will be if they are the exact same element, which happens $3$ times.

$\textbf{Case 2:} |A| = |B| = 2$

In this case, if they share both elements, which happens $3$ times, we will get $2$ for each time, and if they share only one element, which also happens $6$ times, we will get $1$ for each time, for a total of $12$ for this case.

$\textbf{Case 3:} |A| = |B| = 3$

In this case, the only possible scenario is that they both are the set $\{1,2,3\}$, and we have $3$ for this case.

In total, $S_3 = 18$.

Now notice, the number of intersections by each element $1 \ldots 3$, or in general, $1 \ldots n$ is equal for each element because of symmetry - each element when $n=3$ adds $6$ to the answer. Notice that $6 = \binom{4}{2}$ - let's prove that $S_n = n \cdot \binom{2n-2}{n-1}$ (note that you can assume this and answer the problem if you're running short on time in the real test).

Let's analyze the element $k$ - to find a general solution, we must count the number of these subsets that $k$ appears in. For $k$ to be in both $A$ and $B$, we need both sets to contain $k$ and another subset of $1$ through $n$ not including $k$. ($A = \{k\} \cup A'| A' \subset \{1,2,\ldots,n\} \land A' \not \subset \{k\}$ and $B = \{k\} \cup B'| B' \subset \{1,2,\ldots,n\} \land B' \not \subset \{k\}$)

For any $0\leq l \leq n-1$ that is the size of both $A'$ and $B'$, the number of ways to choose the subsets $A'$ and $B'$ is $\binom{n-1}{l}$ for both subsets, so the total number of ways to choose the subsets are $\binom{n-1}{l}^2$. Now we sum this over all possible $l$'s to find the total number of ways to form sets $A$ and $B$ that contain $k$. This is equal to $\sum_{l=0}^{n-1} \binom{n-1}{l}^2$. This is a simplification of Vandermonde's identity, which states that $\sum_{k=0}^{r} \binom{m}{k} \cdot \binom{n}{r-k} = \binom{m+n}{r}$. Here, $m$, $n$ and $r$ are all $n-1$, so this sum is equal to $\binom{2n-2}{n-1}$. Finally, since we are iterating over all $k$'s for $n$ values of $k$, we have $S_n = n \cdot \binom{2n-2}{n-1}$, proving our claim.

We now plug in $S_n$ to the expression we want to find. This turns out to be $\frac{2022 \cdot \binom{4042}{2021}}{2021 \cdot \binom{4040}{2020}}$. Expanding produces $\frac{2022 \cdot 4042!\cdot 2020! \cdot 2020!}{2021 \cdot 4040! \cdot 2021! \cdot 2021!}$.

After cancellation, we have

$$\frac{2022 \cdot 4042 \cdot 4041}{2021 \cdot 2021 \cdot 2021} \implies \frac{4044\cdot 4041}{2021 \cdot 2021}$$ $4044$ and $4041$ don't have any common factors with $2021$, so we're done with the simplification. We want to find $4044 \cdot 4041 + 2021^2 \pmod{1000} \equiv 44 \cdot 41 + 21^2 \pmod{1000} \equiv 1804+441 \pmod{1000} \equiv 2245 \pmod{1000} \equiv \boxed{245}$

~KingRavi ~Edited by MY-2

Solution 2 (Linearity of Expectation)

We take cases based on the number of values in each of the subsets in the pair. Suppose we have $k$ elements in each of the subsets in a pair (for a total of n elements in the set). The expected number of elements in any random pair will be $n \cdot \frac{k}{n} \cdot \frac{k}{n}$ by linearity of expectation because for each of the $n$ elements, there is a $\frac{k}{n}$ probability that the element will be chosen. To find the sum over all such values, we multiply this quantity by $\binom{n}{k}^2$. Summing, we get

$$\sum_{k=1}^{n} \frac{k^2}{n} \binom{n}{k}^2$$ Notice that we can rewrite this as

$$\sum_{k=1}^{n} \frac{1}{n} \left(\frac{k \cdot n!}{(k)!(n - k)!}\right)^2 = \sum_{k=1}^{n} \frac{1}{n} n^2 \left(\frac{(n-1)!}{(k - 1)!(n - k)!}\right)^2 = n \sum_{k=1}^{n} \binom{n - 1}{k - 1}^2 = n \sum_{k=1}^{n} \binom{n - 1}{k - 1}\binom{n - 1}{n - k}$$ We can simplify this using Vandermonde's identity to get $n \binom{2n - 2}{n - 1}$. Evaluating this for $2022$ and $2021$ gives

$$\frac{2022\binom{4042}{2021}}{2021\binom{4040}{2020}} = \frac{2022 \cdot 4042 \cdot 4041}{2021^3} = \frac{2022 \cdot 2 \cdot 4041}{2021^2}$$ Evaluating the numerators and denominators mod $1000$ gives $804 + 441 = 1\boxed{245}$

- pi_is_3.14

Solution 3 (Rigorous)

For each element $i$, denote $x_i = \left( x_{i, A}, x_{i, B} \right) \in \left\{ 0 , 1 \right\}^2$, where $x_{i, A} = \Bbb I \left\{ i \in A \right\}$ (resp. $x_{i, B} = \Bbb I \left\{ i \in B \right\}$).

Denote $\Omega = \left\{ (x_1, \cdots , x_n): \sum_{i = 1}^n x_{i, A} = \sum_{i = 1}^n x_{i, B} \right\}$.

Denote $\Omega_{-j} = \left\{ (x_1, \cdots , x_{j-1} , x_{j+1} , \cdots , x_n): \sum_{i \neq j} x_{i, A} = \sum_{i \neq j} x_{i, B} \right\}$.

Hence,

$$\begin{aligned} S_n & = \sum_{(x_1, \cdots , x_n) \in \Omega} \sum_{i = 1}^n \Bbb I \left\{ x_{i, A} = x_{i, B} = 1 \right\} \\ & = \sum_{i = 1}^n \sum_{(x_1, \cdots , x_n) \in \Omega} \Bbb I \left\{ x_{i, A} = x_{i, B} = 1 \right\} \\ & = \sum_{i = 1}^n \sum_{(x_1, \cdots , x_{i-1} , x_{i+1} , \cdots , x_n) \in \Omega_{-i}} 1 \\ & = \sum_{i = 1}^n \sum_{j=0}^{n-1} \left( \binom{n-1}{j} \right)^2 \\ & = n \sum_{j=0}^{n-1} \left( \binom{n-1}{j} \right)^2 \\ & = n \sum_{j=0}^{n-1} \binom{n-1}{j} \binom{n-1}{n-1-j} \\ & = 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{4044 \cdot 4041}{2021^2} . \end{aligned}$$ This is in the lowest term. Therefore, modulo 1000,

$$\begin{aligned} p + q & \equiv 4044 \cdot 4041 + 2021^2 \\ & \equiv 44 \cdot 41 + 21^2 \\ & \equiv \boxed{\textbf{(245) }} . \end{aligned}$$ ~Steven Chen (www.professorchenedu.com)

Solution 4

Let's ask what the contribution of an element $k\in \{1,2,\cdots,n\}$ is to the sum $S_n = \sum | A \cap B |.$

The answer is given by the number of $(A,B)$ such that $|A|=|B|$ and $k \in A\cap B$, which is given by $\binom{2n-2}{n-1}$ by the following construction: Write down 1 to $n$ except $k$ in a row. Do the same in a second row. Then choose $n-1$ numbers out of these $2n-2$ numbers. $k$ and the numbers chosen in the first row make up $A$. $k$ and the numbers not chosen in the second row make up $B$. This is a one-to-one correspondence between $(A,B)$ and the ways to choose $n-1$ numbers from $2n-2$ numbers.

The contribution from all elements is therefore

$$S_n = n\binom{2n-2}{n-1}.$$ For the rest please see Solution 1 or 2.

~qyang

NOTE: you may have a concern, "what if we chose the same element twice in a set?" Let us look at an example. Suppose we are partioning $S_4,$ $k=4,$ and we list out the rows top: $1,2,3$ bottom: $1,2,3$ If we chose $1$ (top) $2$ (top) and $1$ (bottom), then we can distribute these numbers by sending the numbers in the top row that were chosen to set $A,$ which would be ${1,2,4},$ and set $B$ would be the numbers not chosen in the bottom row, which would be ${2,3,4}.$ To prove this rigourously, let $x$ be the number of elements in the top row chosen and $y$ be the number of elements chosen in the bottom row. Since we choose $n-1$ objects, $x+y=n-1.$ So the amount of elements in $A$ would be $1+x,$ and the amount of elements in $B$ would be $1+(n-1-y)=1+n-1-(n-1-x)=x+1.$

~eqb5000

Solution 5 (No strange notation, proof of all combo lemmas provided)

Assume the subset $A$ of $\{1, 2, 3, \dots, n\}$ has $k$ elements, where $k$ is some integer from $0$ to $n$, inclusive. Then, there are $\tbinom{n}{k}$ ways to choose $A$. Now, we find the amount of ways to choose $B$, given $A$. Assume that $A$ and $B$ have $a$ elements in common, where $0 \le a \le k$. Then, $a$ of the elements in $B$ are also in $A$, so we can pick $\tbinom{k}{a}$ elements here, and the remaining $k-a$ elements in $B$ are $\underline{\text{not}}$ in $A$, so we can pick $\tbinom{n-k}{k-a}$ elements here. Therefore, there are $\tbinom{k}{a}\tbinom{n-k}{k-a}$ ways to select $B$ if $A$ and $B$ have $a$ elements in common.

However, if $A$ and $B$ have $a$ elements in common, the ordered pair $(A, B)$ will contribute $a$ to the total sum. Thus, we multiply by $a$. Since the amount of ways to choose $B$ ranges over all $0 \le a \le k$, we seek the sum;

$\binom{n}{k}\sum_{a=0}^{k} a\binom{k}{a}\binom{n-k}{k-a}$.

The $\binom{n}{k}$ on the outside of the sum represents the amount of ways to choose $A$. Now, we simplify the $a\tbinom{k}{a}$ term a little bit

Note that $a\tbinom{k}{a}=a \cdot \frac{k!}{a!(k-a)!}=\frac{k!}{(a-1)!(k-a)!}=k \cdot \frac{(k-1)!}{(a-1)!(k-a)!}=k\binom{k-1}{a-1}$

The reason we did this is because we want the $a$ in the combination expression, and not as a scale factor. Then, the sum simplifies to

$\binom{n}{k} \sum_{a=0}^{k} k\binom{k-1}{a-1}\binom{n-k}{k-a}$. We can take $k$ out of the sum (it's a constant in the sum), and the sum turns into

$k\binom{n}{k}\sum_{a=0}^{k}\binom{k-1}{a-1}\binom{n-k}{k-a}$.

Now, we use a combinatorial identity called Vandermode's Identity (This identity is well known, if you don't know it, learn it; it's useful for these types of problems). Consider $x+y$ people. We wish to form a committee with $r$ people. We can do this in $\tbinom{x+y}{r}$ ways. However, we can choose $k$ people from the group of $x$ people and $r-k$ people from the other $y$ people, for all $0 \le k \le r$.

This is done in $\sum_{k=0}^{r} \binom{x}{k} \binom{y}{r-k}$ ways, but this is also equal to $\binom{x+y}{r}$.

In our desired sum, we have $x=k-1$, $y=n-k$, and $r=(a-1)+(k-a)=k-1$. Thus, the summation part is equal to $\binom{n-1}{k-1}$, and the total product is $k\binom{n}{k}\binom{n-1}{k-1}$.

Now, we want to sum this over all possible $k$, for $0 \le k \le n$.

This is $\sum_{k=0}^{n} k\binom{n}{k}\binom{n-1}{k-1}$. We can do something with the $k\binom{n}{k}$ term that was similar to something we did last time to obtain that this is also equal to $n\binom{n-1}{k-1}$.

Then, the sum simplifies to $n\sum_{k=0}^{n} \binom{n-1}{k-1} \binom{n-1}{k-1}=n\sum_{k=0}^{n}\binom{n-1}{k-1}^{2}$.

We can use Vandermode's again, with $x=y=n-1$ and $r=(k-1)+(k-1)=2k-2$. Then, the sum is equal to $n\binom{2n-2}{n-1}$.

Now, the problem seeks $\frac{S_{2022}}{S_{2021}}$. This is equal to $\frac{2022\tbinom{4042}{2021}}{2021\tbinom{4040}{2020}}=\frac{\frac{2022 \cdot 4042!}{2021! \cdot 2021!}}{\frac{2021 \cdot 4040!}{2020! \cdot 2020!}}=\frac{2022 \cdot 4042! \cdot 2020! \cdot 2020!}{2021 \cdot 4040! \cdot 2021! \cdot 2021!}=\frac{2022 \cdot 4042 \cdot 4041}{2021 \cdot 2021 \cdot 2021}=\frac{2022 \cdot 2 \cdot 4041}{2021 \cdot 2021}$.

We seek $2022 \cdot 2 \cdot 4041 + 2021 \cdot 2021 \pmod{1000}$. This is equivalent to $22 \cdot 82 + 21 \cdot 21 \equiv 804+441 \equiv \boxed{245} \pmod{1000}$, and we are done.

Video Solution

https://youtu.be/cXJmHV5BnfY ~MathProblemSolvingSkills.com

https://youtu.be/wTYXkE32v9o ~AMC & AIME Training