Difference between revisions of "2022 AIME I Problems/Problem 12"
Oxymoronic15 (talk | contribs) m |
m (→Problem) |
||
(34 intermediate revisions by 14 users not shown) | |||
Line 1: | Line 1: | ||
− | = Problem = | + | == Problem == |
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>. | ||
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 1 (Easy to Understand)== | ||
+ | |||
+ | Let's try out for small values of <math>n</math> to get a feel for the problem. When <math>n=1, S_n</math> is obviously <math>1</math>. The problem states that for <math>n=2, S_n</math> is <math>4</math>. Let's try it out for <math>n=3</math>. | ||
+ | |||
+ | Let's perform casework on the number of elements in <math>A, B</math>. | ||
+ | |||
+ | <math>\textbf{Case 1:} |A| = |B| = 1</math> | ||
+ | |||
+ | In this case, the only possible equivalencies will be if they are the exact same element, which happens <math>3</math> times. | ||
+ | |||
+ | <math>\textbf{Case 2:} |A| = |B| = 2</math> | ||
+ | |||
+ | In this case, if they share both elements, which happens <math>3</math> times, we will get <math>2</math> for each time, and if they share only one element, which also happens <math>6</math> times, we will get <math>1</math> for each time, for a total of <math>12</math> for this case. | ||
+ | |||
+ | <math>\textbf{Case 3:} |A| = |B| = 3</math> | ||
+ | |||
+ | In this case, the only possible scenario is that they both are the set <math>\{1,2,3\}</math>, and we have <math>3</math> for this case. | ||
+ | |||
+ | |||
+ | In total, <math>S_3 = 18</math>. | ||
+ | |||
+ | 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 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' \subset \{1,2,\ldots,n\} \land B' \not \subset \{k\} </math>) | ||
+ | |||
+ | 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 | ||
+ | ~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> | ||
+ | |||
+ | - 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>). | ||
+ | |||
+ | 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) | ||
+ | |||
+ | ==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== | ||
+ | {{AIME box|year=2022|n=I|num-b=11|num-a=13}} | ||
+ | |||
+ | [[Category:Intermediate Combinatorics Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 16:41, 1 February 2024
Contents
Problem
For any finite set , let
denote the number of elements in
. Define
where the sum is taken over all ordered pairs
such that
and
are subsets of
with
.
For example,
because the sum is taken over the pairs of subsets
giving
.
Let
, where
and
are relatively prime positive integers. Find the remainder when
is divided by
1000.
Solution 1 (Easy to Understand)
Let's try out for small values of to get a feel for the problem. When
is obviously
. The problem states that for
is
. Let's try it out for
.
Let's perform casework on the number of elements in .
In this case, the only possible equivalencies will be if they are the exact same element, which happens times.
In this case, if they share both elements, which happens times, we will get
for each time, and if they share only one element, which also happens
times, we will get
for each time, for a total of
for this case.
In this case, the only possible scenario is that they both are the set , and we have
for this case.
In total, .
Now notice, the number of intersections by each element , or in general,
is equal for each element because of symmetry - each element when
adds
to the answer. Notice that
- let's prove that
(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 - to find a general solution, we must count the number of these subsets that
appears in. For
to be in both
and
, we need both sets to contain
and another subset of
through
not including
. (
and
)
For any that is the size of both
and
, the number of ways to choose the subsets
and
is
for both subsets, so the total number of ways to choose the subsets are
.
Now we sum this over all possible
's to find the total number of ways to form sets
and
that contain
. This is equal to
. This is a simplification of Vandermonde's identity, which states that
. Here,
,
and
are all
, so this sum is equal to
. Finally, since we are iterating over all
's for
values of
, we have
, proving our claim.
We now plug in to the expression we want to find. This turns out to be
. Expanding produces
.
After cancellation, we have
and
don't have any common factors with
, so we're done with the simplification. We want to find
~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 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
by linearity of expectation because for each of the
elements, there is a
probability that the element will be chosen. To find the sum over all such values, we multiply this quantity by
. Summing, we get
Notice that we can rewrite this as
We can simplify this using Vandermonde's identity to get
. Evaluating this for
and
gives
Evaluating the numerators and denominators mod
gives
- pi_is_3.14
Solution 3 (Rigorous)
For each element , denote
, where
(resp.
).
Denote .
Denote .
Hence,
Therefore,
This is in the lowest term.
Therefore, modulo 1000,
~Steven Chen (www.professorchenedu.com)
Solution 4
Let's ask what the contribution of an element is to the sum
The answer is given by the number of such that
and
, which is given by
by the following construction: Write down 1 to
except
in a row. Do the same in a second row. Then choose
numbers out of these
numbers.
and the numbers chosen in the first row make up
.
and the numbers not chosen in the second row make up
. This is a one-to-one correspondence between
and the ways to choose
numbers from
numbers.
The contribution from all elements is therefore
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.