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"

(→‎Solution 1 (Easy to Understand))
m (→‎Problem)
 
(26 intermediate revisions by 12 users not shown)
Line 2: Line 2:
 
For any finite set <math>X</math>, let <math>| X |</math> denote the number of elements in <math>X</math>. Define
 
For any finite set <math>X</math>, let <math>| X |</math> denote the number of elements in <math>X</math>. Define
 
<cmath>
 
<cmath>
−
\[
 
 
S_n = \sum | A \cap B | ,
 
S_n = \sum | A \cap B | ,
−
\]
 
 
</cmath>
 
</cmath>
 
where the sum is taken over all ordered pairs <math>(A, B)</math> such that <math>A</math> and <math>B</math> are subsets of <math>\left\{ 1 , 2 , 3,  \cdots , n \right\}</math> with <math>|A| = |B|</math>.
 
where the sum is taken over all ordered pairs <math>(A, B)</math> such that <math>A</math> and <math>B</math> are subsets of <math>\left\{ 1 , 2 , 3,  \cdots , n \right\}</math> with <math>|A| = |B|</math>.
 
For example, <math>S_2 = 4</math> because the sum is taken over the pairs of subsets
 
For example, <math>S_2 = 4</math> because the sum is taken over the pairs of subsets
 
<cmath>
 
<cmath>
−
\[
 
 
(A, B) \in \left\{ (\emptyset, \emptyset) , ( \{1\} , \{1\} ), ( \{1\} , \{2\} ) , ( \{2\} , \{1\} ) , ( \{2\} , \{2\} ) , ( \{1 , 2\} , \{1 , 2\} ) \right\} ,
 
(A, B) \in \left\{ (\emptyset, \emptyset) , ( \{1\} , \{1\} ), ( \{1\} , \{2\} ) , ( \{2\} , \{1\} ) , ( \{2\} , \{2\} ) , ( \{1 , 2\} , \{1 , 2\} ) \right\} ,
−
\]
 
 
</cmath>
 
</cmath>
 
giving <math>S_2 = 0 + 1 + 0 + 0 + 1 + 2 = 4</math>.
 
giving <math>S_2 = 0 + 1 + 0 + 0 + 1 + 2 = 4</math>.
Line 40: Line 36:
 
Now notice, the number of intersections by each element <math>1 \ldots 3</math>, or in general, <math>1 \ldots n</math> is equal for each element because of symmetry - each element when <math>n=3</math> adds <math>6</math> to the answer. Notice that <math>6 = \binom{4}{2}</math> - let's prove that <math>S_n = n \cdot \binom{2n-2}{n-1}</math> (note that you can assume this and answer the problem if you're running short on time in the real test).
 
Now notice, the number of intersections by each element <math>1 \ldots 3</math>, or in general, <math>1 \ldots n</math> is equal for each element because of symmetry - each element when <math>n=3</math> adds <math>6</math> to the answer. Notice that <math>6 = \binom{4}{2}</math> - let's prove that <math>S_n = n \cdot \binom{2n-2}{n-1}</math> (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 <math>k</math> - to find a general solution, we must count the number of these subsets that <math>k</math> appears in. For <math>k</math> to be in both <math>A</math> and <math>B</math>, we need <math>A = \{k\} \cup A'| A' \in \{1,2,\ldots,n\} \land A' \not \in \{k\} </math> and  
+
Let's analyze the element <math>k</math> - to find a general solution, we must count the number of these subsets that <math>k</math> appears in. For <math>k</math> to be in both <math>A</math> and <math>B</math>, we need both sets to contain <math>k</math> and another subset of <math>1</math> through <math>n</math> not including <math>k</math>. (<math>A = \{k\} \cup A'| A' \subset \{1,2,\ldots,n\} \land A' \not \subset \{k\} </math> and  
−
<math>B = \{k\} \cup B'| B' \in \{1,2,\ldots,n\} \land B' \not \in \{k\} </math> (Basically, both sets contain <math>k</math> and another subset of <math>1</math> through <math>n</math> not including <math>k</math>).
+
<math>B = \{k\} \cup B'| B' \subset \{1,2,\ldots,n\} \land B' \not \subset \{k\} </math>)
−
Solution in Progress
+
 
 +
For any <math>0\leq l \leq n-1</math> that is the size of both <math>A'</math> and <math>B'</math>, the number of ways to choose the subsets <math>A'</math> and <math>B'</math> is <math>\binom{n-1}{l}</math> for both subsets, so the total number of ways to choose the subsets are <math>\binom{n-1}{l}^2</math>.
 +
