Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2022 AIME I Problems/Problem 12"

m
Line 16: Line 16:
 
Let <math>\frac{S_{2022}}{S_{2021}} = \frac{p}{q}</math>, where <math>p</math> and <math>q</math> are relatively prime positive integers. Find the remainder when <math>p + q</math> is divided by
 
Let <math>\frac{S_{2022}}{S_{2021}} = \frac{p}{q}</math>, where <math>p</math> and <math>q</math> are relatively prime positive integers. Find the remainder when <math>p + q</math> is divided by
 
1000.
 
1000.
 +
 +
==Solution==
 +
For each element <math>i</math>, denote <math>x_i = \left( x_{i, A}, x_{i, B} \right) \in \left\{ 0 , 1 \right\}^2</math>, where <math>x_{i, A} = \Bbb I \left\{ i \in A \right\}</math> (resp. <math>x_{i, B} = \Bbb I \left\{ i \in B \right\}</math>).
 +
 +
Denote <math>\Omega = \left\{ (x_1, \cdots , x_n): \sum_{i = 1}^n x_{i, A} = \sum_{i = 1}^n x_{i, B} \right\}</math>.
 +
 +
Denote <math>\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\}</math>.
 +
 +
Hence,
 +
<cmath>
 +
\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*}
 +
</cmath>
 +
 +
Therefore,
 +
<cmath>
 +
\begin{align*}
 +
\frac{S_{2022}}{S_{2021}}
 +
& = \frac{2022 \binom{4042}{2021}}{2021 \binom{4040}{2020}} \\
 +
& = \frac{4044 \cdot 4041}{2021^2} .
 +
\end{align*}
 +
</cmath>
 +
 +
This is in the lowest term.
 +
Therefore, modulo 1000,
 +
<cmath>
 +
\begin{align*}
 +
p + q
 +
& \equiv 4044 \cdot 4041 + 2021^2 \\
 +
& \equiv 44 \cdot 41 + 21^2 \\
 +
& \equiv \boxed{\textbf{(245) }} .
 +
\end{align*}
 +
</cmath>
 +
 +
~Steven Chen (www.professorchenedu.com)

Revision as of 23:01, 17 February 2022

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

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)

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2022_AIME_I_Problems/Problem_12&oldid=171288"