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 "2017 AIME I Problems/Problem 9"

(Created page with "==Problem 9== Let <math>a_{10} = 10</math>, and for each integer <math>n >10</math> let <math>a_n = 100a_{n - 1} + n</math>. Find the least <math>n > 10</math> such that <math...")
 
m
Line 5: Line 5:
 
Writing out the recursive statement for <math>a_n, a_{n-1}, \dots, a_{10}</math> and summing them gives <cmath>a_n+\dots+a_{10}=100(a_{n-1}+\dots+a_{10})+n+\dots+10</cmath>
 
Writing out the recursive statement for <math>a_n, a_{n-1}, \dots, a_{10}</math> and summing them gives <cmath>a_n+\dots+a_{10}=100(a_{n-1}+\dots+a_{10})+n+\dots+10</cmath>
 
Which simplifies to <cmath>a_n=99(a_{n-1}+\dots+a_{10})+\frac{1}{2}(n+10)(n-9)</cmath>
 
Which simplifies to <cmath>a_n=99(a_{n-1}+\dots+a_{10})+\frac{1}{2}(n+10)(n-9)</cmath>
−
Therefore, <math>a_n</math> is divisible by <math>99</math> if and only if <math>\frac{1}{2}(n+10)(n-9)</math> is divisible by 99, so <math>(n+10)(n-9)</math> needs to be divisible by 9 and 11. Assume that <math>n+10</math> is a multiple of 11. Writing out a few terms, <math>n=12, 23, 34, 45</math>, we see that <math>n=45</math> is the smallest <math>n</math> that works in this case. Next, assume that <math>n-9</math> is a multiple of 11. Writing out a few terms, <math>n=20, 31, 42, 53</math>, we see that <math>n=53</math> is the smallest <math>n</math> that works in this case. The smallest <math>n</math> is <math>\boxed{45}</math>.
+
Therefore, <math>a_n</math> is divisible by 99 if and only if <math>\frac{1}{2}(n+10)(n-9)</math> is divisible by 99, so <math>(n+10)(n-9)</math> needs to be divisible by 9 and 11. Assume that <math>n+10</math> is a multiple of 11. Writing out a few terms, <math>n=12, 23, 34, 45</math>, we see that <math>n=45</math> is the smallest <math>n</math> that works in this case. Next, assume that <math>n-9</math> is a multiple of 11. Writing out a few terms, <math>n=20, 31, 42, 53</math>, we see that <math>n=53</math> is the smallest <math>n</math> that works in this case. The smallest <math>n</math> is <math>\boxed{45}</math>.

Revision as of 16:22, 8 March 2017

Problem 9

Let $a_{10} = 10$, and for each integer $n >10$ let $a_n = 100a_{n - 1} + n$. Find the least $n > 10$ such that $a_n$ is a multiple of $99$.

Solution

Writing out the recursive statement for $a_n, a_{n-1}, \dots, a_{10}$ and summing them gives \[a_n+\dots+a_{10}=100(a_{n-1}+\dots+a_{10})+n+\dots+10\] Which simplifies to \[a_n=99(a_{n-1}+\dots+a_{10})+\frac{1}{2}(n+10)(n-9)\] Therefore, $a_n$ is divisible by 99 if and only if $\frac{1}{2}(n+10)(n-9)$ is divisible by 99, so $(n+10)(n-9)$ needs to be divisible by 9 and 11. Assume that $n+10$ is a multiple of 11. Writing out a few terms, $n=12, 23, 34, 45$, we see that $n=45$ is the smallest $n$ that works in this case. Next, assume that $n-9$ is a multiple of 11. Writing out a few terms, $n=20, 31, 42, 53$, we see that $n=53$ is the smallest $n$ that works in this case. The smallest $n$ is $\boxed{45}$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2017_AIME_I_Problems/Problem_9&oldid=84463"