Difference between revisions of "2017 AIME I Problems/Problem 9"
m (→Solution) |
(added solution) |
||
Line 2: | Line 2: | ||
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>a_n</math> is a multiple of <math>99</math>. | 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>a_n</math> is a multiple of <math>99</math>. | ||
− | ==Solution== | + | ==Solution 1== |
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 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>. | 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>. | ||
+ | ==Solution 2== | ||
+ | <cmath>a_n \equiv a_{n-1} + n \pmod {99} </cmath> | ||
+ | By looking at the first few terms, we can see that | ||
+ | <cmath>a_n \equiv 10+11+12+ \dots + n \pmod {99} </cmath> | ||
+ | This implies | ||
+ | <cmath>a_n \equiv \frac{n(n+1)}{2} - \frac{10*9}{2} \pmod {99} </cmath> | ||
+ | Since <math>a_n \equiv 0 \pmod {99}</math>, we can rewrite the equivalence, and simplify | ||
+ | <cmath>0 \equiv \frac{n(n+1)}{2} - \frac{10*9}{2} \pmod {99} </cmath> | ||
+ | <cmath>0 \equiv n(n+1) - 90 \pmod {99} </cmath> | ||
+ | <cmath>0 \equiv n^2+n+9 \pmod {99} </cmath> | ||
+ | <cmath>0 \equiv 4n^2+4n+36 \pmod {99} </cmath> | ||
+ | <cmath>0 \equiv (2n+1)^2+35 \pmod {99} </cmath> | ||
+ | <cmath>64 \equiv (2n+1)^2 \pmod {99} </cmath> | ||
+ | The smallest squares that are congruent to <math>64 \pmod {99}</math> are <math>(\pm 8)^2</math> and <math>(\pm 19)^2</math>, so | ||
+ | <cmath>2n+1 \equiv -8, 8, 19, \text{or } {-19} \pmod {99}</cmath> | ||
+ | <math>2n+1 \equiv -8 \pmod {99}</math> yields <math>n=45</math> as the smallest integer solution. | ||
+ | |||
+ | <math>2n+1 \equiv 8 \pmod {99}</math> yields <math>n=53</math> as the smallest integer solution. | ||
+ | |||
+ | <math>2n+1 \equiv -19 \pmod {99}</math> yields <math>n=89</math> as the smallest integer solution. | ||
+ | |||
+ | <math>2n+1 \equiv -8 \pmod {99}</math> yields <math>n=9</math> as the smallest integer solution. However, <math>n</math> must be greater than <math>10</math>. | ||
+ | |||
+ | The smallest positive integer solution greater than <math>10</math> is <math>n=\boxed{045}</math>. | ||
+ | |||
+ | <i> Solution by MathLearner01 </i> | ||
==See also== | ==See also== | ||
{{AIME box|year=2017|n=I|num-b=8|num-a=10}} | {{AIME box|year=2017|n=I|num-b=8|num-a=10}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 18:19, 8 March 2017
Contents
[hide]Problem 9
Let , and for each integer let . Find the least such that is a multiple of .
Solution 1
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 .
Solution 2
By looking at the first few terms, we can see that This implies Since , we can rewrite the equivalence, and simplify The smallest squares that are congruent to are and , so yields as the smallest integer solution.
yields as the smallest integer solution.
yields as the smallest integer solution.
yields as the smallest integer solution. However, must be greater than .
The smallest positive integer solution greater than is .
Solution by MathLearner01
See also
2017 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 8 |
Followed by Problem 10 | |
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.