Difference between revisions of "2022 AIME I Problems/Problem 12"
m |
Mathandski (talk | contribs) m (fixed sad latex, also made the "easy to understand" solution easier to read) |
||
Line 40: | Line 40: | ||
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' \subset \{1,2,\ldots,n\} \land A' \not \subset \{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' \subset \{1,2,\ldots,n\} \land B' \not \subset \{k\} | + | <math>B = \{k\} \cup B'| B' \subset \{1,2,\ldots,n\} \land B' \not \subset \{k\} </math>) |
− | For any <math>0 | + | 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. | 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. | ||
Line 50: | Line 50: | ||
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} = 44 \cdot 41 + 21^2 \pmod{1000} = 1804+ | + | <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} = 44 \cdot 41 + 21^2 \pmod{1000} = 1804+481 \pmod{1000} = 2245 \pmod{1000} = \boxed{245}</math> |
Revision as of 23:58, 11 October 2022
Contents
[hide]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
Linearity of Expectation Solution
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 2 (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)
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.