Difference between revisions of "2017 AIME I Problems/Problem 9"
m |
(→Solution 2) |
||
Line 16: | Line 16: | ||
<cmath>0 \equiv \frac{n(n+1)}{2} - \frac{10*9}{2} \pmod {99} </cmath> | <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(n+1) - 90 \pmod {99} </cmath> | ||
− | |||
<cmath>0 \equiv 4n^2+4n+36 \pmod {99} </cmath> | <cmath>0 \equiv 4n^2+4n+36 \pmod {99} </cmath> | ||
<cmath>0 \equiv (2n+1)^2+35 \pmod {99} </cmath> | <cmath>0 \equiv (2n+1)^2+35 \pmod {99} </cmath> | ||
Line 31: | Line 30: | ||
The smallest positive integer solution greater than <math>10</math> is <math>n=\boxed{045}</math>. | The smallest positive integer solution greater than <math>10</math> is <math>n=\boxed{045}</math>. | ||
+ | |||
+ | ==Solution 3== | ||
+ | <math>a_n=a_{n-1} + n \pmod{99}</math>. | ||
+ | Using the steps of the previous solution we get up to | ||
+ | <cmath>0 \equiv n^2+n+9 \pmod {99} </cmath> | ||
+ | <cmath>n=9y \implies 9y^2+y+1 \equiv 0 \pmod{11}</cmath> | ||
+ | Since this is the AIME and <cmath>y>1</cmath> you get <cmath>2 \leq n \leq 111</cmath>. You can use trial and error to get <math>y=5 \implies \boxed{45}</math> but if you want a smarter way see below: | ||
+ | Factor to get <cmath>y(9y+1) \equiv 10 \pmod{11}</cmath> so <math>y \equiv \{1, 2, 5, 10\} \pmod{11}</math> and then testing all of them only <math>y \equiv 5 \pmod{11}</math> works so <math>y=5 \implies \boxed{45}</math>. | ||
==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 16:29, 9 March 2017
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 only 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 3
.
Using the steps of the previous solution we get up to
Since this is the AIME and
you get
. You can use trial and error to get
but if you want a smarter way see below:
Factor to get
so
and then testing all of them only
works so
.
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.