Question

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 $(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.$

Answer

Solution:

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 $S_n = n \sum_{k=1}^{n} \binom{n-1}{k-1}^2 = n\binom{2n-2}{n-1}.$

Therefore $\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}.$ 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 Problem 12

Solution:

Problem 12 in Other Years