2022 AIME II Problems/Problem 10
Find the remainder whenis divided by .
Video Solution by OmegaLearn
Solution 1 (Telescoping)
We first write the expression as a summation. is how we force the expression to telescope. ~qyang
Solution 2 (Hockey Stick)
Doing simple algebra calculation will give the following equation:
Next, by using Hockey-Stick Identity, we have:
Since seems like a completely arbitrary number, we can use Engineer's Induction by listing out the first few sums. These are, in the order of how many terms there are starting from term: , , , , , and . Notice that these are just , , , , , . It's clear that this pattern continues up to terms, noticing that the "indexing" starts with instead of . Thus, the value of the sum is .
As in solution 1, obtain Write this as
We can safely write this expression as , since plugging and into both equal meaning they won't contribute to the sum.
Use the sum of powers formulae. We obtain
We can factor the following expression as and simplifying, we have
Substituting and simplifying gets so we would like to find To do this, get Next,
To solve this problem, we need to use the following result:
Now, we use this result to solve this problem.
Therefore, modulo 1000, .
~Steven Chen (www.professorchenedu.com)
Solution 6 (Combinatorial Method)
We examine the expression . Imagine we have a set of integers. Then the expression can be translated to the number of pairs of element subsets of .
To count this, note that each pair of element subsets can either share value or values. In the former case, pick three integers , , and . There are ways to select these integers and ways to pick which one of the three is the shared integer. This gives .
In the latter case, we pick integers , , , and in a total of ways. There are ways to split this up into sets of integers — ways to pick which integers are together and dividing by to prevent overcounting. This gives .
So we have We use the Hockey Stick Identity to evaluate this sum: Evaluating while accounting for mod gives the final answer to be .
|2022 AIME II (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|