Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2020 AIME II Problems/Problem 8"

m (→‎Video Solution)
(→‎Solution (Official MAA))
Line 2: Line 2:
 
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>.
 
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 (Official MAA)==
+
==Solution 1 (Official MAA)==
 
First it will be shown by induction that the zeros of <math>f_n</math> are the integers
 
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>
 
<math>a, {a+2,} {a+4,} \dots, {a + n(n-1)}</math>, where <math>a = n - \frac{n(n-1)}2.</math>
Line 9: Line 9:
  
 
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>.
 
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.
 +
 +
\begin{center}
 +
\begin{tabular}{ c c c c }
 +
<math>x</math> & 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 & -9,-7,-5...21 & 11 & 55 \\
 +
\end{tabular}
 +
\end{center}
 +
 +
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==
 
==Video Solution==

Revision as of 21:37, 6 May 2023

Problem

Define a sequence recursively by $f_1(x)=|x-1|$ and $f_n(x)=f_{n-1}(|x-n|)$ for integers $n>1$. Find the least value of $n$ such that the sum of the zeros of $f_n$ exceeds $500,000$.

Solution 1 (Official MAA)

First it will be shown by induction that the zeros of $f_n$ are the integers $a, {a+2,} {a+4,} \dots, {a + n(n-1)}$, where $a = n - \frac{n(n-1)}2.$

This is certainly true for $n=1$. Suppose that it is true for $n = m-1 \ge 1$, and note that the zeros of $f_m$ are the solutions of $|x - m| = k$, where $k$ is a nonnegative zero of $f_{m-1}$. Because the zeros of $f_{m-1}$ form an arithmetic sequence with common difference $2,$ so do the zeros of $f_m$. The greatest zero of $f_{m-1}$ is\[m-1+\frac{(m-1)(m-2)}2 =\frac{m(m-1)}2,\]so the greatest zero of $f_m$ is $m+\frac{m(m-1)}2$ and the least is $m-\frac{m(m-1)}2$.

It follows that the number of zeros of $f_n$ is $\frac{n(n-1)}2+1=\frac{n^2-n+2}2$, and their average value is $n$. The sum of the zeros of $f_n$ is\[\frac{n^3-n^2+2n}2.\]Let $S(n)=n^3-n^2+2n$, so the sum of the zeros exceeds $500{,}000$ if and only if $S(n) > 1{,}000{,}000 = 100^3\!.$ Because $S(n)$ is increasing for $n > 2$, the values $S(100) = 1{,}000{,}000 - 10{,}000 + 200 = 990{,}200$ and $S(101)=1{,}030{,}301 - 10{,}201 + 202 = 1{,}020{,}302$ show that the requested value of $n$ is $\boxed{101}$.

Solution 2 (Same idea, easier to see)

Starting from $f_1(x)=|x-1|$, we can track the solutions, the number of solutions, and their sum.

\begin{center} \begin{tabular}{ c c c c } 

$x$ & 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 & -9,-7,-5...21 & 11 & 55 \\

\end{tabular} \end{center}

It is clear that the solutions form arithmetic sequences with a difference of 2, and the negative solutions cancel out all but $n$ of the $1+\frac{n(n-1)}{2}$ solutions. Thus, the sum of the solutions is $n \cdot [1+\frac{n(n-1)}{2}]$, which is a cubic function.

$n \cdot [1+\frac{n(n-1)}{2}]>500,000$

Multiplying both sides by $2$,

$n \cdot [2+n(n-1)]>1,000,000$

1 million is $10^6=100^3$, so the solution should be close to $100$.

100 is slightly too small, so $\boxed{101}$ works.

~ dragnin

Video Solution

https://youtu.be/EwGydCuoHNM

~MathProblemSolvingSkills.com

Video Solution

https://youtu.be/g13o0wgj4p0

~IceMatrix

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_II_Problems/Problem_8&oldid=192845"