Difference between revisions of "2022 AIME I Problems/Problem 12"
m (→Solution 3) |
m (→Problem) |
||
(2 intermediate revisions by 2 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 50: | Line 46: | ||
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> | 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} | + | <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> |
Line 56: | Line 52: | ||
~Edited by MY-2 | ~Edited by MY-2 | ||
− | ==Linearity of Expectation | + | ==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> | 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> | ||
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.