Difference between revisions of "2017 AIME I Problems/Problem 9"

Revision as of 15:29, 9 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 1

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{045}$ .

Solution 2

$a_n \equiv a_{n-1} + n \pmod {99}$ By looking at the first few terms, we can see that $a_n \equiv 10+11+12+ \dots + n \pmod {99}$ This implies $a_n \equiv \frac{n(n+1)}{2} - \frac{10*9}{2} \pmod {99}$ Since $a_n \equiv 0 \pmod {99}$ , we can rewrite the equivalence, and simplify $0 \equiv \frac{n(n+1)}{2} - \frac{10*9}{2} \pmod {99}$ $0 \equiv n(n+1) - 90 \pmod {99}$ $0 \equiv 4n^2+4n+36 \pmod {99}$ $0 \equiv (2n+1)^2+35 \pmod {99}$ $64 \equiv (2n+1)^2 \pmod {99}$ The only squares that are congruent to $64 \pmod {99}$ are $(\pm 8)^2$ and $(\pm 19)^2$ , so $2n+1 \equiv -8, 8, 19, \text{or } {-19} \pmod {99}$ $2n+1 \equiv -8 \pmod {99}$ yields $n=45$ as the smallest integer solution.

$2n+1 \equiv 8 \pmod {99}$ yields $n=53$ as the smallest integer solution.

$2n+1 \equiv -19 \pmod {99}$ yields $n=89$ as the smallest integer solution.

$2n+1 \equiv 19 \pmod {99}$ yields $n=9$ as the smallest integer solution. However, $n$ must be greater than $10$ .

The smallest positive integer solution greater than $10$ is $n=\boxed{045}$ .

Solution 3

$a_n=a_{n-1} + n \pmod{99}$ . Using the steps of the previous solution we get up to $0 \equiv n^2+n+9 \pmod {99}$ $n=9y \implies 9y^2+y+1 \equiv 0 \pmod{11}$ Since this is the AIME and $y>1$ you get $2 \leq n \leq 111$ . You can use trial and error to get $y=5 \implies \boxed{45}$ but if you want a smarter way see below: Factor to get $y(9y+1) \equiv 10 \pmod{11}$ so $y \equiv \{1, 2, 5, 10\} \pmod{11}$ and then testing all of them only $y \equiv 5 \pmod{11}$ works so $y=5 \implies \boxed{45}$ .

@@ Line 16: / Line 16: @@
 <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>
@@ Line 31: / Line 30: @@
 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==
 {{AIME box|year=2017|n=I|num-b=8|num-a=10}}
 {{MAA Notice}}

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

Page

Toolbox

Search