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 | + | 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 15:22, 8 March 2017
Problem 9
Let , and for each integer
let
. Find the least
such that
is a multiple of
.
Solution
Writing out the recursive statement for and summing them gives
Which simplifies to
Therefore,
is divisible by 99 if and only if
is divisible by 99, so
needs to be divisible by 9 and 11. Assume that
is a multiple of 11. Writing out a few terms,
, we see that
is the smallest
that works in this case. Next, assume that
is a multiple of 11. Writing out a few terms,
, we see that
is the smallest
that works in this case. The smallest
is
.