2022 AIME I Problems/Problem 12

Problem

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 $\left\{ 1 , 2 , 3, \cdots , n \right\}$ with $|A| = |B|$ . For example, $S_2 = 4$ because the sum is taken over the pairs of subsets $(A, B) \in \left\{ (\emptyset, \emptyset) , ( \{1\} , \{1\} ), ( \{1\} , \{2\} ) , ( \{2\} , \{1\} ) , ( \{2\} , \{2\} ) , ( \{1 , 2\} , \{1 , 2\} ) \right\} ,$ 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.

Solution 1 (Easy to Understand)

Let's try out for small values of $n$ to get a feel for the problem.

Solution 2 (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{align*} 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{align*}$

Therefore, $\begin{align*} \frac{S_{2022}}{S_{2021}} & = \frac{2022 \binom{4042}{2021}}{2021 \binom{4040}{2020}} \\ & = \frac{4044 \cdot 4041}{2021^2} . \end{align*}$

This is in the lowest term. Therefore, modulo 1000, $\begin{align*} p + q & \equiv 4044 \cdot 4041 + 2021^2 \\ & \equiv 44 \cdot 41 + 21^2 \\ & \equiv \boxed{\textbf{(245) }} . \end{align*}$

~Steven Chen (www.professorchenedu.com)

2022 AIME I (Problems • Answer Key • Resources)
Preceded by Problem 11	Followed by Problem 13
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search

2022 AIME I Problems/Problem 12

Contents

Problem

Solution 1 (Easy to Understand)

Solution 2 (Rigorous)

See Also