Difference between revisions of "2020 AIME II Problems/Problem 8"
Topnotchmath (talk | contribs) m |
m (→Video Solution) |
||
(16 intermediate revisions by 10 users not shown) | |||
Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
+ | Define a sequence recursively by <math>f_1(x)=|x-1|</math> and <math>f_n(x)=f_{n-1}(|x-n|)</math> for integers <math>n>1</math>. Find the least value of <math>n</math> such that the sum of the zeros of <math>f_n</math> exceeds <math>500,000</math>. | ||
+ | |||
+ | ==Solution 1 (Official MAA)== | ||
+ | First it will be shown by induction that the zeros of <math>f_n</math> are the integers | ||
+ | <math>a, {a+2,} {a+4,} \dots, {a + n(n-1)}</math>, where <math>a = n - \frac{n(n-1)}2.</math> | ||
+ | |||
+ | This is certainly true for <math>n=1</math>. Suppose that it is true for <math>n = m-1 \ge 1</math>, and note that the zeros of <math>f_m</math> are the solutions of <math>|x - m| = k</math>, where <math>k</math> is a nonnegative zero of <math>f_{m-1}</math>. Because the zeros of <math>f_{m-1}</math> form an arithmetic sequence with common difference <math>2,</math> so do the zeros of <math>f_m</math>. The greatest zero of <math>f_{m-1}</math> is<cmath>m-1+\frac{(m-1)(m-2)}2 =\frac{m(m-1)}2,</cmath>so the greatest zero of <math>f_m</math> is <math>m+\frac{m(m-1)}2</math> and the least is <math>m-\frac{m(m-1)}2</math>. | ||
+ | |||
+ | It follows that the number of zeros of <math>f_n</math> is <math>\frac{n(n-1)}2+1=\frac{n^2-n+2}2</math>, and their average value is <math>n</math>. The sum of the zeros of <math>f_n</math> is<cmath>\frac{n^3-n^2+2n}2.</cmath>Let <math>S(n)=n^3-n^2+2n</math>, so the sum of the zeros exceeds <math>500{,}000</math> if and only if <math>S(n) > 1{,}000{,}000 = 100^3\!.</math> Because <math>S(n)</math> is increasing for <math>n > 2</math>, the values <math>S(100) = 1{,}000{,}000 - 10{,}000 + 200 = 990{,}200</math> and <math>S(101)=1{,}030{,}301 - 10{,}201 + 202 = 1{,}020{,}302</math> show that the requested value of <math>n</math> is <math>\boxed{101}</math>. | ||
+ | |||
+ | ==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. | ||
+ | |||
+ | <cmath>\begin{array}{c|c|c|c} | ||
+ | n&Solutions&number&sum\\ | ||
+ | 1&1&1&1\\ | ||
+ | 2&1,3&2&4\\ | ||
+ | 3&0,2,4,6&4&12\\ | ||
+ | 4&-2,0,2...10&7&28\\ | ||
+ | 5&-5,-3,-1...15&11&55\\ | ||
+ | \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. | ||
+ | |||
+ | <math>n \cdot [1+\frac{n(n-1)}{2}]>500,000</math> | ||
+ | |||
+ | Multiplying both sides by <math>2</math>, | ||
+ | |||
+ | <math>n \cdot [2+n(n-1)]>1,000,000</math> | ||
+ | |||
+ | 1 million is <math>10^6=100^3</math>, so the solution should be close to <math>100</math>. | ||
+ | |||
+ | 100 is slightly too small, so <math>\boxed{101}</math> works. | ||
+ | |||
+ | ~ dragnin | ||
+ | |||
+ | ==Video Solution== | ||
+ | https://youtu.be/EwGydCuoHNM | ||
+ | |||
+ | ~MathProblemSolvingSkills.com | ||
+ | |||
+ | ==Video Solution== | ||
+ | https://youtu.be/g13o0wgj4p0 | ||
+ | |||
==See Also== | ==See Also== | ||
{{AIME box|year=2020|n=II|num-b=7|num-a=9}} | {{AIME box|year=2020|n=II|num-b=7|num-a=9}} | ||
+ | [[Category:Intermediate Algebra Problems]] | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 11:22, 20 January 2024
Contents
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
is
so 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
is
Let
, 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.
Multiplying both sides by ,
1 million is , so the solution should be close to
.
100 is slightly too small, so works.
~ dragnin
Video Solution
~MathProblemSolvingSkills.com
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.