Difference between revisions of "2020 AIME II Problems/Problem 8"
(→Solution 2 (Same idea, easier to see)) |
Orion 2010 (talk | contribs) m (→Solution 2 (Same idea, easier to see)) |
||
(5 intermediate revisions by 5 users not shown) | |||
Line 11: | Line 11: | ||
==Solution 2 (Same idea, easier to see)== | ==Solution 2 (Same idea, easier to see)== | ||
− | Starting from <math>f_1(x)=|x-1|</math>, we can track the solutions, the number of solutions, and their sum | + | Starting from <math>f_1(x)=|x-1|</math>, we can track the solutions, the number of solutions, and their sum: |
<cmath>\begin{array}{c|c|c|c} | <cmath>\begin{array}{c|c|c|c} | ||
− | + | n&Solutions&number&sum\ | |
1&1&1&1\ | 1&1&1&1\ | ||
2&1,3&2&4\ | 2&1,3&2&4\ | ||
3&0,2,4,6&4&12\ | 3&0,2,4,6&4&12\ | ||
4&-2,0,2...10&7&28\ | 4&-2,0,2...10&7&28\ | ||
− | 5&- | + | 5&-5,-3,-1...15&11&55\ |
\end{array}</cmath> | \end{array}</cmath> | ||
It is clear that the solutions form arithmetic sequences with a difference of 2, and the negative solutions cancel out all but <math>n</math> of the <math>1+\frac{n(n-1)}{2}</math> solutions. Thus, the sum of the solutions is <math>n \cdot [1+\frac{n(n-1)}{2}]</math>, which is a cubic function. | It is clear that the solutions form arithmetic sequences with a difference of 2, and the negative solutions cancel out all but <math>n</math> of the <math>1+\frac{n(n-1)}{2}</math> solutions. Thus, the sum of the solutions is <math>n \cdot [1+\frac{n(n-1)}{2}]</math>, which is a cubic function. | ||
+ | (Side Note: Gergor-Newton Interpolation Formula is applicable here) | ||
<math>n \cdot [1+\frac{n(n-1)}{2}]>500,000</math> | <math>n \cdot [1+\frac{n(n-1)}{2}]>500,000</math> | ||
Line 35: | Line 36: | ||
~ dragnin | ~ dragnin | ||
− | |||
− | |||
− | |||
− | |||
− | |||
==Video Solution== | ==Video Solution== | ||
https://youtu.be/g13o0wgj4p0 | https://youtu.be/g13o0wgj4p0 | ||
− | |||
− | |||
==See Also== | ==See Also== |
Latest revision as of 20:00, 11 January 2025
Contents
[hide]Problem
Define a sequence recursively by and for integers . Find the least value of such that the sum of the zeros of exceeds .
Solution 1 (Official MAA)
First it will be shown by induction that the zeros of are the integers , where
This is certainly true for . Suppose that it is true for , and note that the zeros of are the solutions of , where is a nonnegative zero of . Because the zeros of form an arithmetic sequence with common difference so do the zeros of . The greatest zero of isso the greatest zero of is and the least is .
It follows that the number of zeros of is , and their average value is . The sum of the zeros of isLet , so the sum of the zeros exceeds if and only if Because is increasing for , the values and show that the requested value of is .
Solution 2 (Same idea, easier to see)
Starting from , we can track the solutions, the number of solutions, and their sum:
It is clear that the solutions form arithmetic sequences with a difference of 2, and the negative solutions cancel out all but of the solutions. Thus, the sum of the solutions is , which is a cubic function. (Side Note: Gergor-Newton Interpolation Formula is applicable here)
Multiplying both sides by ,
1 million is , so the solution should be close to .
100 is slightly too small, so works.
~ dragnin
Video Solution
See Also
2020 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 7 |
Followed by Problem 9 | |
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.