Now we sum this over all possible <math>l</math>'s to find the total number of ways to form sets <math>A</math> and <math>B</math> that contain <math>k</math>. This is equal to <math>\sum_{l=0}^{n-1} \binom{n-1}{l}^2</math>. This is a simplification of Vandermonde's identity, which states that <math>\sum_{k=0}^{r} \binom{m}{k} \cdot \binom{n}{r-k} = \binom{m+n}{r}</math>. Here, <math>m</math>, <math>n</math> and <math>r</math> are all <math>n-1</math>, so this sum is equal to <math>\binom{2n-2}{n-1}</math>. Finally, since we are iterating over all <math>k</math>'s for <math>n</math> values of <math>k</math>, we have <math>S_n = n \cdot \binom{2n-2}{n-1}</math>, proving our claim.
 +
 
 +
We now plug in <math>S_n</math> to the expression we want to find. This turns out to be <math>\frac{2022 \cdot \binom{4042}{2021}}{2021 \cdot \binom{4040}{2020}}</math>. Expanding produces <math>\frac{2022 \cdot 4042!\cdot 2020! \cdot 2020!}{2021 \cdot 4040! \cdot 2021! \cdot 2021!}</math>.
 +
 
 +
After cancellation, we have <cmath>\frac{2022 \cdot 4042 \cdot 4041}{2021 \cdot 2021 \cdot 2021} \implies \frac{4044\cdot 4041}{2021 \cdot 2021}</cmath>
 +
 
 +
<math>4044</math> and <math>4041</math> don't have any common factors with <math>2021</math>, so we're done with the simplification. We want to find <math>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}</math>
 +
 
 +
 
 
~KingRavi
 
~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 <math>k</math> 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 <math>n \cdot \frac{k}{n} \cdot \frac{k}{n}</math> by linearity of expectation because for each of the <math>n</math> elements, there is a <math>\frac{k}{n}</math> probability that the element will be chosen. To find the sum over all such values, we multiply this quantity by  <math>\binom{n}{k}^2</math>. Summing, we get <cmath>\sum_{k=1}^{n} \frac{k^2}{n} \binom{n}{k}^2</cmath> Notice that we can rewrite this as <cmath>\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}</cmath> We can simplify this using Vandermonde's identity to get <math>n \binom{2n - 2}{n - 1}</math>. Evaluating this for <math>2022</math> and <math>2021</math> gives <cmath>\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}</cmath> Evaluating the numerators and denominators mod <math>1000</math> gives <math>804 + 441 = 1\boxed{245}</math>
  
−
==Solution 2 (Rigorous)==
+
- pi_is_3.14
 +
 
 +
==Solution 3 (Rigorous)==
 
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>).
 
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>).
  
Line 87: Line 99:
  
 
~Steven Chen (www.professorchenedu.com)
 
~Steven Chen (www.professorchenedu.com)
 +
 +
==Solution 4==
 +
Let's ask what the contribution of an element <math>k\in \{1,2,\cdots,n\}</math> is to the sum <math>S_n = \sum | A \cap B |.</math>
 +
 +
The answer is given by the number of <math>(A,B)</math> such that <math>|A|=|B|</math> and <math>k \in A\cap B</math>, which is given by <math>\binom{2n-2}{n-1}</math>
 +
by the following construction: Write down 1 to <math>n</math> except <math>k</math> in a row. Do the same in a second row. Then choose <math>n-1</math> numbers out of these <math>2n-2</math> numbers. <math>k</math> and the numbers chosen in the first row make up <math>A</math>. <math>k</math> and the numbers not chosen in the second row make up <math>B</math>. This is a one-to-one correspondence between <math>(A,B)</math> and the ways to choose <math>n-1</math> numbers from <math>2n-2</math> numbers.
 +
 +
The contribution from all elements is therefore
 +
<cmath>S_n = n\binom{2n-2}{n-1}.</cmath>
 +
For the rest please see Solution 1 or 2.
 +
 +
~qyang
 +
 +
==Video Solution==
 +
https://youtu.be/cXJmHV5BnfY ~MathProblemSolvingSkills.com
 +
 +
https://youtu.be/wTYXkE32v9o ~AMC & AIME Training
  
 
==See Also==
 
==See Also==
 
{{AIME box|year=2022|n=I|num-b=11|num-a=13}}
 
{{AIME box|year=2022|n=I|num-b=11|num-a=13}}
 +
 +
[[Category:Intermediate Combinatorics Problems]]
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 15:41, 1 February 2024

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. 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{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)

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

Video Solution

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

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

See Also

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

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