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"

(→‎Solution 3)
(→‎Solution 3)
Line 34: Line 34:
 
<math>a_n=a_{n-1} + n \pmod{99}</math>.  Using the steps of the previous solution we get up to <math>n^2+n+ \equiv 90 \pmod{99}</math>. This gives away the fact that <math>(n)(n+1) \equiv 0 \pmod{9} \implies n \equiv \{0, 8\} \pmod{9}</math> so either <math>n</math> or <math>n+1</math> must be a multiple of 9.  
 
<math>a_n=a_{n-1} + n \pmod{99}</math>.  Using the steps of the previous solution we get up to <math>n^2+n+ \equiv 90 \pmod{99}</math>. This gives away the fact that <math>(n)(n+1) \equiv 0 \pmod{9} \implies n \equiv \{0, 8\} \pmod{9}</math> so either <math>n</math> or <math>n+1</math> must be a multiple of 9.  
  
−
Case 1 (<math>n|9</math>): Say <math>n=9x</math> and after simplification <math>x(9x+1) = 10y \forall x \in \mathbb{Z}</math>.   
+
Case 1 (<math>n|9</math>): Say <math>n=9x</math> and after simplification <math>x(9x+1) = 10 \pmod{90} \forall x \in \mathbb{Z}</math>.   
 +
 
 +
Case 2: (<math>n+1|9</math>): Say <math>n=9a</math> and after simplification <math>(9a-1)(a) = 10 \pmod{90} \forall a \in \mathbb{Z}</math>.
 +
 
 +
As a result <math>a</math> must be a divisor of <math>10</math> and after doing some testing in both cases the smallest value that works is <math>x=5 \implies \boxed{45}</math>.
 +
 
 +
~First
  
−
Case 2: (<math>n+1|9</math>): Say <math>n=9a</math> and after simplification <math>(9a-1)(a) = 10b \forall a \in \mathbb{Z}</math>.
 
−
Using the AIME  answer format and the restrictions of the problem:
 
−
<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 17:40, 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 $n^2+n+ \equiv 90 \pmod{99}$. This gives away the fact that $(n)(n+1) \equiv 0 \pmod{9} \implies n \equiv \{0, 8\} \pmod{9}$ so either $n$ or $n+1$ must be a multiple of 9.

Case 1 ($n|9$): Say $n=9x$ and after simplification $x(9x+1) = 10 \pmod{90} \forall x \in \mathbb{Z}$.

Case 2: ($n+1|9$): Say $n=9a$ and after simplification $(9a-1)(a) = 10 \pmod{90} \forall a \in \mathbb{Z}$.

As a result $a$ must be a divisor of $10$ and after doing some testing in both cases the smallest value that works is $x=5 \implies \boxed{45}$.

~First


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. AMC logo.png

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