2022 AIME I Problems/Problem 12
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
Solution 3 (Rigorous)
For each element , denote , where (resp. ).
This is in the lowest term. Therefore, modulo 1000,
~Steven Chen (www.professorchenedu.com)
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.
https://youtu.be/wTYXkE32v9o ~AMC & AIME Training
|2022 AIME I (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|