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

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

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 n^2+n+9 \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 smallest 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 -8 \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 by MathLearner01

See also

2017 AIME I (ProblemsAnswer KeyResources)
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